Big integer division efficiency

[Marian Kechlibar]

Hi Paul,

thank you for your information. This is news for me; I did not find your
135-dec record
by google, probably because it was not a RSA-number challenge ... I will
take a look.
The 3-large prime variation is also interesting.

We definitely want to try 512-bit, but of course we want to develop GNFS
for that purpose
as well. We already have a small GNFS engine with line sieving, but
lattice sieving will
be needed for any serious factorization attempts. The current version of
GNFS is too slow
and it would benefit greatly from any enhancements (like the one I
started this thread with).

Best regards

Marian
> 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
>
>