; factoring rsa moduli
(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 primes
(let ((sieve (make-vector 1001 #t)) (ps (list)))
(do ((p 2 (+ p 1))) ((< 1000 p) (reverse ps))
(when (vector-ref sieve p)
(set! ps (cons p ps))
(do ((i (* p p) (+ i p))) ((< 1000 i))
(vector-set! sieve i #f))))))
(define (next-prime n) (cadr (member n primes)))
(define (rsa-factors n e d)
(let ((k (- (* d e) 1)))
(let loop ((g 2) (t k))
(when verbose?
(display g) (display " ")
(display t) (newline))
(if (positive? (modulo t 2))
(loop (next-prime g) k)
(let* ((t (/ t 2))
(x (expm g t n))
(y (gcd (- x 1) n)))
(if (and (< 1 x) (< 1 y))
(values y (/ n y))
(loop g t)))))))
(define verbose? #t)
(call-with-values
(lambda () (rsa-factors 25777 3 16971))
(lambda (p q) (display p) (newline)
(display q) (newline)))
(newline)
(define n #xa66791dc6988168de7ab77419bb7fb0c001c62710270075142942e19a8d8c51d053b3e3782a1de5dc5af4ebe99468170114a1dfe67cdc9a9af55d655620bbab)
(define e #x10001)
(define d #x123c5b61ba36edb1d3679904199a89ea80c09b9122e1400c09adcf7784676d01d23356a7d44d6bd8bd50e94bfc723fa87d8862b75177691c11d757692df8881)
(call-with-values
(lambda () (rsa-factors n e d))
(lambda (p q) (display p) (newline)
(display q) (newline)))