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

**URL:** <https://discourse.julialang.org/t/why-it-is-so-slow-to-factor-bigint-by-primes/31112>\
**Category:** General Usage\
**Tags:** package, nemo\
**Created:** [November 15, 2019, 2:04am UTC](https://discourse.julialang.org/t/why-it-is-so-slow-to-factor-bigint-by-primes/31112 "2019-11-15T02:04:02Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![shenlixing](https://avatars.discourse-cdn.com/v4/letter/s/439d5e/32.png) [@shenlixing](https://discourse.julialang.org/u/shenlixing)\
**Post date:** [November 15, 2019, 2:04am UTC](https://discourse.julialang.org/t/why-it-is-so-slow-to-factor-bigint-by-primes/31112/1 "2019-11-15T02:04:02Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![chrisvwx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisvwx/32/45289_2.png) [@chrisvwx](https://discourse.julialang.org/u/chrisvwx)\
**Post date:** [November 15, 2019, 4:43am UTC](https://discourse.julialang.org/t/why-it-is-so-slow-to-factor-bigint-by-primes/31112/2 "2019-11-15T04:43:47Z")

</div>

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

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

```

---

<div class="post-metadata">

**Author:** ![shenlixing](https://avatars.discourse-cdn.com/v4/letter/s/439d5e/32.png) [@shenlixing](https://discourse.julialang.org/u/shenlixing)\
**Post date:** [November 17, 2019, 6:55am UTC](https://discourse.julialang.org/t/why-it-is-so-slow-to-factor-bigint-by-primes/31112/3 "2019-11-17T06:55:47Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![chrisvwx](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisvwx/32/45289_2.png) [@chrisvwx](https://discourse.julialang.org/u/chrisvwx)\
**Post date:** [November 17, 2019, 8:54pm UTC](https://discourse.julialang.org/t/why-it-is-so-slow-to-factor-bigint-by-primes/31112/4 "2019-11-17T20:54:59Z")

</div>

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](https://github.com/wbhart/Nemo.jl/blob/0a721f194590110e9f8faaabf2b42823a76ed9bc/src/flint/fmpz.jl) function to do factorization.

---

<div class="post-metadata">

**Author:** ![non-Jedi](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/non-jedi/32/3645_2.png) [@non-Jedi](https://discourse.julialang.org/u/non-Jedi)\
**Post date:** [November 17, 2019, 10:31pm UTC](https://discourse.julialang.org/t/why-it-is-so-slow-to-factor-bigint-by-primes/31112/5 "2019-11-17T22:31:59Z")

</div>

Could you post the [quoted](https://discourse.julialang.org/t/psa-make-it-easier-to-help-you/14757) output of running:

```julia
using Pkg
Pkg.build("Nemo")

```

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

---

<div class="post-metadata">

**Author:** ![shenlixing](https://avatars.discourse-cdn.com/v4/letter/s/439d5e/32.png) [@shenlixing](https://discourse.julialang.org/u/shenlixing)\
**Post date:** [November 18, 2019, 9:30am UTC](https://discourse.julialang.org/t/why-it-is-so-slow-to-factor-bigint-by-primes/31112/6 "2019-11-18T09:30:06Z")

</div>

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