fork download
copy 
  1. package main
  2.  
  3. import (
  4.     "fmt"
  5.     "math/big"
  6.     "sort"
  7. )
  8.  
  9. // sort []*big.Int into increasing order, using sort package
  10. type BigIntSlice []*big.Int
  11. func (s BigIntSlice) Len() int           { return len(s) }
  12. func (s BigIntSlice) Less(i, j int) bool { return s[i].Cmp(s[j]) < 0 }
  13. func (s BigIntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
  14. func (s BigIntSlice) Sort()              { sort.Sort(s) }
  15.  
  16. var (
  17.     zero  = big.NewInt(0);
  18.     one   = big.NewInt(1);
  19.     two   = big.NewInt(2);
  20.     four  = big.NewInt(4);
  21.     six   = big.NewInt(6);
  22.     wheel = [11]*big.Int{one,two,two,four,two,four,two,four,six,two,six}
  23. )
  24.  
  25. func factors(n *big.Int) (fs []*big.Int) {
  26.     mod   := new(big.Int) // modulus
  27.     div   := new(big.Int) // dividend
  28.     limit := big.NewInt(1000) // switch to rho
  29.     z     := big.NewInt(0); // temporary storage
  30.     w     := 0 // wheel index
  31.     f     := big.NewInt(2); // trial divisor
  32.     z.Mul(f, f)
  33.     for z.Cmp(n) <= 0 && f.Cmp(limit) <= 0 {
  34.         div.DivMod(n, f, mod)
  35.         for mod.Cmp(zero) == 0 {
  36.             fs = append(fs, new(big.Int).Set(f))
  37.             n.Set(div)
  38.             div.DivMod(n, f, mod)
  39.         }
  40.         f.Add(f, wheel[w]); z.Mul(f, f)
  41.         w += 1; if w == 11 { w = 3 }
  42.     }
  43.     if n.Cmp(one) == 0 { return fs }
  44.     h := big.NewInt(1) // hare
  45.     t := big.NewInt(1) // tortoise
  46.     g := big.NewInt(1) // greatest common divisor
  47.     c := big.NewInt(1) // random number parameter
  48.     for !(n.ProbablyPrime(20)) {
  49.     	for g.Cmp(one) == 0 {
  50.     		z.Mul(h, h); z.Add(z, c); z.Mod(z, n); h.Set(z)
  51.     		z.Mul(h, h); z.Add(z, c); z.Mod(z, n); h.Set(z)
  52.     		z.Mul(t, t); z.Add(z, c); z.Mod(z, n); t.Set(z)
  53.     		z.Sub(t, h); z.Abs(z)
  54.     		g.GCD(nil, nil, z, n)
  55.     	}
  56.     	if g.ProbablyPrime(20) {
  57.             div.DivMod(n, g, mod)
  58.             for mod.Cmp(zero) == 0 {
  59.                 fs = append(fs, new(big.Int).Set(g))
  60.                 n.Set(div)
  61.                 div.DivMod(n, g, mod)
  62.             }
  63.         h.Set(one)
  64.         t.Set(one)
  65.         g.Set(one)
  66.         c.Add(c, one)
  67.     	}
  68.     }
  69.     fs = append(fs, new(big.Int).Set(n))
  70.     sort.Sort(BigIntSlice(fs))
  71.     return fs
  72. }
  73.  
  74. func main() {
  75. 	fmt.Println(factors(big.NewInt(13290059)))
  76. 	x := big.NewInt(583910384809)
  77. 	y := big.NewInt(291648291013)
  78. 	x.Mul(x,y)
  79. 	fmt.Println(x)
  80. 	fmt.Println(factors(x))
  81. }
Success #stdin #stdout 4.48s 790016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[3119 4261]
170296465834288046421517
[291648291013 583910384809]
https://ideone.com/fXvo2R
language:
Go (go 1.12.1)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!