#lang racket
(require math)

(define (break-rsa N e d)
  (define (break-rsa-helper N e d k t g)
    (cond
      [(odd? t) (break-rsa-helper N e d k k (random-integer 2 N))]
      (else 
       (let ([x (modulo (expt g (/ t 2)) N)])
         (let ([y (gcd (- x 1) N)])
           (cond
             [(and (> x 1) (> y 1)) (cons y (/ N y))]
             (else (break-rsa-helper N e d k (/ t 2) g))))))))
  (let ([k (- (* e d) 1)])
    (break-rsa-helper N e d k k (random-integer 2 N))))

(break-rsa 25777 3 16971)