Xilinx 3s8000?

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.

Ron <News5@spamex.com> 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.

Why not use bricks with matrix or bus wired fpgas?, and let them share the
load. They got lvds etc.. so they can ship data quick within a board.
If one needs more horsepower one simple adds another brick to the backplane.

Spartan is the low-cost FPGA product line, and thus more limited in
size.
Virtex -2 and Virtex-4 offer bigger sizes and higher speed (at higher
cost)

If the design does not fit, partition it into several chips, probably
at minimal performance loss (if done right).

Peter Alfke, Xilinx

On Wed, 03 May 2006 18:10:15 -0700, Ron <News5@spamex.com> 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..?

Mike Harrison wrote:
> 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..?

Exactly what I was thinking Mike. :-)  What's frustrating is that 
although I could see spending a thousand or two thousand dollars for a 
development board, I simply cannot justify spending $2,495 of my 
retirement nest egg for the software tools alone.

I wonder if Peter Alfke of Xilinx would care to comment on the 
possibility of my acquiring a loaner devboard and development s/w? I'm 
located in the San Gabriel Valley just North-West of Los Angeles. The 
email address I'm using (News5@spamex.com) is valid by the way, at least 
until it starts getting too much spam, and then I'll change it to News6, 
News7, etc.

Some of the large computer software makers (MatLab, MapleSoft, etc) 
offer non-profit discounts for educational and personal non-commercial 
use. It would be wonderful if Xilinx (my favorite) or one of the other 
FPGA vendors would offer some sort of low cost alternative to me and 
those in my situation who would love to use your high end FPGAs, but 
cannot afford the cost of the s/w development tools.

Thanks,

Ron

Ron,

We already sponsor this sort of research at many universities and schools.

If you want to go play, there are many excellent programs in graduate 
education on the subject.

I am aware of a very active group at UCLA.

Austin

Ron wrote:

> Mike Harrison wrote:
> 
>> 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..?
> 
> 
> Exactly what I was thinking Mike. :-)  What's frustrating is that 
> although I could see spending a thousand or two thousand dollars for a 
> development board, I simply cannot justify spending $2,495 of my 
> retirement nest egg for the software tools alone.
> 
> I wonder if Peter Alfke of Xilinx would care to comment on the 
> possibility of my acquiring a loaner devboard and development s/w? I'm 
> located in the San Gabriel Valley just North-West of Los Angeles. The 
> email address I'm using (News5@spamex.com) is valid by the way, at least 
> until it starts getting too much spam, and then I'll change it to News6, 
> News7, etc.
> 
> Some of the large computer software makers (MatLab, MapleSoft, etc) 
> offer non-profit discounts for educational and personal non-commercial 
> use. It would be wonderful if Xilinx (my favorite) or one of the other 
> FPGA vendors would offer some sort of low cost alternative to me and 
> those in my situation who would love to use your high end FPGAs, but 
> cannot afford the cost of the s/w development tools.
> 
> Thanks,
> 
> Ron

Austin Lesea wrote:
> Ron,
> 
> We already sponsor this sort of research at many universities and schools.
> 
> If you want to go play, there are many excellent programs in graduate 
> education on the subject.
> 
> I am aware of a very active group at UCLA.
> 
> Austin


uh... would you mind giving me a pointer to these guys ?

lukasz

Austin Lesea wrote:

> We already sponsor this sort of research at many universities and schools.
> If you want to go play, ...

Play? Research? How insulting. Didn't you read my original message at 
all? There is no play or research involved. I suppose since this is a 
hobby of mine, it could be considered "play" in a sense, but there is 
also a $30,000 reward for factoring RSA-704 which isn't normally 
associated with "play".

I have already designed and tested my circuit (both in simulation and on 
a *REAL* FPGA, but using a smaller bus width). There is absolutely NO 
research whatsoever involved, it's purely a pragmatic matter of 
implementation and being able to afford your overpriced software design 
tools on my retirement savings.

For what it's worth, I've had Fermat's Method of integer factorization 
running on a Lattice LFEC20E FPGA for a couple of weeks so far (it's the 
only algorithm small enough to fit on the Lattice board), but since it's 
a sub-optimal factorization method, I have little or no hope that it 
will ever find the answer. ECM is another matter however, because it's 
well known and respected in numerical analysis circles. That and its 
relative simplicity compared with NFS is the reason I chose it.

Gads, play indeed.

Ron

http://www.emsec.ee.ucla.edu/

Austin

Lukasz Salwinski wrote:

> Austin Lesea wrote:
> 
>> Ron,
>>
>> We already sponsor this sort of research at many universities and 
>> schools.
>>
>> If you want to go play, there are many excellent programs in graduate 
>> education on the subject.
>>
>> I am aware of a very active group at UCLA.
>>
>> Austin
> 
> 
> 
> uh... would you mind giving me a pointer to these guys ?
> 
> lukasz

Ron,

I play everyday.  Play is what some people call work who don't enjoy 
what they do.  My oldest brother Ron had a great attitude: if you don't 
look forward to walking through the door in the morning: don't - go get 
another job.

To help you win a prize is not in the realm of 'sponsored tax deductible 
activities' that Xilinx is inclined to support.

I meant no disrespect.  If you call it "hard work" then that is fine by me.

That prize for factoring is an incentive to continue the research in 
cypher breaking, and improving computational methods.

We need no such prize:  our customers have real problems (3-D Xray 
imaging, 3G base stations, joint task strike fighter plane, Mars Rovers, 
gigabit routers, etc.) that need our devices every day to solve their 
problems.

That prize was 1.73 billion dollars (US)last year (Xilinx sales).

If you feel that you can win the prize, you should invest your own 
money, and build the "solver."  I have no doubt it will be done by 
someone, and soon (since there are published papers on how to use FPGAs 
to do this now for less money).

Austin

Ron wrote:

> Austin Lesea wrote:
> 
>> We already sponsor this sort of research at many universities and 
>> schools.
>> If you want to go play, ...
> 
> 
> Play? Research? How insulting. Didn't you read my original message at 
> all? There is no play or research involved. I suppose since this is a 
> hobby of mine, it could be considered "play" in a sense, but there is 
> also a $30,000 reward for factoring RSA-704 which isn't normally 
> associated with "play".
> 
> I have already designed and tested my circuit (both in simulation and on 
> a *REAL* FPGA, but using a smaller bus width). There is absolutely NO 
> research whatsoever involved, it's purely a pragmatic matter of 
> implementation and being able to afford your overpriced software design 
> tools on my retirement savings.
> 
> For what it's worth, I've had Fermat's Method of integer factorization 
> running on a Lattice LFEC20E FPGA for a couple of weeks so far (it's the 
> only algorithm small enough to fit on the Lattice board), but since it's 
> a sub-optimal factorization method, I have little or no hope that it 
> will ever find the answer. ECM is another matter however, because it's 
> well known and respected in numerical analysis circles. That and its 
> relative simplicity compared with NFS is the reason I chose it.
> 
> Gads, play indeed.
> 
> Ron