mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-01-27, 16:07   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Thumbs up Simultaneous Factoring

Just a thought.

I see that NFSNET is now doing 5,307+, having just sieved 5,307-.

I not that it is possible to do BOTH of them at the same time and
save 25% of the run time.

For each number, we need to sieve the norms of two polynomials.
This is a total of "four sieve procedures" for the two numbers.

But one of the sieves is the SAME for both numbers.

The linear polynomial is the same for both numbers. At the cost of
some additional memory it should be possible to do both numbers at once.
You would need to sieve the linear polynomial only once. This would
save 25%.

Perhaps NFSNET should look into this for their siever.

Bob
R.D. Silverman is offline   Reply With Quote
Old 2005-01-27, 17:44   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

237238 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Just a thought.

I see that NFSNET is now doing 5,307+, having just sieved 5,307-.

I not that it is possible to do BOTH of them at the same time and
save 25% of the run time.

For each number, we need to sieve the norms of two polynomials.
This is a total of "four sieve procedures" for the two numbers.

But one of the sieves is the SAME for both numbers.

The linear polynomial is the same for both numbers. At the cost of
some additional memory it should be possible to do both numbers at once.
You would need to sieve the linear polynomial only once. This would
save 25%.

Perhaps NFSNET should look into this for their siever.

Bob
A nice idea!

I'll think about it.

Paul
xilman is offline   Reply With Quote
Old 2005-01-27, 20:38   #3
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46408 Posts
Default

I once mentioned the same idea to Peter Montgomery, he replied that a certain Bob Silverman mentioned it almost ten years earlier. He also told me that this idea is not implemented in the CWI siever, however multiple polynomial NFS for factoring one number is. Maybe the code could be adapted to the many-numbers-at-once idea.

He also mentioned another nice trick to use symmetry in the algebraic polynomial: for even polynomials, F(a,b) is smooth iff F(-a,b) is, so the algebraic side only needs to sieve nonnegative values. For symmetric polynomials (same coefficients left-to-right as right-to-left), F(a,b) is smooth iff F(b,a) is, though this symmetry seems harder to exploit. He said these tricks are not implemented in the CWI siever, either.

Alex
akruppa is offline   Reply With Quote
Old 2005-01-27, 21:15   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Wink

Quote:
Originally Posted by akruppa
I once mentioned the same idea to Peter Montgomery, he replied that a certain Bob Silverman mentioned it almost ten years earlier. He also told me that this idea is not implemented in the CWI siever, however multiple polynomial NFS for factoring one number is. Maybe the code could be adapted to the many-numbers-at-once idea.

He also mentioned another nice trick to use symmetry in the algebraic polynomial: for even polynomials, F(a,b) is smooth iff F(-a,b) is, so the algebraic side only needs to sieve nonnegative values. For symmetric polynomials (same coefficients left-to-right as right-to-left), F(a,b) is smooth iff F(b,a) is, though this symmetry seems harder to exploit. He said these tricks are not implemented in the CWI siever, either.

Alex

Hi,

I was aware of the symmetry tricks as well; I had even suggested one or
two to Peter some time ago.

I looked into implementing one of the simpler ones (you discussed it above)
and concluded that you needed too much memory and saving of state
information to be effective.

Bob
R.D. Silverman is offline   Reply With Quote
Old 2014-10-15, 04:20   #5
Jayder
 
Jayder's Avatar
 
Dec 2012

4268 Posts
Default

I hope it is alright to bump this 9-year-old topic. I am wondering if the situation is any different, here in the future. Is it?
Jayder is offline   Reply With Quote
Old 2014-10-15, 09:08   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

Yes: many-linear-sides factorisation has been implemented by the EPFL group and used to collect half a dozen largest-SNFS records in succession.

http://eprint.iacr.org/2014/653.pdf
fivemack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Largest Simultaneous Primes robert44444uk Octoproth Search 4 2006-02-04 18:45

All times are UTC. The time now is 08:29.

Sat Nov 28 08:29:40 UTC 2020 up 79 days, 5:40, 3 users, load averages: 1.39, 1.73, 1.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.