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