Skip to content

Instantly share code, notes, and snippets.

@inaz2
Last active September 21, 2023 09:31
Show Gist options
  • Save inaz2/478785979f2de3be66ae7857bc87b7b3 to your computer and use it in GitHub Desktop.
Save inaz2/478785979f2de3be66ae7857bc87b7b3 to your computer and use it in GitHub Desktop.
Pollard-rho algorithm in Haskell/OCaml/F#/Common Lisp/Gauche Scheme/Typed Racket/Erlang
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 22.04.3 LTS
Release: 22.04
Codename: jammy
$ grep "processor\|model name" /proc/cpuinfo
processor : 0
model name : Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
processor : 1
model name : Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
processor : 2
model name : Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
processor : 3
model name : Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
$ python3 --version
Python 3.10.12
$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 9.2.8
$ ocamlopt --version
4.13.1
$ dotnet --version
7.0.110
$ sbcl --version
SBCL 2.1.11.debian
$ gosh -V
Gauche scheme shell, version 0.9.12 [utf-8,pthreads], x86_64-pc-linux-gnu
(version "0.9.12")
(command "gosh")
(scheme.id gauche)
(languages scheme r5rs r7rs)
(encodings utf-8)
(website "https://practical-scheme.net/gauche")
(build.platform "x86_64-pc-linux-gnu")
(build.configure "--prefix=/usr/local" "--enable-multibyte=utf-8")
(scheme.path "/usr/local/share/gauche-0.98/site/lib" "/usr/local/share/gauche-0.98/0.9.12/lib")
(gauche.threads pthreads)
(gauche.net.tls)
$ ./racket/bin/racket --version
Welcome to Racket v8.10 [cs].
$ erl -version
Erlang (SMP,ASYNC_THREADS) (BEAM) emulator version 12.2.1
$ ghc -O2 -o haskell PollardRho.hs
$ ocamlfind ocamlopt -O2 -o ocaml -linkpkg -package zarith Pollard_rho.ml
$ cd fsharp/
$ dotnet publish -c Release
$ cd ..
$ sbcl --script pollard-rho.cl
$ gosh build-standalone -o gauche pollard-rho.scm
$ ./racket/bin/raco exe --orig-exe -o typed-racket pollard-rho.rkt
$ time python3 pollard_rho.py 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949
real 0m14.679s
user 0m14.662s
sys 0m0.009s
$ time ./haskell 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949
real 0m6.300s
user 0m6.286s
sys 0m0.012s
$ time ./ocaml 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949
real 0m5.547s
user 0m5.539s
sys 0m0.005s
$ time ./fsharp/bin/Release/net7.0/publish/fsharp 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949
real 0m14.156s
user 0m14.147s
sys 0m0.037s
$ time ./common-lisp 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949
real 0m38.043s
user 0m37.861s
sys 0m0.141s
$ time ./gauche 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949
real 1m50.042s
user 2m9.899s
sys 0m8.852s
$ time ./typed-racket 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949
real 0m29.163s
user 0m28.976s
sys 0m0.176s
$ time escript pollard_rho.erl 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949
real 0m30.620s
user 0m30.449s
sys 0m0.161s
;; single-line comments
#|
multi-line comments
|#
(declaim (optimize (speed 3) (debug 0) (safety 0)))
(defun pollard-rho (n)
(labels
((g (x)
(mod (+ (* x x) 1) n))
(f (x y d)
(cond
((= d 1) (let* ((x2 (g x))
(y2 (g (g y)))
(d2 (gcd (abs (- x2 y2)) n)))
(f x2 y2 d2)))
((/= d n) d)
(t nil))))
(f 2 2 1)))
(defun main ()
(let* ((args *posix-argv*)
(n (parse-integer (second args)))
(p (pollard-rho n)))
(if p
(format t "~a = ~a * ~a~%" n p (/ n p))
(format t "~a is prime~%" n))))
#|
(main)
|#
(sb-ext:save-lisp-and-die "common-lisp"
:toplevel #'main
:executable t)
#lang typed/racket
;; single-line comments
#|
multi-line comments
|#
(: pollard-rho (-> Integer (Option Integer)))
(define (pollard-rho n)
(: g (-> Integer Integer))
(define (g x)
(modulo (+ (* x x) 1) n))
(: f (-> Integer Integer Integer (Option Integer)))
(define (f x y d)
(cond
((= d 1) (let* ((x2 (g x))
(y2 (g (g y)))
(d2 (gcd (abs (- x2 y2)) n)))
(f x2 y2 d2)))
((not (= d n)) d)
(else #f)))
(f 2 2 1))
(: main (-> Void))
(define (main)
(let* ((args (current-command-line-arguments))
(n (string->number (vector-ref args 0)))
(n (assert n exact-integer?))
(p (pollard-rho n)))
(if p
(printf "~a = ~a * ~a~%" n p (/ n p))
(printf "~a is prime~%" n))))
(main)
;; single-line comments
#|
multi-line comments
|#
(define (pollard-rho n)
(define (g x)
(mod (+ (* x x) 1) n))
(define (f x y d)
(cond
((= d 1) (let* ((x2 (g x))
(y2 (g (g y)))
(d2 (gcd (abs (- x2 y2)) n)))
(f x2 y2 d2)))
((not (= d n)) d)
(else #f)))
(f 2 2 1))
(define (main args)
(let* ((n (string->number (list-ref args 1)))
(p (pollard-rho n)))
(if p
(format #t "~a = ~a * ~a~%" n p (/ n p))
(format #t "~a is prime~%" n)))
0)
#!/usr/bin/env escript
%% -*- erlang -*-
%%! -sname pollard_rho -mnesia debug verbose
-mode(compile).
% single-line comments
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).
g(N, X) -> (X*X + 1) rem N.
f(N, X, Y, 1) ->
X2 = g(N, X),
Y2 = g(N, g(N, Y)),
D2 = gcd(abs(X2 - Y2), N),
f(N, X2, Y2, D2);
f(N, _, _, D) ->
if
D /= N -> D;
true -> []
end.
pollard_rho(N) -> f(N, 2, 2, 1).
main([Arg]) ->
N = list_to_integer(Arg),
P = pollard_rho(N),
if
is_integer(P) -> io:format("~w = ~w * ~w\n", [N, P, N div P]);
true -> io:format("~w is prime\n", [N])
end.
(*
$ sudo apt install libzarith-ocaml-dev
#use "topfind";;
#require "zarith";;
*)
(*
multi-line comments
*)
let pollard_rho n = Z.(
let g x = (x*x + one) mod n in
let rec f x y d =
if d == one then
let x' = g x in
let y' = g (g y) in
let d' = gcd (abs (x' - y')) n in
f x' y' d'
else if d != n then Some(d)
else None in
f ~$2 ~$2 ~$1
)
let () = Z.(
let n = of_string Sys.argv.(1) in
match pollard_rho n with
| Some(p) -> Printf.printf "%a = %a * %a\n" output n output p output (n/p)
| None -> Printf.printf "%a is prime\n" output n
)
import sys
from math import gcd
# single-line comments
"""
multi-line comments
"""
def pollard_rho(n: int) -> int | None:
x, y, d = 2, 2, 1
while d == 1:
x = (x*x + 1) % n
y = (y*y + 1) % n
y = (y*y + 1) % n
d = gcd(abs(x-y), n)
if d != n:
return d
else:
return None
if __name__ == '__main__':
n = int(sys.argv[1])
p = pollard_rho(n)
if p:
print('{} = {} * {}'.format(n, p, n//p))
else:
print('{} is prime'.format(n))
import System.Environment
import Text.Printf
-- single-line comments
{-
multi-line comments
-}
pollardRho n =
f 2 2 1
where
f x y 1 =
let x' = g x
y' = g (g y)
d' = gcd (abs (x' - y')) n in
f x' y' d'
f x y d
| n /= d = Just d
| otherwise = Nothing
g x = (x*x + 1) `mod` n
main = do
args <- getArgs
let n = read (head args) :: Integer
case pollardRho n of
Just p -> printf "%v = %v * %v\n" n p (n `div` p)
Nothing -> printf "%v is prime\n" n
open System.Numerics
// single-line comments
(*
multi-line comments
*)
let pollardRho n =
let inline g x = (x*x + 1I) % n
let rec f x y d =
if d = 1I then
let x' = g x
let y' = g (g y)
let d' = bigint.GreatestCommonDivisor(abs (x' - y'), n)
f x' y' d'
else if d <> n then Some(d)
else None
f 2I 2I 1I
[<EntryPoint>]
let main args =
let n = bigint.Parse(args[0])
match pollardRho n with
| Some(p) -> printfn "%A = %A * %A" n p (n/p)
| None -> printfn "%A is prime" n
0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment