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";