Quadratic Sieve and NFS factorization in Julia


#1

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:

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.


#2

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.


#3

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 it, or some subset of it. A good example of a C library wrapper in modern Julia can be found here (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.


#4

What is a scientific language?


#5

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


#6

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

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.