I'm new to this, I tried writing a code compare Guass' Lemma and Euler's Criteria for finding the Legendre symbol for any 2 numbers, they both work perfectly fine for small numbers (less than 5 digits) but at some point above that they always give different answers. Can anyone out there point out why at least one of the methods fails with large numbers? As an example, LS(n<20510/1047290) is right but LS(n>20511/104729) gives different answers. Thank you. 

use strict;
use warnings;
use integer;
use Time::HiRes;
use Benchmark;

my ($qa,$a,$b,$p,$k,$t,$c,$z,$w,$n,$r);
my ($start_run,$end_run,$run_time);
my ($start_rune,$end_rune,$run_timee);

print "Find Legendre symbol of:";
$qa=<>;
print "modulo:";
$p=<>;
#Gauss
$start_run = time();
$c=($p+1)/2;
$n=0;
$k=1;
while($k < $c){
    $r=$k*$qa;
    $r= $r % $p;
    if ($r > $p/2)    {
        $n++;
    
        }    
    $k++;
}
if($n % 2){
    $w=-1;
}
else{
    $w=1;
}
$end_run = time();
$run_time = $end_run - $start_run;

#Euler
$start_rune = time();
$c=($p-1)/2;
$t=1;
$k=$qa;
while ($t ne $c){
    $k=$k*$qa; 
    $t++;
    $k=$k % $p;
}
if($k == 1){
    $z=1;
}  
else{
    $z=-1;
}
$end_rune = time();
$run_timee = $end_run - $start_run;
if($w ne $z){
    print "algorithms disagree for $qa mod $p \n";
    exit;
}
if($z == 1){
    print "quad res \n";
}
else{
    print "not quad res \n";
}
print "Running time for Guass Lemma: $run_time seconds\n";
print "Running time for Eulers Criterion: $run_timee seconds\n";

[download]

EDIT: edited code so compiles

In reply to dealing with large numbers by waspoe1

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.