0
$\begingroup$

Recently, I have taken upon myself the task of writing an algorithm to compute the prime factorization of an integer. I am neither a mathematician nor a programmer/computers' engineer as an occupation, and I do math merely as a hobby and because I like it very much. Nonetheless, I am pretty good at math, and I know number theory to a decent degree. I can code in Java so Eclipse is my chosen IDE. I will start a little bit far, but it is essential, so I apologize in advance for a long read.

The algorithm I've written is not based on the General Number Field Sieve, but rather on efficient implementations of the Miller-Rabin primality test, and the sieve of Atkin. Although the MR test does have a complexity of its own, you will understand it's not the obstacle of this prime factorization algorithm. Hence we'll assume the complexity of my algorithm is that of sieve of Atkin:

$$O (N\cdot \sqrt{log\,log\,N})$$

The MR test is instant even for numbers with over 100 digits, but is only deterministic up to $3.317\cdot10^{24} $, or around $2^{81}$. It is based on ideas in the following links:

https://miller-rabin.appspot.com/ https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

The sieving method itself is also efficient, capable of returning a list of all primes up to $1,000,000,000 = 10^9$ in just about $8$ seconds, or $100,000,000 = 10^8$ instantly. The sieving algorithm does not depend on the MR test, and is completely independent.

From here on, the algorithm first checks if the number is prime with the MR test. If not, it tries to find the prime factors of the given integer in the sieve (of Atkin). The sieve contains all the prime numbers up to $\sqrt{n}$. Although a number $n$ may have prime factors $p>\sqrt{n}$, for example $21=7\cdot3$, it is still only necessary to check for primes that are smaller than that, because $n$ will have at most one prime factor $p>\sqrt{n}$, and once we've devided $n$ by all its prime factors $p<\sqrt{n}$, then what we'll be left with is either $1$, if all its prime factors are smaller than $\sqrt{n}$, or a new prime $p>\sqrt{n}$. This is important, because here is where my algorithm reaches a dead-end. This is due to the fact that my algorithm is memory-dependent. Numbers whose prime factors are large are both time and space consuming. One way to pass that is to first create a very small prime sieve, say up to $\sqrt[4]{n}$, and divide $n$ by all its prime factors that are within this limit. Then to create another primes sieve up to $\sqrt{c}$, which is whatever number we're left with after the division. However, when dealing with numbers whose prime factors are lurking around $\sqrt n$ (as in semiprimes in RSA-Encryption), creating a sieve of primes up to the square root of the original number is inevitable in my algorithm. This also imposes an "upper bound" to the integers I am able to factorize. All $n < 2^{63}$, approximately, (a little less due to memory usage), can be factorized. Above that, it depends on the magnitude of the prime factors of the number. Numbers with prime factors larger than $2^{31}$ just cannot be computed, because of the memory usage. However, huge numbers, even $n>10^{25}$, with "relatively" small prime factors will be factored exceptionally fast, even if some of their prime factors are large.

Now, I am not saying my algorithm is the best, or can't be optimized any further, but I am quite proud of it. Calling the method with an input of a number, say $n=9,222,495,785,442,405,189$ or $n=7,492,495,785,434,405,183$ for example, it returns the following results, respectively, instantly. The method returns a 2D array of 2 lines, the first addresses the prime factors of the number, and the second line the corresponding exponents of these factors:


[3, 1307, 784025825507303]

[2, 1, 1]

Solution took 9 ms


[5981, 58153, 21541730131]

[1, 1, 1]

Solution took 103 ms


Nonetheless, this algorithm addresses 2 difficulties:

  1. Memory usage becomes an issue
  2. Even if memory usage was not a problem, my algorithm can factorize integers effectively (by effectively I mean in a matter of milliseconds up to about a second) up to a certain limit, around $10^{20}$. Beyond that it may just take too much time if the prime factors aren't relatively small

Obviously, I could just check all the primes up to $\sqrt n$ with a MR test rather than a sieve, and eventually find the prime factorization but this method is extremely inefficient, and therefore will be disregarded.

I have known about the General Number Field Sieve (GNFS) for a long time now, but facing these problems in my little project encouraged me to once again look into it, as I know that exactly beyond this limit of $n=10^{20}$ is where the more sophisticated integer factoring algorithms start to shine, such as the GNFS, Lenstra elliptic curves, SNFS, Quadratic sieve and more. The complexity of the GNFS also seems to be better than mine, and is as follows:

