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: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.