Project:
 ```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 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 ``` ```; modern elliptic curve factorization, part 1 (define (digits n . args) (let ((b (if (null? args) 10 (car args)))) (let loop ((n n) (d '())) (if (zero? n) d (loop (quotient n b) (cons (modulo n b) d)))))) (define (add P1 P2 P0 N) (define (square n) (* n n)) (let* ((x0 (car P0)) (x1 (car P1)) (x2 (car P2)) (z0 (cdr P0)) (z1 (cdr P1)) (z2 (cdr P2)) (t1 (modulo (* (+ x1 z1) (- x2 z2)) n)) (t2 (modulo (* (- x1 z1) (+ x2 z2)) n))) (cons (modulo (* (square (+ t2 t1)) z0) n) (modulo (* (square (- t2 t1)) x0) n)))) (define (double P An Ad N) (define (square n) (* n n)) (let* ((x (car P)) (z (cdr P)) (t1 (modulo (square (+ x z)) N)) (t2 (modulo (square (- x z)) N)) (t3 (- t1 t2))) (cons (modulo (* t1 t2 4 Ad) N) (modulo (* (+ (* t3 An) (* t2 Ad 4)) t3) N)))) (define (multiply K P An Ad N) (cond ((zero? K) (cons 0 0)) ((= K 1) P) ((= K 2) (double P An Ad N)) (else (let loop ((ks (cdr (digits K 2))) (Q (double P An Ad N)) (R P)) (cond ((null? ks) R) ((odd? (car ks)) (loop (cdr ks) (double Q An Ad N) (add Q R P N))) (else (loop (cdr ks) (add R Q P N) (double R An Ad N)))))))) (define (curve12 N s) (let* ((u (modulo (- (* s s) 5) N)) (v (modulo (* 4 s) N)) (v-u (- v u))) (values (modulo (* (* v-u v-u v-u) (+ u u u v)) N) (modulo (* 4 u u u v) N) (cons (modulo (* u u u) N) (modulo (* v v v) N))))) (define n 5569379) (define s 4921134) (define An #f) (define Ad #f) (define P #f) (call-with-values (lambda () (curve12 n s)) (lambda (a b c) (set! An a) (set! Ad b) (set! P c))) (display "An: ") (display An) (newline) (display "Ad: ") (display Ad) (newline) (display "P: ") (display P) (newline) (define P2 (double P An Ad n)) (display "P2: ") (display P2) (newline) (define P3 (add P2 P P n)) (display "P3: ") (display P3) (newline) (define P4 (double P2 An Ad n)) (display "P4: ") (display P4) (newline) (define P6 (double P3 An Ad n)) (display "P6: ") (display P6) (newline) (define P7 (add P4 P3 P n)) (display "P7: ") (display P7) (newline) (define P13 (add P7 P6 P n)) (display "P13: ") (display P13) (newline) (display "P13: ") (display (multiply 13 P An Ad n)) (newline) ```
 ```1 2 3 4 5 6 7 8 9 10 ``` ```An: 3660795 Ad: 1539615 P: (4087911 . 2770287) P2: (3539269 . 4477480) P3: (2517168 . 4993956) P4: (4683984 . 2280932) P6: (3440206 . 1480034) P7: (2544042 . 2445346) P13: (577485 . 4434222) P13: (577485 . 4434222) ```