Programming Praxis

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 x^r−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)
190
> (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