# Quadratic Sieve and NFS factorization in Julia

**URL:** <https://discourse.julialang.org/t/quadratic-sieve-and-nfs-factorization-in-julia/9942>\
**Category:** Numerics\
**Created:** [March 24, 2018, 3:27pm UTC](https://discourse.julialang.org/t/quadratic-sieve-and-nfs-factorization-in-julia/9942 "2018-03-24T15:27:52Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Juan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juan/32/7657_2.png) [@Juan](https://discourse.julialang.org/u/Juan)\
**Post date:** [March 24, 2018, 3:27pm UTC](https://discourse.julialang.org/t/quadratic-sieve-and-nfs-factorization-in-julia/9942/1 "2018-03-24T15:27:52Z")

</div>

Hello.

What’s the most advanced method used in primes.jl to factorize numbers?

I’m looking for implementations of SIQS and NFS in Julia.

I’ve only found this basic one of QS:  
[https://github.com/hamukazu/quadratic\_sieve/blob/master/qs.jl](https://github.com/hamukazu/quadratic_sieve/blob/master/qs.jl)

Do you know about any other, maybe more efficient?

I’m surprised to see that most codes of this kind are written in C or Python, or even Java or Mathematica, but not in Julia, supposedly a fast scientific language.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [March 24, 2018, 4:07pm UTC](https://discourse.julialang.org/t/quadratic-sieve-and-nfs-factorization-in-julia/9942/2 "2018-03-24T16:07:07Z")

</div>

It’s an _open source_ fast scientific language. Algorithm implementations don’t write themselves – if you implement it, it will exist. I’m sure the Primes package would welcome your contributions. Of course if you don’t feel like doing so but need these algorithms, you can call C, Python, Java and Mathematica quite easily.

---

<div class="post-metadata">

**Author:** ![ExpandingMan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/expandingman/32/866_2.png) [@ExpandingMan](https://discourse.julialang.org/u/ExpandingMan)\
**Post date:** [March 24, 2018, 4:36pm UTC](https://discourse.julialang.org/t/quadratic-sieve-and-nfs-factorization-in-julia/9942/3 "2018-03-24T16:36:48Z")

</div>

> [@StefanKarpinski](#):
>
> It’s an open source fast scientific language.

And, perhaps more relevant in this case, a _very young_ fast scientific language, relatively speaking.

I’m unfamiliar with what would be considered a “standard” C library for number theory, but if you are after getting lots of number theoretic functionality up and running in Julia very quickly you might consider picking one and [wrapping](https://docs.julialang.org/en/stable/manual/calling-c-and-fortran-code/) it, or some subset of it. A good example of a C library wrapper in modern Julia can be found [here](https://github.com/JuliaDatabases/ODBC.jl/blob/master/src/API.jl) (only about 800 lines of code for ODBC which I think is pretty good). For what it’s worth, the Python, Java and Mathematica implementations you are referring to are almost undoubtedly wrappers as well. There is no overhead to calling C functions in Julia. Of course ultimately we’d all prefer to have as much functionality as possible available in pure Julia, but part of working in a young language is picking your priorities. The collection of what’s already available in pure Julia is quite impressive for a language that hasn’t even hit 1.0 yet, but obviously we still have some big holes.

---

<div class="post-metadata">

**Author:** ![thofma](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thofma/32/1691_2.png) [@thofma](https://discourse.julialang.org/u/thofma)\
**Post date:** [March 24, 2018, 4:46pm UTC](https://discourse.julialang.org/t/quadratic-sieve-and-nfs-factorization-in-julia/9942/4 "2018-03-24T16:46:16Z")

</div>

What is a scientific language?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [March 24, 2018, 4:48pm UTC](https://discourse.julialang.org/t/quadratic-sieve-and-nfs-factorization-in-julia/9942/5 "2018-03-24T16:48:15Z")

</div>

In this context, presumably a programming language designed with scientific computations in mind.

---

<div class="post-metadata">

**Author:** ![jlapeyre](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jlapeyre/32/4514_2.png) [@jlapeyre](https://discourse.julialang.org/u/jlapeyre)\
**Post date:** [March 24, 2018, 5:58pm UTC](https://discourse.julialang.org/t/quadratic-sieve-and-nfs-factorization-in-julia/9942/6 "2018-03-24T17:58:28Z")

</div>

Here are some more advanced prime number and factoring algorithms. These wrap C libraries.

> **[GitHub - jlapeyre/PrimeSieve.jl: fast generation and counting of primes](https://github.com/jlapeyre/PrimeSieve.jl)**
>
> fast generation and counting of primes. Contribute to jlapeyre/PrimeSieve.jl development by creating an account on GitHub.

This package needs some maintenance in order to be fully functional with recent versions of Julia. But `mfactor` works with v0.6.2  
I don’t recall which algorithms are implemented.