jsMath

Number Theory - primality

Primality testing via Fermat's Little Theorem:
n=3409503222440054020204050683098097097 Mod(2,n)^(n-1) 
        
256

Factoring n might take a lot longer:
factor(n) 
        
3^2 * 378833691382228224467116742566455233
is_prime(n) 
        
False

Finding all Carmichael numbers up to 7000:
for n in range(2,7000): if not is_prime(n): carmichael = True for a in range(1,n): if Mod(a,n)^n != Mod(a,n): carmichael = False break if carmichael: print n 
        
561
1105
1729
2465
2821
6601

We can check for a given number n, what percentage of 1<= a<n are witnesses that n is not prime:
def witness(n): count = 0 for a in range(1,n): if Mod(a,n)^n != Mod(a,n): count +=1 print float(count/n) 
       
witness(287) 
        
0.968641114983
witness(190) 
        
0.789473684211
witness(808) 
        
0.99504950495