[ create a new paste ] login | about

Project: programmingpraxis
Link: http://programmingpraxis.codepad.org/t9gygODg    [ raw code | output | fork ]

programmingpraxis - Scheme, pasted on Apr 20:
; 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)


Output:
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)


Create a new paste based on this one


Comments: