[ create a new paste ] login | about

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

programmingpraxis - Scheme, pasted on Mar 17:
; extending pollard’s p-1 factorization algorithm

(define (expm b e m)
  (define (m* x y) (modulo (* x y) m))
  (cond ((zero? e) 1)
        ((even? e) (expm (m* b b) (/ e 2) m))
        (else (m* b (expm (m* b b) (/ (- e 1) 2) m)))))

(define (pollard1 n b1)
  (let stage1 ((a 2) (i 2))
    (if (< i b1)
        (stage1 (expm a i n) (+ i 1))
        (let ((d (gcd (- a 1) n)))
          (if (< 1 d n) d #f)))))

(define (pollard2 n b1 b2)
  (let stage1 ((a 2) (i 2))
    (if (< i b1)
        (stage1 (expm a i n) (+ i 1))
        (let ((d (gcd (- a 1) n)))
          (if (< 1 d n) (list 'stage1 d)
            (let stage2 ((j b1))
              (if (= j b2) #f
                (let ((d (gcd (- (expm a j n) 1) n)))
                  (if (< 1 d n) (list 'stage2 d)
                    (stage2 (+ j 1)))))))))))

(display (pollard1 15770708441 150)) (newline)
(display (pollard1 15770708441 180)) (newline)
(display (pollard2 15770708441 150 180)) (newline)


Output:
1
2
3
#f
135979
(stage2 135979)


Create a new paste based on this one


Comments: