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 >
