Glory and riches are showered upon those who successfully factor one of

the RSA Challenge Numbers (see note [1]) ;-). I would like to be the

first to factor an RSA number using a standalone

FPGA development

board(s) (ie; not connected to a conventional computer).

The RSA Challenge numbers have traditionally been solved by networks of

supercomputers using a distributed Number Field Sieve (NFS) or similar

method. Sieving is unfortunately not suited to

FPGA implementation, but

there is another integer factorization method called the Elliptic Curve

Method (ECM, see note [3]) that I think might stand a chance of cracking

RSA-704. I have therefore designed and tested a Verilog implementation

of ECM with a compile time bus-width specification (ie; `define L 704)

so that it's easy to determine how the LUT requirement increases as I

change the bus width. I've optimized the circuit for gate count to the

extent of multiplexing everything that is used more than once (multiply,

divide, modulo, etc) - a process that almost brought tears to my eyes at

one point, because I had to eliminate several areas that naturally lent

themselves to parallelization.

Even so, the design requires far more LUTs than are currently available

from anyone as far as I know. I presently have Xilinx xc3s500e and Actel

ProASIC3E A3PE600 development boards, but I can't compile the design for

a 704 bit bus-width because I get the error message in Note [4] below (I

also get a similar message from the Actel synthesizer). I *can* compile

the design for a 384 bus-width however. Using a Xilinx 3s4000 as the

target device (even though I only have a 3s500) with a 384 bit

bus-width, I get the following Device utilization summary:

---------------------------

Selected Device : 3s4000fg676-4

Number of Slices: 49176 out of 27648 177% (*)

Number of Slice Flip Flops: 52253 out of 55296 94%

Number of 4 input LUTs: 83797 out of 55296 151% (*)

Number of bonded IOBs: 18 out of 489 3%

Number of GCLKs: 1 out of 8 12%

WARNING:Xst:1336 - (*) More than 100% of Device resources are used

---------------------------

This would lead me to believe that my design would require at least

101,376 LUTs, and probably more depending on how much of the

FPGA is

consumed by routing. Since the Xilinx 3s4000 has 55296 LUTs and 27648

slices, I imagine a part with twice that number of slices & LUTs (a

Xilinx 3s8000 perhaps?) would be needed to fit my design. Anyone care to

hazard a guess as to if/when such a monster might be available?

Also, thus far the longest number that has been factored with ECM is

only 66 decimal digits (see Note [3]). If RSA-704 (212 decimal digits)

were factored, it would set a new record for ECM factoring also.

If such a device did become available, my only hope for acquiring the

requisite hardware/software would be to work out a deal with the

FPGA
vendor or someone to lend me the necessary development board and s/w

tools in exchange for the potential fame and glory, since I am but a

humble retired engineer/hobbyist. :-)

Ron

_________________

Notes:

[1] RSA Challenge Numbers:

http://www.rsasecurity.com/rsalabs/node.asp?id=2093
[2] Factoring Methods:

http://mathworld.wolfram.com/PrimeFa...lgorithms.html
[3] Elliptic Curve Factorization Method

http://mathworld.wolfram.com/Ellipti...ionMethod.html
[4] When synthesizing ECM with a 704 bit bus-width for the Xilinx

xc3s4000-4fg676, I get:

ERROR: Portability:3 - This Xilinx application has run out of memory or

has encountered a memory conflict. Current memory usage is 2092148 kb.

Memory problems may require a simple increase in available system

memory, or possibly a fix to the software or a special workaround. To

troubleshoot or remedy the problem, first: Try increasing your system's

RAM. Alternatively, you may try increasing your system's virtual memory

or swap space. If this does not fix the problem, please try the

following: Search the Answers Database at support.xilinx.com to locate

information on this error message. If neither of the above resources

produces an available solution, please use Web Support to open a case

with Xilinx Technical Support off of support.xilinx.com. As it is

likely that this may be an unforeseen problem, please be prepared to

submit relevant design files if necessary.

ERROR: XST failed

Process "Synthesize" did not complete.