PasteRack.org
Paste # 43426
2014-08-23 08:10:40

Fork as a new paste.

Paste viewed 78 times.


Embed:

RSA factorization

  1. #lang racket
  2. (require math)
  3.  
  4. (define (break-rsa N e d)
  5.   (define (break-rsa-helper N e d k t g)
  6.     (cond
  7.       [(odd? t) (break-rsa-helper N e d k k (random-integer 2 N))]
  8.       (else
  9.        (let ([x (modulo (expt g (/ t 2)) N)])
  10.          (let ([y (gcd (- x 1) N)])
  11.            (cond
  12.              [(and (> x 1) (> y 1)) (cons y (/ N y))]
  13.              (else (break-rsa-helper N e d k (/ t 2) g))))))))
  14.   (let ([k (- (* e d) 1)])
  15.     (break-rsa-helper N e d k k (random-integer 2 N))))
  16.  
  17. (break-rsa 25777 3 16971)
  18.  
  19.  
  20.  

=>

'(149 . 173)