package main

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

// sort []*big.Int into increasing order, using sort package
type BigIntSlice []*big.Int
func (s BigIntSlice) Len() int           { return len(s) }
func (s BigIntSlice) Less(i, j int) bool { return s[i].Cmp(s[j]) < 0 }
func (s BigIntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s BigIntSlice) Sort()              { sort.Sort(s) }

var (
    zero  = big.NewInt(0);
    one   = big.NewInt(1);
    two   = big.NewInt(2);
    four  = big.NewInt(4);
    six   = big.NewInt(6);
    wheel = [11]*big.Int{one,two,two,four,two,four,two,four,six,two,six}
)

func factors(n *big.Int) (fs []*big.Int) {
    mod   := new(big.Int) // modulus
    div   := new(big.Int) // dividend
    limit := big.NewInt(1000) // switch to rho
    z     := big.NewInt(0); // temporary storage
    w     := 0 // wheel index
    f     := big.NewInt(2); // trial divisor
    z.Mul(f, f)
    for z.Cmp(n) <= 0 && f.Cmp(limit) <= 0 {
        div.DivMod(n, f, mod)
        for mod.Cmp(zero) == 0 {
            fs = append(fs, new(big.Int).Set(f))
            n.Set(div)
            div.DivMod(n, f, mod)
        }
        f.Add(f, wheel[w]); z.Mul(f, f)
        w += 1; if w == 11 { w = 3 }
    }
    if n.Cmp(one) == 0 { return fs }
    h := big.NewInt(1) // hare
    t := big.NewInt(1) // tortoise
    g := big.NewInt(1) // greatest common divisor
    c := big.NewInt(1) // random number parameter
    for !(n.ProbablyPrime(20)) {
    	for g.Cmp(one) == 0 {
    		z.Mul(h, h); z.Add(z, c); z.Mod(z, n); h.Set(z)
    		z.Mul(h, h); z.Add(z, c); z.Mod(z, n); h.Set(z)
    		z.Mul(t, t); z.Add(z, c); z.Mod(z, n); t.Set(z)
    		z.Sub(t, h); z.Abs(z)
    		g.GCD(nil, nil, z, n)
    	}
    	if g.ProbablyPrime(20) {
            div.DivMod(n, g, mod)
            for mod.Cmp(zero) == 0 {
                fs = append(fs, new(big.Int).Set(g))
                n.Set(div)
                div.DivMod(n, g, mod)
            }
        h.Set(one)
        t.Set(one)
        g.Set(one)
        c.Add(c, one)
    	}
    }
    fs = append(fs, new(big.Int).Set(n))
    sort.Sort(BigIntSlice(fs))
    return fs
}

func main() {
	fmt.Println(factors(big.NewInt(13290059)))
	x := big.NewInt(583910384809)
	y := big.NewInt(291648291013)
	x.Mul(x,y)
	fmt.Println(x)
	fmt.Println(factors(x))
}