Factorization of RSA704

[bai]

Hi all,

RSA704 is factored. A report describing the details of the factorization effort can be found on http://maths.anu.edu.au/~bai

Best regards,
Shi

[debrouxl]

Good job

[otchij]

My congratulations with successful silver grade factorization!

It is nice to see that CADO-NFS is mature enough to handle such dimension.

Just small questions about your achievement:

1) 2^33 used as large prime bound on both sides. Thus special q range should be from 500M to 8589M. In report we see 10000M as an upper boundary. Is it possible to point the largest special q value in your sieving?

2) The second stage (lingen) in block Wiedemann algorithm was taking 10 days. What version of lingen are you using? Single-thread, multi-thread or something else?

Best Regards

[xilman]

Originally Posted by bai

Hi all,

RSA704 is factored. A report describing the details of the factorization effort can be found on http://maths.anu.edu.au/~bai

Best regards,
Shi

The other Paul has just mailed the usual suspects with this result.
Paul

[Batalov]

Stupendous job!
(degree 6, too - very good test)

What was the degree 5 best polynomial?

[bai]

Originally Posted by otchij

My congratulations with successful silver grade factorization!

It is nice to see that CADO-NFS is mature enough to handle such dimension.

Just small questions about your achievement:

1) 2^33 used as large prime bound on both sides. Thus special q range should be from 500M to 8589M. In report we see 10000M as an upper boundary. Is it possible to point the largest special q value in your sieving?

2) The second stage (lingen) in block Wiedemann algorithm was taking 10 days. What version of lingen are you using? Single-thread, multi-thread or something else?

Best Regards

Thanks otchij. Paul mentioned that "Indeed some special-q were above the large prime bound. The largest special-q was 9999999929 (which gave 3 relations in total). This is not really a problem since we can merge all k relations with a given special-q, to obtain k-1 relation-sets without this special-q. Currently CADO-NFS only implements a single-thread version of lingen. It is planned to completely rewrite this program."

[bai]

Originally Posted by Batalov

Stupendous job!
(degree 6, too - very good test)

What was the degree 5 best polynomial?

Thanks Batalov. As far as I can locate, the best deg 5 poly is,

Y1: 49758016715758193
Y0: -62594076250212057850135759159429623544504
c5: 77052360
c4: -842263139899117196
c3: 3877551127632265865220186773
c2: 1349801344279038732547104688214106165
c1: -1381013605456477529347256999964508765576480869
c0: -112375960656174315827082110714419649578392608747527665
# lognorm: 71.08, alpha: -8.60 (proj: -1.96), E: 62.48,
# Murphy's E=4.04e-16

which is about half of the E of the deg 6 one (assuming we can compare polynomials of different degree directly.) It was found by a previous version of polyselect2.c inside polyselect/ folder. As then we mostly focused on deg 6 polynomials, and continued until we found something matching/above the targeted Murphy E (e.g. the projected E's on http://maths.anu.edu.au/~bai/proj_E/).

[poily]

Congrats, nice job! Not so much feasible unfactored RSA numbers left.

[Stargate38]

Yes. Lets hope they find a way to factor RSA-1024. I've been waiting a long time for that.

[ixfd64]

Originally Posted by poily

Congrats, nice job! Not so much feasible unfactored RSA numbers left.

But still a lot.

[Dubslow]

Originally Posted by ixfd64

But still a lot.

The smallest is RSA-210, and I'm pretty sure NFS@Home could sieve that, much like B200. RSA-704 was 212 digits.