Prime Factorization

Generic algorithms that could be implemented in almost any language, e.g. matrix operations and FFT.

Re: Prime Factorization

Postby over9000 » Tue Jun 24, 2014 8:51 pm

webmasterpdx wrote:I think having the same thing for floating point could be very useful too, so that we could calculate pi to a large number of places......beat the record.... :lol:

Have you looked at Fabrice Bellard's notes on how he beat the record? It's a very good read. The problem he mentions is that the problem is really more I/O bound than compute-bound when you get to that many digits.
Posts: 98
Joined: Tue Aug 06, 2013 1:49 am

Re: Prime Factorization

Postby doddy1985 » Fri Jun 27, 2014 6:46 pm

Maybe if I/O is a bigger issue, it might be worth implementing something into the FPGA fabric..
Posts: 15
Joined: Tue Oct 08, 2013 4:38 pm

Re: Prime Factorization

Postby bgb » Wed Nov 04, 2015 2:54 pm

Since the Epiphany cores do not have a divide instruction, using them for any factoring is going to be tricky.
I do not know enough about the current best factoring algorithms (Quadratic Sieve, Multiple Polynomial QS,
and Number Field Sieve) to know if they could use the epiphany or not.

Here is what I have been looking at. First Knuth Volume 2 Section 4.5.4 Algorithm D (page 373 in the 2nd Edition)
is the "Factoring with Sieves" method. It is a very interesting algorithm because after initialization, it can find
factors using only tiny numbers. So, in theory, it could factor 2^2000 size numbers using arithmetic on numbers
below 1000 (the sieves) but it would take a very long time since Algorithm D is O(n).

If you study the algorithm, the sieves could be implemented as shift registers in an FPGA. Each sieve is one
shift register. All the sieves run in parallel.

D.H.Lehmer and his son implemented quadratic sieves using various devices, like bicycle chains, film strips,
and electronic delay lines. Lehmer has a paper "A New Factorization Technique Using Quadratic Forms",
Mathematics of Computation, Volume 28, Number 126, April 1974, Pages 625-635.
(Available for free at
The paper present an O(n^1/2) factoring method using quadratic sieves.

As an aside, if trying to factor Mersenne numbers of the form 2^p-1, there is a method given in Hans Riesel's book
for speeding up a quadratic sieve by a factor of 2*p^2.

Lets say an FPGA sieve can sieve 2^28 numbers per second. There are 86,400 seconds in a day. So our sieve
can handle 10^13 numbers per day. Given Lehmer's method is O(n^1/2) I think this means an FPGA sieve
could factor a 26 digit number in one day. Lehmer's method requires checking 3 polynomials, which would
be a natural fit for running all 3 in parallel on 3 boards. (My analysis skills are not the strongest so there could
be a mistake in this logic.)

Given that the Number Field Sieve can factor a 26 digit number faster than 1 day, this is not an earth shaking result
but it might be fun.
Posts: 1
Joined: Wed Nov 04, 2015 2:23 pm

Re: Prime Factorization

Postby xilman » Sun Nov 08, 2015 6:07 pm

bgb wrote:Given that the Number Field Sieve can factor a 26 digit number faster than 1 day, this is not an earth shaking result
but it might be fun.
True, but misleading. Freely available NFS implementations can factor numbers well over 100 digits in less than a day on many machines.
Posts: 80
Joined: Sat May 10, 2014 8:10 pm
Location: UK


Return to Algorithms

Who is online

Users browsing this forum: No registered users and 3 guests