AKS Primality Prover, Part 1

October 2, 2012

Finding the multiplicative order of n modulo r is easy; we just start with k = 2 and keep incrementing k until we find the answer:

(define (compute-r n)
  (let ((target (* 4 (square (log2 n)))))
    (if (not (td-prime? n)) #f
      (do ((r 3 (+ r 1)))
          ((and (not (= r n)) (< target (ord r n))) r)))))

We represent a polynomial as a list of its coefficients, most significant first, and use several helper functions to compute the modular multiplication of two polynomials. Plus adds two polynomials, assuming that the leading coefficients have the same degree; we can’t use map because they might have different lengths. Mod-poly performs the modulo operation on two polynomials, with the second of form xr−1, by splitting the list of coefficients at r and adding the two pieces. Times and mod-n performs normal integer operations. The coefficients of the first polynomial are reversed, so multiplication proceeds right-to-left, and a leading zero is added to each polynomial to make the degrees of the two addends the same:

(define (poly-mult-mod xs ys r n)
  (define (times x) (lambda (y) (* x y)))
  (define (plus xs ys)
    (let loop ((xs xs) (ys ys) (zs (list)))
      (cond ((null? xs) (reverse (append (reverse ys) zs)))
            ((null? ys) (reverse (append (reverse xs) zs)))
            (else (loop (cdr xs) (cdr ys)
                        (cons (+ (car xs) (car ys)) zs))))))
  (define (mod-poly xs)
    (let-values (((hs ts) (split r (reverse xs))))
      (reverse (plus hs ts))))
  (define (mod-n x) (modulo x n))
  (let ((xs (reverse xs)))
    (let loop ((xs (cdr xs)) (zs (map (times (car xs)) ys)))
      (if (null? xs) (map mod-n (mod-poly zs))
        (loop (cdr xs) (plus (cons 0 zs)
                             (map (times (car xs)) ys)))))))

Then modular exponentiation of a polynomial is done by the usual square-and-multiply method:

(define (poly-power-mod bs e r n)
  (let loop ((bs bs) (e e) (rs (list 1)))
    (if (zero? e) rs
      (loop (poly-mult-mod bs bs r n)
            (quotient e 2)
            (if (even? e) rs
              (poly-mult-mod rs bs r n))))))

Here are two examples:

> (ord 191 89)
> (poly-power-mod '(1 4 12 3) 2 5 17)
(6 0 15 5 0)

We used split and expm from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/xUSr2dTr.


Pages: 1 2

2 Responses to “AKS Primality Prover, Part 1”

  1. […] I’ll have a full write-up at my blog later this week: Part 1 and Part […]

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 )

Connecting to %s

%d bloggers like this: