Re: Xilinx 3s8000?

On Wed, 03 May 2006 18:10:15 -0700, Ron <News5@xxxxxxxxxx> wrote:

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/PrimeFactorizationAlgorithms.html

[3] Elliptic Curve Factorization Method
http://mathworld.wolfram.com/EllipticCurveFactorizationMethod.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.

Maybe you should talk to XIlinx about lending you a devboard for one of their high-end chips, in
return for some good publicity when you crack it..?
.

Relevant Pages

  • Xilinx 3s8000?
    ... I would like to be the first to factor an RSA number using a standalone FPGA development board. ... 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 below. ... ERROR: Portability:3 - This Xilinx application has run out of memory or has encountered a memory conflict. ...
    (comp.arch.fpga)
  • Re: 66MIPS 8bit microcontroller
    ... The FPSLIC runs at 40 MHz and has max 32 kB code memory and no external bus. ... It's pretty simple to knock over a FPGA on Priceand Icc, ... Plus, it skews design decisions. ... course there are the complications of any combination of FPGA and CPU ...
    (comp.arch.embedded)
  • Re: Xilinx 3s8000?
    ... I brushed it off and came across some Xilinx devices. ... there is another integer factorization method called the Elliptic Curve ... the design requires far more LUTs than are currently available ... has encountered a memory conflict. ...
    (comp.arch.fpga)
  • Re: newbie wants to do VHDL on an FPGA
    ... I have done FPGA design some years ago using a Schematic Design tool ... from Xilinx, so I am not totally "green". ... the Spartan 3 family. ...
    (comp.arch.fpga)
  • Re: Rad-hard (neutron/SEU and space) tutorial?
    ... Read all papers from MAPLD, RADECS, NSREC, and SELSE. ... Read all the online information from Xilinx ... DAC, power supplies, etc) design, as well as for FPGA and ASIC ... Even if my FPGA or ASIC design is solid, ...
    (comp.arch.fpga)
Loading