codepad | about

 Link:

Scheme, pasted on Mar 25:
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 ``` ```; 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))) ```

Output:
 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ``` ```2 50912 2 25456 2 12728 2 6364 2 3182 2 1591 3 50912 3 25456 3 12728 3 6364 3 3182 3 1591 5 50912 5 25456 5 12728 5 6364 149 173 2 3912086784511471289561151952301925086168946454709316095960618800742799369173365724802767882894790378640224771497700744632822349777243736269522672978216650880 2 1956043392255735644780575976150962543084473227354658047980309400371399684586682862401383941447395189320112385748850372316411174888621868134761336489108325440 2 978021696127867822390287988075481271542236613677329023990154700185699842293341431200691970723697594660056192874425186158205587444310934067380668244554162720 2 489010848063933911195143994037740635771118306838664511995077350092849921146670715600345985361848797330028096437212593079102793722155467033690334122277081360 23234950162188993388155927630085331316851060055334470382368804331834850828939 23443439767333138692938389505422341860387525814723848738690073331642118819681 ```

Comments: