Frobenius Primality Test
November 13, 2012
As we know, it is difficult to prove that a number n is prime, so the usual recourse is a pseudoprimality test that is easy and fast but may possibly, though with very small probability, produce an incorrect answer. The most commonly used pseudoprimality test is doubtless the Miller-Rabin test, even though it is known to have errors in some circumstances. In today’s exercise we will examine the Frobenius test, which is an extension of and improvement on the Lucas test of a previous exercise.
Frobenius Pseudoprimality Test: Given an integer n greater than 2, determine with high probability if it is COMPOSITE or PROBABLY PRIME:
1. [Choose parameters] Set a and b to distinct random numbers uniformly distributed on the range 1 to n-1 inclusive. Set d = a^2 – 4b. If d is a perfect square or if gcd(2abd, n) ≠ 1 go to Step 1.
2. [Initialization] Set m = (n – (d/n)) / 2, where (d/n) is the jacobi symbol. Set w = a^2 * b^(-1) – 2 (mod n), where b^(-1) is the modular inverse of b with respect to n. Set u = 2. Set v = w. Set ms to a list of the bits in the binary representation of m, most significant bit first.
3. [Compute Lucas chain] If ms is empty, go to Step 4. If the first element of ms is 1, set u = u * v – w (mod n), set v = v * v – 2 (mod n), remove the first element of ms, and go to Step 3. If the first element of ms is 0, set v = u * v – w (mod n), set u = u * u – 2 (mod n), remove the first element of ms, and go to Step 3.
4. [Lucas test] If w * u ≠ 2 * v (mod n), report COMPOSITE and halt.
5. [Frobenius test] Set x = b ^ ((n-1)/2) (mod n). If x * u == 2 (mod n), report PROBABLY PRIME, otherwise report COMPOSITE. Halt.
A Frobenius test by itself isn’t perfect, so it is common to combine it with a Miller-Rabin pseudoprime test to just a few small bases.
Your task is to write a primality test based on Frobenius pseudoprimes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
A Python version. I had some problems with the formatting of the text in the exercise. Especially symbols as != seem to be missing. The debugging information given was most helpful. A full version is here.
def frobenius(n): """ returns True if n is probably prime """ if n % 2 == 0 or n < 2: return False #step 1 while 1: a = randint(1, n-1) b = randint(1, n-1) d = a ** 2 - 4 * b if not (is_square(d) or gcd(2 * a * b * d, n) != 1): break #step 2 m = (n - jacobi(d, n)) // 2 v = w = (a ** 2 * inverse(b, n) - 2) % n u = 2 # step 3 for bit in bits_of(m): if bit: u = (u * v - w) % n v = (v * v - 2) % n else: v = (u * v - w) % n u = (u * u - 2) % n # step 4 if (w * u - 2 * v) % n != 0: return False return (pow(b, (n - 1) // 2, n) * u) % n == 2Fixed the missing not-equals sign in Step 4. Thanks.
There is also something missing at the end of Step 1 line 1.
In step 2 v is set to 2. Should that not be v = w?
Fixed both of those. Thanks. I didn’t do that very well, did I?
I’m glad the debugging information was useful for you.
Somtimes mistakes are made. Thanks a lot for the exercises. As you can see from my posts I am enjoying them a lot.
[…] Pages: 1 2 […]