Skip to content

Instantly share code, notes, and snippets.

@inaz2

inaz2/pollardRho.go

Last active September 18, 2023 12:08
Show Gist options
  • Save inaz2/df13aaa38c4f4d685d1de86a54799891 to your computer and use it in GitHub Desktop.
Save inaz2/df13aaa38c4f4d685d1de86a54799891 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. inaz2 revised this gist Sep 18, 2023. 2 changed files with 16 additions and 13 deletions.
    24 changes: 12 additions & 12 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -6,16 +6,16 @@ $ go build -ldflags="-s -w" -trimpath pollardRho.go
    $ time ./pollardRho 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047

    real 0m0.067s
    user 0m0.065s
    sys 0m0.005s
    real 0m0.160s
    user 0m0.060s
    sys 0m0.103s

    $ time ./pollardRho 60766145992321225002169406923
    60766145992321225002169406923 = 250117558771727 * 242950340194949

    real 0m27.209s
    user 0m26.874s
    sys 0m1.468s
    real 0m26.342s
    user 0m24.501s
    sys 0m2.392s


    $ python3 --version
    @@ -24,13 +24,13 @@ Python 3.10.12
    $ time python3 pollard_rho.py 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047

    real 0m0.152s
    user 0m0.138s
    sys 0m0.014s
    real 0m0.119s
    user 0m0.102s
    sys 0m0.016s

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

    real 0m14.642s
    user 0m14.641s
    sys 0m0.005s
    real 0m15.385s
    user 0m15.365s
    sys 0m0.013s
    5 changes: 4 additions & 1 deletion pollard_rho.py
    View file
    Original file line number Diff line number Diff line change
    @@ -42,4 +42,7 @@ def pollard_rho(n):
    print('{} is prime'.format(n))
    else:
    p = pollard_rho(n)
    print('{} = {} * {}'.format(n, p, n//p))
    if p:
    print('{} = {} * {}'.format(n, p, n//p))
    else:
    print('{} is prime'.format(n))
  2. inaz2 revised this gist Sep 18, 2023. 2 changed files with 5 additions and 3 deletions.
    2 changes: 2 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -5,12 +5,14 @@ $ go build -ldflags="-s -w" -trimpath pollardRho.go

    $ time ./pollardRho 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047

    real 0m0.067s
    user 0m0.065s
    sys 0m0.005s

    $ time ./pollardRho 60766145992321225002169406923
    60766145992321225002169406923 = 250117558771727 * 242950340194949

    real 0m27.209s
    user 0m26.874s
    sys 0m1.468s
    6 changes: 3 additions & 3 deletions pollardRho.go
    View file
    Original file line number Diff line number Diff line change
    @@ -38,14 +38,14 @@ func main() {
    }

    if n.ProbablyPrime(20) {
    fmt.Printf("%v is prime", n)
    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, p, q)
    fmt.Printf("%v = %v * %v\n", n, p, q)
    } else {
    fmt.Printf("%v is prime", n)
    fmt.Printf("%v is prime\n", n)
    }
    }
    }
  3. inaz2 revised this gist Aug 17, 2023. 1 changed file with 5 additions and 5 deletions.
    10 changes: 5 additions & 5 deletions pollardRho.go
    View file
    Original file line number Diff line number Diff line change
    @@ -19,11 +19,11 @@ func pollardRho(n *big.Int) (*big.Int, bool) {
    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
    }
    if d.Cmp(n) != 0 {
    return d, true
    } else {
    return nil, false
    }
    }

    func main() {
  4. inaz2 revised this gist Aug 17, 2023. 2 changed files with 24 additions and 22 deletions.
    28 changes: 14 additions & 14 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -1,34 +1,34 @@
    $ go version
    go version go1.20.3 linux/amd64
    go version go1.21.0 linux/amd64

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

    $ time ./pollardRho 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047
    real 0m0.032s
    user 0m0.024s
    real 0m0.067s
    user 0m0.065s
    sys 0m0.005s

    $ time ./pollardRho 60766145992321225002169406923
    60766145992321225002169406923 = 250117558771727 * 242950340194949
    real 0m17.733s
    user 0m17.745s
    sys 0m0.337s
    real 0m27.209s
    user 0m26.874s
    sys 0m1.468s


    $ python3 --version
    Python 3.10.6
    Python 3.10.12

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

    real 0m0.073s
    user 0m0.061s
    sys 0m0.004s
    real 0m0.152s
    user 0m0.138s
    sys 0m0.014s

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

    real 0m16.712s
    user 0m16.671s
    sys 0m0.008s
    real 0m14.642s
    user 0m14.641s
    sys 0m0.005s
    18 changes: 10 additions & 8 deletions pollardRho.go
    View file
    Original file line number Diff line number Diff line change
    @@ -6,21 +6,24 @@ import (
    "math/big"
    )

    func pollardRho(z *big.Int, n *big.Int) bool {
    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.IsInt64() && d.Int64() == 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.Set(x); d.Sub(d, y); d.Abs(d); d.GCD(nil, nil, d, n)
    d.Sub(x, y); d.Abs(d); d.GCD(nil, nil, d, n)
    }

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

    func main() {
    @@ -37,9 +40,8 @@ func main() {
    if n.ProbablyPrime(20) {
    fmt.Printf("%v is prime", n)
    } else {
    p := new(big.Int)
    isPrime := pollardRho(p, n)
    if !isPrime {
    p, ok := pollardRho(n)
    if ok {
    q := new(big.Int).Div(n, p)
    fmt.Printf("%v = %v * %v", n, p, q)
    } else {
  5. inaz2 revised this gist Apr 15, 2023. 2 changed files with 56 additions and 11 deletions.
    22 changes: 11 additions & 11 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -5,15 +5,15 @@ $ go build -ldflags="-s -w" -trimpath pollardRho.go

    $ time ./pollardRho 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047
    real 0m0.028s
    user 0m0.028s
    sys 0m0.000s
    real 0m0.032s
    user 0m0.024s
    sys 0m0.005s

    $ time ./pollardRho 60766145992321225002169406923
    60766145992321225002169406923 = 250117558771727 * 242950340194949
    real 0m17.816s
    user 0m17.834s
    sys 0m0.340s
    real 0m17.733s
    user 0m17.745s
    sys 0m0.337s


    $ python3 --version
    @@ -22,13 +22,13 @@ Python 3.10.6
    $ time python3 pollard_rho.py 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047

    real 0m0.074s
    user 0m0.054s
    sys 0m0.012s
    real 0m0.073s
    user 0m0.061s
    sys 0m0.004s

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

    real 0m16.749s
    user 0m16.705s
    real 0m16.712s
    user 0m16.671s
    sys 0m0.008s
    45 changes: 45 additions & 0 deletions pollard_rho.py
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,45 @@
    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)
    print('{} = {} * {}'.format(n, p, n//p))
  6. inaz2 created this gist Apr 15, 2023.
    34 changes: 34 additions & 0 deletions gistfile1.txt
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,34 @@
    $ go version
    go version go1.20.3 linux/amd64

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

    $ time ./pollardRho 12814570762777948741
    12814570762777948741 = 3861801803 * 3318288047
    real 0m0.028s
    user 0m0.028s
    sys 0m0.000s

    $ time ./pollardRho 60766145992321225002169406923
    60766145992321225002169406923 = 250117558771727 * 242950340194949
    real 0m17.816s
    user 0m17.834s
    sys 0m0.340s


    $ python3 --version
    Python 3.10.6

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

    real 0m0.074s
    user 0m0.054s
    sys 0m0.012s

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

    real 0m16.749s
    user 0m16.705s
    sys 0m0.008s
    49 changes: 49 additions & 0 deletions pollardRho.go
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,49 @@
    package main

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

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

    one := big.NewInt(1)
    for d.IsInt64() && d.Int64() == 1 {
    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.Set(x); d.Sub(d, y); d.Abs(d); d.GCD(nil, nil, d, n)
    }

    z.Set(d)
    return d.Cmp(n) == 0
    }

    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)
    } else {
    p := new(big.Int)
    isPrime := pollardRho(p, n)
    if !isPrime {
    q := new(big.Int).Div(n, p)
    fmt.Printf("%v = %v * %v", n, p, q)
    } else {
    fmt.Printf("%v is prime", n)
    }
    }
    }