; extending pollard’s p-1 factorization algorithm
(define (expm b e m)
(define (m* x y) (modulo (* x y) m))
(cond ((zero? e) 1)
((even? e) (expm (m* b b) (/ e 2) m))
(else (m* b (expm (m* b b) (/ (- e 1) 2) m)))))
(define (pollard1 n b1)
(let stage1 ((a 2) (i 2))
(if (< i b1)
(stage1 (expm a i n) (+ i 1))
(let ((d (gcd (- a 1) n)))
(if (< 1 d n) d #f)))))
(define (pollard2 n b1 b2)
(let stage1 ((a 2) (i 2))
(if (< i b1)
(stage1 (expm a i n) (+ i 1))
(let ((d (gcd (- a 1) n)))
(if (< 1 d n) (list 'stage1 d)
(let stage2 ((j b1))
(if (= j b2) #f
(let ((d (gcd (- (expm a j n) 1) n)))
(if (< 1 d n) (list 'stage2 d)
(stage2 (+ j 1)))))))))))
(display (pollard1 15770708441 150)) (newline)
(display (pollard1 15770708441 180)) (newline)
(display (pollard2 15770708441 150 180)) (newline)