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