$$ e^{(\sqrt[3]{\frac {64}{9}}+o(1))\cdot(ln\,n)^{\frac13}\cdot (ln\,ln\,n)^{\frac23}}$$

And since to my understanding it does not consume so much memory, and is not bounded by any limit, it is therefore more general and addresses the 2 issues that I mentioned. By no means an easy task to write an algorithm for it, I still decided to try it. It is a very challenging task, which also appeals to me. Delving into it, I started with the wiki entry, obviously: https://en.wikipedia.org/wiki/General_number_field_sieve. But even exploring additional sources was of no use. I could not "translate" the math into an algorithm. I couldn't find examples how it works either. The wiki entry, at the bottom of it, does contain links to varius implementations of the GNFS, but non of which are in Java. Hence I cannot translate them either.


What I really want is an implementation of the algorithm of the GNFS written in Java, if you know of any, which when given an integer, returns an array of the prime factorization of the number in a form similiar to the one my method returns, so that I can follow it and actually implement it myself while understanding it too. Even some sort of a translation of the given C/C++/C# implementations in the wiki page to JAVA will be excellent. A good example which I can "translate" to an algorithm will also be great, and so is a way of perhaps "transforming" my algorithm, in a way, to the GNFS - if it's possible.

Thank you very much in advance for reading it,

Matan.

$\endgroup$
  • $\begingroup$ Are you looking for a Java program? This doesn't seem to be the right site for this. $\endgroup$ – Don Thousand Apr 22 at 18:20
  • $\begingroup$ It is what I prefer the most, but I am not sure it exists, so my thought was that if I post it here, I might get "something". Do you think it would be more suitable to post on the "Stackoverflow" variant? @DonThousand $\endgroup$ – Matan Apr 22 at 18:23
  • 5
    $\begingroup$ I'm going to be blunt: you're going the wrong way about this. I can assure you that an implementation of the GNFS will give you approximately 0 enlightenment as to how it works or how to write your own implementation. At best you will be able to copy the algorithm verbatim modulo insignificant changes. The general number field sieve is not simple. The math and ideas behind it are not simple. But most importantly, the algorithm stands atop an entire field of knowledge. Without this knowledge it's impossible to decipher how the algorithm works and it might as well be black magic. $\endgroup$ – orlp Apr 22 at 18:35
  • 1
    $\begingroup$ projecteuclid.org/download/pdf_1/euclid.em/1047915103 and github.com/radii/msieve and kmgnfs.cti.gr/kmGNFS/Home.html and link.springer.com/chapter/10.1007/BFb0091541 and citeseerx.ist.psu.edu/viewdoc/… all discuss and/or present implementations. Please have a look, see whether anything looks like what you need. $\endgroup$ – Gerry Myerson Apr 23 at 3:32
  • 1
    $\begingroup$ 1 of them is pretty good as to what's the math behind the GNFS. Very good even. But I don't know how to implement it. Some of the theories are clear on paper but not very straightforward to compute. @GerryMyerson $\endgroup$ – Matan Apr 25 at 13:02
1
$\begingroup$

Here are some more references on the (General) Number Field Sieve. I don't know whether any of them will give you enough detail to put together an implementation. I also haven't checked whether they are available on the web, or whether you need to go to a library instead.

Sam Wagstaff's book, The Joy of Factoring, has a chapter on it. He recommends Lenstra & Lenstra, eds., The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554 for the early history of the algorithm. Also, Pomerance, The number field sieve, Proc Sympos Appl Math 48 (1994) 465-480 for an excellent summary of the algorithm. Also, Crandall & Pomerance, Prime Numbers, Springer 2005 for a thorough description of the modern algorithm.

Wagstaff also mentions Montgomery & Murphy, Improved polynomial selection for the number field sieve, in the book, The Mathematics of Public Key Cryptography Conference, Fields Institute 1999.

The Crandall-Pomerance book may be your best bet. They have over 20 pages on the sieve, including a presentation as an algorithm (but not as computer code).

$\endgroup$
  • $\begingroup$ Thank you very much. I really appreciate it. I will look into them, starting with the Crandall-Pomerance book. Thanks! $\endgroup$ – Matan Apr 26 at 12:16
  • $\begingroup$ You have the option of "accepting" an answer by clicking in the check-mark next to it. $\endgroup$ – Gerry Myerson Apr 30 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.