## 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))`

#t

> (pocklington? (mersenne 521))

#t

> (pocklington? (mersenne 607))

unknown

> (pseudoprime? 3825123056546413051)

#t

> (pocklington? 3825123056546413051)

#f

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.

Pages: 1 2

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?

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.

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’.