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
http://www.ams.org/journals/mcom/all_issues.html.)
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.
by over9000 » Tue Jun 24, 2014 8:51 pm