Why it is so slow to factor(BigInt) by Primes?

General Usage
,
1

I add Primes into Julia today , it works well.
But a little surprise, when factor(12346871234523845243095830496798990897706789), it takes 89 seconds, much longer than SageMath ( less than 1 second).

I guess that Primes using GMP to factor BigInt, it should not be so slow as tested.
What’s the reason?

2

Try the following and let us know how it compares with Sage:

Pkg.add("Nemo")
using Nemo
@elapsed factor(fmpz(12346871234523845243095830496798990897706789))
# about 0.17 sec on my computer
7 Likes
3

Thanks.
I tried to using Nemo, but

julia> using Nemo
ERROR: InitError: error compiling init: could not load library “C:\Users\Adm
inistrator.julia\packages\Nemo\qzx0m\deps\usr\bin\libflint”
The specified module could not be found.

Anyway, I believe that Nemo is a good package.

4

I don’t have any direct suggestions for your Nemo.jl problem; have you used other packages which use binary libraries? For example if you add Cxx.jl, and then try “using Cxx”, do you get a similar error?

To your original question of why Prime.jl’s factor function is slow, I guess that the answer is that no one has taken the time to put the fastest factorization tools into Primes.jl. The Nemo guys are number theorists, so it makes sense that they’d have a fast factorization technique in their package. BTW, it looks to me like Nemo calls a flint function to do factorization.

1 Like
5

Could you post the quoted output of running:

using Pkg
Pkg.build("Nemo")

This might be a bug that should be filed against the package.

2 Likes
6

Thanks for your kind suggestion.
After test , I found It’s windows 7 made the trouble. Nemo is wonderful ! :smiley:

1 Like