Improved NFS polynomial selection

jasonp · 2014-09-05, 16:39

Paper by Paul Zimmermann just posted here.

They used the dataset for RSA768 that we generated here in 2011, plus some new quite clever techniques, to find a polynomial that sieves 5-7% faster than the one actually used for RSA768. If you helped with that, you may find yourself in the acknowledgements :)

Optimized results are also included for RSA896 using the huge dataset computed here together with the CADO group, plus some preliminary results for RSA1024.

xilman · 2014-09-05, 17:34

Quote:

Originally Posted by jasonp

Paper by Paul Zimmermann just posted here.

Thanks. Downloaded a copy and printed fo bed-time reading tonight.

VBCurtis · 2014-09-05, 17:59

Jason-
You've said for a long time that sextic searches are dramatically more difficult to optimize, and that some advance in algorithm was needed. This looks like just what you wished for two years ago!

Are you considering coming out of retirement to code this into msieve?

Thanks for the reference; the paper is quite readable for us mere enthusiasts!

2014-09-06, 01:51

Thank you for the link to a very interesting paper.
I have been developing a form of integer factorization over general conics. Hillgarter's 1996 paper provides an algorithm in Maple 5 which unfortunately only creates trivial factorizations using the method I am experimenting with. The following is as far as I have gotten factoring an integer that can be used to factor RSA - 1536. I'm providing the polynomial I obtained with GGNFS.
I will see what CADO 2.1 can do in terms of providing a better polynomial faster.

ET_ · 2014-09-07, 10:51

Quote:

Originally Posted by jasonp

Paper by Paul Zimmermann just posted here.

They used the dataset for RSA768 that we generated here in 2011, plus some new quite clever techniques, to find a polynomial that sieves 5-7% faster than the one actually used for RSA768. If you helped with that, you may find yourself in the acknowledgements :)

Optimized results are also included for RSA896 using the huge dataset computed here together with the CADO group, plus some preliminary results for RSA1024.

I'm there!

Luigi

xilman · 2014-09-07, 11:02

Quote:

Originally Posted by ET_

I'm there!

Luigi

[aol]Me too !!??!!!! [/aol]

2014-09-05, 16:39	#1
jasonp Tribal Bullet Oct 2004 5×23×31 Posts	Improved NFS polynomial selection Paper by Paul Zimmermann just posted here. They used the dataset for RSA768 that we generated here in 2011, plus some new quite clever techniques, to find a polynomial that sieves 5-7% faster than the one actually used for RSA768. If you helped with that, you may find yourself in the acknowledgements :) Optimized results are also included for RSA896 using the huge dataset computed here together with the CADO group, plus some preliminary results for RSA1024. Last fiddled with by jasonp on 2014-09-05 at 16:49

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial selection	Max0526	NFS@Home	9	2017-05-20 08:57
Updated polynomial selection	jasonp	Msieve	65	2011-05-01 19:06
GNFS polynomial selection	Unregistered	Information & Answers	3	2011-04-16 14:24
2^877-1 polynomial selection	fivemack	Factoring	47	2009-06-16 00:24
Polynomial selection	CRGreathouse	Factoring	2	2009-05-25 07:55

2014-09-05, 17:59	#3
VBCurtis "Curtis" Feb 2005 Riverside, CA 7·829 Posts	Jason- You've said for a long time that sextic searches are dramatically more difficult to optimize, and that some advance in algorithm was needed. This looks like just what you wished for two years ago! Are you considering coming out of retirement to code this into msieve? Thanks for the reference; the paper is quite readable for us mere enthusiasts!