Improved Standard Continuation
November 8, 2011
Here is our version of the elliptic curve factorization function:
(define ec-factor ; Crandall/Pomerance Algorithm 7.4.4
(let* ((b1-saved 0) (b2-saved 0) (ps '()) (as '()) (ds '()) (d 210)
(sv (make-vector (+ d 1) #f)) (bv (make-vector (+ d 1) #f)))
(lambda (n b1 b2 s)
(when (not (and (= b1 b1-saved) (= b2 b2-saved)))
(set! b1-saved b1) (set! b2-saved b2) (set! ps (primes b2))
(set! as (let loop ((ps ps) (as (list)))
(let ((a (ilog (car ps) b1)))
(if (= a 1) (append (reverse as) (cycle 1))
(loop (cdr ps) (cons a as))))))
(set! ds (cons 0 (map (lambda (x) (/ x 2))
(map - (cdr ps) (reverse (cdr (reverse ps))))))))
(let-values (((an ad q) (curve12 n s)))
(let stage1 ((ps ps) (as as) (ds ds) (q q))
(if (< (car ps) b1)
(stage1 (cdr ps) (cdr as) (cdr ds)
(multiply (expt (car ps) (car as)) q an ad n))
(let ((g (gcd (cdr q) n))) (if (< 1 g n) (list 1 g)
(let* ((v (- b1 1)) (r (multiply v q an ad n))
(t (multiply (- b1 1 d d) q an ad n))
(alpha (modulo (* (car r) (cdr r)) n)))
(vector-set! sv 1 (double q an ad n))
(vector-set! sv 2 (double (vector-ref sv 1) an ad n))
(do ((i 3 (+ i 1))) ((< d i))
(vector-set! sv i
(add (vector-ref sv (- i 1))
(vector-ref sv 1)
(vector-ref sv (- i 2)) n)))
(do ((i 1 (+ i 1))) ((< d i))
(vector-set! bv i
(modulo (* (car (vector-ref sv i))
(cdr (vector-ref sv i))) n)))
(let stage2 ((v v) (ps ps) (ds ds) (r r) (t t) (g 1))
(if (null? ps) (let ((g (gcd g n))) (if (< 1 g n) (list 2 g) #f))
(let ((v2d (+ v d d)) (alpha (modulo (* (car r) (cdr r)) n)))
(let loop ((ps ps) (ds ds) (g g))
(if (and (pair? ps) (< (car ps) v2d))
(loop (cdr ps) (cdr ds) (modulo (* g (+ (*
(- (car r) (car (vector-ref sv (car ds))))
(+ (cdr r) (cdr (vector-ref sv (car ds)))))
(- alpha) (vector-ref bv (car ds)))) n))
(let* ((old-r r) (r (add r (vector-ref sv d) t n)))
(let ((g (gcd g n))) (if (< 1 g n) (list 2 g)
(stage2 v2d ps ds r old-r g))))))))))))))))))
The only change we made was to replace variable d with i and variable r with v; since some implementations of Scheme don’t recognize differences in case, we couldn’t retain the original variable names. We reused the elliptic arithmetic functions add, double and multiply from the previous exercises.
Our ec-factor function is a drop-in replacement for the earlier factors function. An updated version of the function, with improved Pollard rho (the Brent variation) and Pollard p−1 (the two-stage improved standard continuation) functions, is shown on the next page. In this form, complicated factorizations are ten to fifty times faster than the old function.
The complete factors function is shown on the next page and at http://programmingpraxis.codepad.org/SdrzlWbh. Two sample factorizations are shown below:
> (factors (repunit 66))
Trial division: bound=1000
Found factors (3 7 11 11 13 23 37 67)
Remaining co-factor 58993628694531296147719957524688808978821367471004660551
Pollard rho: bound=500000, constant=1
Found factor 4093, remaining co-factor 144132979952434146464011623563862225699
53913381628307
Pollard rho: bound=500000, constant=2
Found non-prime factor 190056571
Trial division: bound=1000
Pollard rho: bound=500000, constant=1
Found factor 21649, remaining co-factor 8779
Factorization complete
Pollard rho: bound=500000, constant=3
Found factor 513239, remaining co-factor 147761341791192537461208953746267179103
Pollard rho: bound=500000, constant=4
Found factor 599144041, remaining co-factor 246620731710144034397913595783
Pollard rho: bound=500000, constant=5
Pollard p-1: b1=100000, b2=5000000
Elliptic curve 1: b1=50000, b2=2500000, s=1325338914
Elliptic curve 2: b1=50000, b2=2500000, s=1196705985
In stage 2, found factor 183411838171, remaining co-factor 1344628210313298373
Factorization complete
(3 7 11 11 13 23 37 67 4093 8779 21649 513239 599144041 183411838171 1344628210313298373)
> (factors (repunit 69))
Trial division: bound=1000
Found factors (3 37 277)
Remaining co-factor 3613722025274371844768956682314083036104696754516249101086646213
Pollard rho: bound=500000, constant=1
Pollard p-1: b1=100000, b2=5000000
Found factor 203864078068831, remaining co-factor 17726134292546940492766254883101518975039516780123
Pollard p-1: b1=100000, b2=5000000
Found factor 11111111111111111111111, remaining co-factor 1595352086329224644348978893
Factorization complete
(3 37 277 203864078068831 11111111111111111111111 1595352086329224644348978893)
