codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
; 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)
Private
[
?
]
Run code
Submit