In the Lehmann test [1] we select values of \(a\) and show that \(a^{(n-1)/2} \pmod {n}=\pm 1\) for a prime number (\(n\)). We will select different sizes of prime numbers and test them by generating up to 100 random values of \(a\).
Lehmann test for primality |
Theory
In the Lehmann test we select values of \(a\) and show that \(a^{(n-1) /2} \pmod {n}=\pm 1\) for a prime number (\(n\)). We will select different sizes of prime numbers (defined by the number of bits in the prime number) and test them by generating up to 100 random values of \(a\):
import random import sys from Crypto.Util.number import getPrime from Crypto.Random import get_random_bytes primebits=64 if (len(sys.argv)>1): primebits=int(sys.argv[1]) n = getPrime(primebits,randfunc=get_random_bytes) print (f"Prime number has {primebits} bits and is {n}\n") for i in range (1,100): a = random.randint(2,100) res=pow(a,(n-1)//2,n) print (f"[a={a}, res={res}]",end=' ') if (res==1 or res==-1): print ("\n\nIt is prime") print (f"\n{a}^{(n-1)//2} (mod {n}) = {res}") sys.exit() print ("\n\nIt is not likely to be a prime")
A sample run of a 64-bit prime number is:
Prime number is 15295822202028749467 [a=99, res=15295822202028749466] [a=42, res=15295822202028749466] [a=26, res=1] It is prime 26^7647911101014374733 mod 15295822202028749467 = 1
A sample run for a 256-bit prime number:
Prime number is 98966833787083080336599445239568993344820392527910451601686258027733103498011 [a=66, res=98966833787083080336599445239568993344820392527910451601686258027733103498010] [a=78, res=98966833787083080336599445239568993344820392527910451601686258027733103498010] [a=14, res=1] It is prime 14^49483416893541540168299722619784496672410196263955225800843129013866551749005 mod 98966833787083080336599445239568993344820392527910451601686258027733103498011 = 1
and:
Prime number is 95168745464491343095426904965808174127244976341285457855655737804874362319157 [a=70, res=95168745464491343095426904965808174127244976341285457855655737804874362319156] [a=57, res=95168745464491343095426904965808174127244976341285457855655737804874362319156] [a=59, res=1] It is prime 59^47584372732245671547713452482904087063622488170642728927827868902437181159578 mod 95168745464491343095426904965808174127244976341285457855655737804874362319157 = 1
And for a 512-bit prime:
Prime number has 512 bits and is 10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842243 [a=58, res=10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842242] [a=58, res=10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842242] [a=63, res=10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842242] [a=7, res=10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842242] [a=20, res=10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842242] [a=13, res=10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842242] [a=95, res=10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842242] [a=100, res=1] It is prime 100^5109174713551817977460054356482586271524632345735571133423528688062143484490306719071857314868071517045185394556539285512066727763647788740384920967421121 (mod 10218349427103635954920108712965172543049264691471142266847057376124286968980613438143714629736143034090370789113078571024133455527295577480769841934842243) = 1
References
[1] Lehmann, D. J. (1982). On primality tests. SIAM Journal on Computing, 11(2), 374-375 [link].