[Primes Home][Home]
Lehmann's Primality Test allows us to test is an integer (\(n\) is prime. For this Lehmann defined that this is try: \(a^{(n-1)/2} \equiv \pm 1\) for every value of \(a\).
Lehmann's Primality Test
[Primes Home][Home]
Lehmann's Primality Test allows us to test is an integer (\(n\) is prime. For this Lehmann defined that this is try: \(a^{(n-1)/2} \equiv \pm 1\) for every value of \(a\).
|
import sys n=97 if (len(sys.argv)>1): n=int(sys.argv[1]) if (n>200): sys.exit() for a in range(1,n): val = pow(a,(n-1)//2,n) if (val>1): print (a,val-n) else: print (a,val)
A sample run for \(n=27\) is:
1 1 2 1 3 1 4 1 5 -1 6 1 7 -1 8 1 9 1 10 -1 11 1 12 1 13 -1 14 -1 15 -1 16 1 17 -1 18 1 19 -1 20 -1 21 -1 22 1 23 -1 24 1 25 1 26 -1 27 1
A sample run with \(n=25\) gives:
C:\python3>python leh.py 25 1 1 2 -4 3 -9 4 -9 5 0 6 -14 7 1 8 -14 9 -19 10 0 11 -4 12 -19 13 -19 14 -4 15 0 16 -19 17 -14 18 1 19 -14 20 0 21 -9 22 -9 23 -4 24 1
and \(n=26\):
C:\python3>python leh.py 26 1 1 2 -12 3 1 4 -12 5 1 6 -12 7 1 8 -12 9 1 10 -12 11 1 12 -12 13 -13 14 -12 15 1 16 -12 17 1 18 -12 19 1 20 -12 21 1 22 -12 23 1 24 -12 25 1