Any info on this maybe improved matrix algebra for GNFS?

[Nicko van Someren]

Francois,

	This is a new implementation, not a new method, though
there are some neat tricks in this implementation.  Ben Handley
from the University of Otago in New Zealand worked for us last
winter and spent some time on a fast implementation of the
block Lanczos algorithm with the speed critical sections done
in Itanium machine code.  This was one step towards the goal of
showing that 512 bit keys can be factored without having to use
a supercomputer but can in fact be factored using just what we
had in the office.  The technology is little different from the
stuff done to solve the last puzzle in The Codebook other than
the fact that few offices have quad-processor Compaq Alpha
servers but an increasingly large number have Win2K servers
with Itaniums in them.

	I think that Ben intends to publish some of the results
and code as part of his university dissertation.  I don't know
if he reads this list so I will forward this message to him in
case he wants to add more.

	Nicko


Francois Grieu wrote:

> Found the following at
> <http://www.eweek.com/article/0,3658,s=712&a=25047,00.asp>
> 
> "(..) The paper, written by Nicko van Someren, CTO of nCipher Corp., a
> security equipment vendor based in Cambridge, England (..) discloses
> that (..) a student researcher at nCipher recently developed a new
> implementation of a factoring method known as the General Number Field
> Sieve, or GNFS, which could be used to factor a 512-bit key in about
> three weeks using an off-the-shelf server with an Intel Corp. Itanium
> processor. The calculations the student performed using the server are
> the second phase of the GNFS method.
> Previously, this process was thought to be feasible only on much more
> powerful computers, such as Cray supercomputers."
> 
> In a recent message, Nicko van Someren confirms:
> 
>>My research student last winter showed that 512 bit keys can be
>>factored in a matter of weeks using only the hardware found in a
>>busy 70 person office."
>>
> 
> Is there any info on the method used by this student to solve
> the matrix algebra?
> 
> Is any novelty claimed beyond the technique used in
> <http://codebook.org/codebook_solution.pdf>
>  "The program we used for this was optimized for running on vector
>   computers, which is what CWI used for their record (RSA-155)
>   factorization (..) We started to rewrite this program so that it
>   would run better on the hardware available for us (..)
>   Compaq generously let us use one of their quad processor
>   ES40 systems. The total running time on this machine was 13 days,
>   which is almost as good as the 16-processor Cray."
> 
> or to the one used in the recent
> <http://www.loria.fr/~zimmerma/records/gnfs158>
>  "The block Lanczos algorithm produced 62 elements of the kernel of
>   this matrix. This took two weeks on the six PCs on which the filter
>   job was run."
> 
> 
> TIA
> 
>   François Grieu
> 
> 
> 



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com