Pocklington’s N-1 Primality Prover

September 28, 2012

The first if identifies obvious composites, and the second if does trial division to a million, which will be faster than anything else we can do. Then f-loop gathers factors until f exceeds the cube root of n, using both trial division and Pollard’s rho method, a-loop finds a suitable witness, and the last two clauses of the cond make the determination.

(define (pocklington? n)
  (if (not (pseudoprime? n)) #f
    (if (< n #e1e12) (= (car (td n #e1e6)) n)
      (let* ((n-1 (- n 1))
             (root2 (iroot 2 n)) (root3 (iroot 3 n))
             (fs (td n-1 1000)) (f (apply * fs)))
        (let f-loop ((f f) (fs fs))
          (if (< f root3)
              (let ((p (rho (/ n-1 f) #e1e6)))
                (if p (f-loop (* f p) (cons p fs)) 'unknown))
              (let a-loop ((a 2))
                (if (not (= (expm a n-1 n) 1)) #f
                  (let loop ((fs fs))
                    (let ((g (gcd (- (expm a (/ n-1 (car fs)) n) 1) n)))
                      (cond ((< 1 g n) #f)
                            ((= g n) (a-loop (+ a 1)))
                            ((pair? (cdr fs)) (loop (cdr fs)))
                            ((< root2 f) #t)
                            (else (let* ((ds (digits n f))
                                         (c2 (car ds)) (c1 (cadr ds))
                                         (s (- (* c1 c1) (* 4 c2))))
                                    (not (square? s)))))))))))))))

Here are some examples. Note the test of 3825123056546413051, which is a strong pseudoprime to bases 2, 3 and 5, but is correctly identified as composite by the Pocklington test. By the way, the symbol unknown is considered to be true by Scheme, which you will want to consider as you are checking return values from the function:

> (pocklington? (mersenne 89))
> (pocklington? (mersenne 521))
> (pocklington? (mersenne 607))
> (pseudoprime? 3825123056546413051)
> (pocklington? 3825123056546413051)

We stole much code from the Standard Prelude and previous exercises, too much to make a list here, but you can see it all assembled at http://programmingpraxis.codepad.org/UB4OxZv1.

About these ads

Pages: 1 2

5 Responses to “Pocklington’s N-1 Primality Prover”

  1. David said

    I’m not sure what happens when sufficient factors are found but the number is composite. You would have to test every a where 1 < a < n – 1, which is a heck of a lot of candidates. For that matter, what if a number is prime, but the witness is closer to n-1 than 1?

  2. programmingpraxis said

    If N is composite, you will waste a lot of time trying to prove that it is prime. Sorry. That’s why you should do one or several probable-prime tests before you start.

  3. PeterD said

    It seems to not be widely known that in the Pocklington test, the “a” doesn’t have to be the same for each (or any 2) prime q|f. There just needs to be some aq that passes for each q.

    This is mentioned in Handbook of Applied Cryptography, 4.7 Notes and further references: “In Fact 4.38, the integer a does not have to be the same for all q. [...] The same is true of Fact 4.40, which is due to Pocklington [981].”

    So, in the algorithm described above, it’s unnecessary to stop testing with a=2 just because one of the factors failed, and for a=3 and, more importantly, it’s unnecessary to re-test any q that already passed with any earlier ‘a’.

  4. Adrian said

    Hello, I’m a prime numbers fan and I have some cuestions about “extended Pocklington’s theorem”:

    1-What method are you using to calculate c1 and c2?, I understand you resolve this equation with Bezout id:

    n = C2 f^2 + C1 f + 1

    n-1 = C2 f^2 + C1 f (type y=xa+xb “diofantic equation” with y=n-1, a= f^2, b=f, x=C2, y=C1)

    but the are infinite solutions the first in your example can be C2=0 and C1=4230740453823643 and you have C2=28917 and C1=96609474553. Are all solutions avalaible to test the perfect square condition?

    2-If f need to be between cube root and square root of n. You have:

    cube root < f < square root?

    but in example "f = 146302999770 is greater than the cube root of n." you are not comparing if f = 146302999770 < square root.

    3-Can you apply this extension without Pocklington original?

    I understand if c1 and c2 hold the perfect square conditions you know if number is prime or not. Why it's necessary to prove pocklington first?

    4-Is this the best method to calculate primality of n knowing factors of n-1? Where can I see the implementation?

    Regards from Spain

  5. programmingpraxis said

    @Adrian: Welcome to Programming Praxis!

    1) c1 and c2 are calculated as the “digits” of n to the base f.

    2) f can be larger than the square root of n. If it is, that simplifies the calculation. If not, the primality of n can be proved as long as f is greater than the cube root of n.

    3) Because that’s the way the algorithm works.

    4) If you know all the factors of n-1 you can use Lucas’ algorithm instead of Pocklington’s. You can see the implementation by following the links in the last paragraph or by clicking through to Page 2 of the blog entry.

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


Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: