As Bill noted, it is known that Pollard Rho does not "perform comparably for all numbers of the same size." Still I got interested in trying it out myself. I wrote a simple implementation and got this result:
julia> n = big(3)^100 + 2 julia> @time factorize(n) elapsed time: 74.539066901 seconds (5360852768 bytes allocated, 23.12% gc time) Dict{BigInt,Int64} with 3 entries: 246451584544723 => 1 31721 => 1 65924521656039679831393… => 1 So I, as Bill would say, "was lucky." Of course, this is not of real use, but I learned some things, and I learned that Julia with BigInt may not yet be ready for number theory applications. On Thursday, March 19, 2015 at 11:26:10 PM UTC+1, lapeyre....@gmail.com wrote: > > Tim is correct in a sense. I translated some big int code a while ago, I > think it was the pollard rho method (don't quite remember the details) and > the inability to reuse storage for a bigint caused a big performance hit. > (I thought about some workaround, but unfortunately I don't remember what > it was or if I even tried it) > > Stefan wrote a simple stop-gap factor() routine and noted in a comment > that it needs to be improved. But Bill Hart is correct: It can't do 3^100 + > 2 no matter how efficient bigint arithmetic is. > > The Maxima routines and the perl module by Dana Jacobsen are good, but > they would require translating and asking the authors to liberalize the > license. > > I wrapped the msieve c library. > > https://github.com/jlapeyre/PrimeSieve.jl > > It does 3^100 + 2 in less than a second on my machine > > On Friday, March 13, 2015 at 6:20:16 PM UTC+1, Hans W Borchers wrote: >> >> I got interested in factorizing some larger integers such as N = 3^100 + >> 2 . >> In all tries, factor(N) did not return and had to be interrupted: >> >> julia> N = big(3)^100 + 2 >> julia> factor(N) >> ^CERROR: interrupt >> in finalizer at ./base.jl:126 >> in + at gmp.jl:243 >> in factor at primes.jl:111 >> >> It is calling GMP, but the GMP software cannot be the reason as this >> works >> with the GMP package in R and returns the factorization within seconds: >> >> R> library(gmp) >> R> N <- bigz(3)^100 >> R> factorize(N) >> Big Integer ('bigz') object of length 3: >> [1] 31721 246451584544723 65924521656039679831393482841 >> R> system.time(factorize(N)) >> user system elapsed >> 3.738 0.000 3.730 >> >> Is this a bug? Did I do something wrong? >> The first factor, 31721, is not even large. Mathematical software such as >> GAP or PARI/GP will factorize this in much less than a second. >> >> PS: Versioninfo >> Julia Version 0.3.6; System: Linux (x86_64-linux-gnu) >> CPU: Intel(R) Core(TM) i3-3217U CPU @ 1.80GHz; WORD_SIZE: 64 >> BLAS: libblas.so.3; LAPACK: liblapack.so.3 >> LIBM: libopenlibm; LLVM: libLLVM-3.3 >> >