use Math::BigInt; 	#allows big integers needed for this algorithm


$x=$k=0;
#$M=$ARGV[0]-1;
#$n=$ARGV[0]; 						#testing variable

$data_file="primelist.txt"; 	#imports known primes (91000-93000)
open(DAT, $data_file) || die("Could not open file!");
@raw_data=<DAT>;
close(DAT);

foreach $line(@raw_data) { #puts text file into a stepped array @prime
	$tempPrime=$line;
	@prime = split(/:/, $line);
}
# foreach $line(@prime) {	#makes sure primes are loaded in array
# print "$line\n";
# }




	
for ($n=91001; $n<93000; $n++) {
	$counter=0;
	$M=$n-1;
	print "\$n: $n\n";
	while ($M%2 != 1) {  	# Loop to calculate $M and $k (2^k*M)
		$M=$M/2;
		$k+=1;
		#print "K=$k, M=$M\n";
		}
	for($a = 2; $a<($n-1);$a++){
		 my $tempA = Math::BigInt->new($a);
		 $b = $tempA->bmodpow($M,$n);  	#set b = a^m mod n
		 #print "\$b=$b\n"; 				#tells us what b is
		 		
		if ($b==1) {     				#test 1 (does b=1?)
			#print "$n: Prime (test1)\n";
			$counter++;
		} else {  
		
		for ($i=0; $i<$k; $i++) {
			if ($b==($n-1)) {
				#print "\$b-temp=$b\n";
				$counter++;
				#print "$n is a prime (test2)\n";
				last; 					#exits loop upon $b==1
				
			} else {
				$tempB = Math::BigInt->new($b);
				$b = $tempB->bmodpow(2,$n);
				#print "$b\n";
				#print "$n is composite\n";
				}                                                   
			}                                                          
										#print "\$a\=: $a\n";
		}
	}
	$ticker[$n]=$counter;	#Keep track of number of false positives
	$percentage[$n]=$counter/$n;		#Figure out percentage
	print "Counter: $ticker[$n]\n";
	print "Percentage: $percentage[$n]\n";
	$n++;
}