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, [email protected]
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
>>
>
