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.

About these ads

Pages: 1 2

6 Responses to “Frobenius Primality Test”

  1. Paul said

    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 ==  2
    
  2. programmingpraxis said

    Fixed the missing not-equals sign in Step 4. Thanks.

  3. Paul said

    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?

  4. programmingpraxis said

    Fixed both of those. Thanks. I didn’t do that very well, did I?

    I’m glad the debugging information was useful for you.

  5. Paul said

    Somtimes mistakes are made. Thanks a lot for the exercises. As you can see from my posts I am enjoying them a lot.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 598 other followers

%d bloggers like this: