Big integer division efficiency

[Paul Leyland]

On Wed, 2007-11-07 at 15:43, Marian Kechlibar wrote:
> Hi Alexander,
> 
> 1. Thank you.
> 
> 2. Yes. Not now, but in the future. And here are the reasons why:
> 
>     2.1   The last time that SIQS was used to achieve a factoring record
> was,
> I believe, in 1994. That time, MPQS with a single-large variation was used,
> and the factored number had about 440 bits.

Your information is out of date and incorrect.

The 1994 factorization was that of RSA-129, a 426-bit number.  It used
MPQS (not SIQS), and with two large primes (not one).  The title of the
paper describing that computation is "THE MAGIC WORDS ARE SQUEAMISH
OSSIFRAGE".

More recently (4 September 2001 to be precise) the 135-digit cofactor of
2,1606L was completed by QS.  Both MPQS and SIQS sievers were used (SIQS
by Sam Wagstaff; MPQS by Arjen Lenstra, Alec Muffett and myself), each
using 3 large primes.

The information above should be enough to feed into a search engine if
you want more detail on these factorizations.


There is no doubt that a 512-bit number can be factored by QS.   There
is equally no doubt that it would be many times easier to do it by
GNFS.  I'm not sure how much easier, but I'd guess about 20-fold.  Our
paper contains the timing data which would let you make a reasonable
estimate from the asymptotic behaviours of QS and GNFS


Paul

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20071107/4f9b252e/attachment.bin