Pollard-rho algorithm in Golang and math/big

gistfile1.txt

$ go version
go version go1.21.0 linux/amd64

$ go build -ldflags="-s -w" -trimpath pollardRho.go

$ time ./pollardRho 12814570762777948741
12814570762777948741 = 3861801803 * 3318288047

real	0m0.160s
user	0m0.060s
sys	0m0.103s

$ time ./pollardRho 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m26.342s
user	0m24.501s
sys	0m2.392s


$ python3 --version
Python 3.10.12

$ time python3 pollard_rho.py 12814570762777948741
12814570762777948741 = 3861801803 * 3318288047

real	0m0.119s
user	0m0.102s
sys	0m0.016s

$ time python3 pollard_rho.py 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m15.385s
user	0m15.365s
sys	0m0.013s

pollard_rho.py

import sys
from random import randint
from math import gcd

def miller_rabin(n, k=20):
    s, d = 0, n-1

    while d % 2 == 0:
        s += 1
        d //= 2

    for i in range(k):
        a = randint(2, n-1)
        x = pow(a, d, n)
        if x == 1:
            continue
        for r in range(s):
            if x == n-1:
                break
            x = (x*x) % n
        else:
            return False

    return True

def pollard_rho(n):
    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

if __name__ == '__main__':
    n = int(sys.argv[1])
    is_prime = miller_rabin(n)
    if is_prime:
        print('{} is prime'.format(n))
    else:
        p = pollard_rho(n)
        if p:
            print('{} = {} * {}'.format(n, p, n//p))
        else:
            print('{} is prime'.format(n))

pollardRho.go

package main

import (
    "fmt"
    "os"
    "math/big"
)

func pollardRho(n *big.Int) (*big.Int, bool) {
    x := big.NewInt(2)
    y := big.NewInt(2)
    d := big.NewInt(1)

    one := big.NewInt(1)
    for d.Cmp(one) == 0 {
        x.Mul(x, x); x.Add(x, one); x.Mod(x, n)
        y.Mul(y, y); y.Add(y, one); y.Mod(y, n)
        y.Mul(y, y); y.Add(y, one); y.Mod(y, n)
        d.Sub(x, y); d.Abs(d); d.GCD(nil, nil, d, n)
    }

    if d.Cmp(n) != 0 {
        return d, true
    } else {
        return nil, false
    }
}

func main() {
    if len(os.Args) < 2 {
        fmt.Printf("Usage: %v N\n", os.Args[0])
        os.Exit(1)
    }
    n := new(big.Int)
    if _, ok := n.SetString(os.Args[1], 0); !ok {
        fmt.Printf("Error: \"%v\" is not valid format. Supported prefixes are \"0b\", \"0o\", \"0x\".\n", os.Args[1])
        os.Exit(1)
    }

    if n.ProbablyPrime(20) {
        fmt.Printf("%v is prime\n", n)
    } else {
        p, ok := pollardRho(n)
        if ok {
            q := new(big.Int).Div(n, p)
            fmt.Printf("%v = %v * %v\n", n, p, q)
        } else {
            fmt.Printf("%v is prime\n", n)
        }
    }
}