mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-05-09, 17:23   #12
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default

Quote:
Originally Posted by jasonp View Post
I understand that (you can't code it up and not realize that). But I think it's valid to ask if there are ways to tweak NFS parameters that speed up the algorithm for input sizes of interest.
Of course there are ways. That's what my recent paper was all about.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-09, 17:41   #13
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

101101100011102 Posts
Default

Quote:
Originally Posted by jasonp View Post
It's a sign of my ignorance that I don't consider filtering to be easy at all :)
I belive Bob to have been guilty of a terminolgical inexactitude. Filtering is "easy" in the sense that it takes much less computation than either sieving or linear algebra.

In my experience, creating and implementing efficient filtering algorithms is far from easy. The simple algorithms are either not very good at filtering or very memory inefficient or both. Most implementations of good algorithms use far too much memory, IMO, and I've spent some time tweaking the CWI filter code to make it run on commonly available machines.

Paul

Last fiddled with by xilman on 2007-05-09 at 17:42 Reason: Fix typo and trim quoted material
xilman is offline   Reply With Quote
Old 2007-05-09, 17:49   #14
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts
Default

Quote:
Originally Posted by xilman View Post
I belive Bob to have been guilty of a terminolgical inexactitude. Filtering is "easy" in the sense that it takes much less computation than either sieving or linear algebra.

In my experience, creating and implementing efficient filtering algorithms is far from easy. The simple algorithms are either not very good at filtering or very memory inefficient or both. Most implementations of good algorithms use far too much memory, IMO, and I've spent some time tweaking the CWI filter code to make it run on commonly available machines.

Paul
I agree that implementations of good algorithms (e.g. clique methods) take
tons of memory. But they take so little TIME that one can afford to do
an out-of-core implementation using temporary files for storage.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-09, 18:44   #15
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

144668 Posts
Default

What I'm saying is:

Suppose I have sieved against significantly too large a factor base size; say the n(L) primes less than L.

What happens if I run the matrix-construction step as if I had used a smaller factor base, say the n(S) primes less than S? If I sieved allowing two large primes plus the special-Q, I will have lots of relations in which I have two large primes, plus the special-Q, plus one or two primes between S and L; the primes between S and L will seldom be singletons because the number of relations is significantly greater than n(L).

I wasn't sure whether the answer would be 'you get a uselessly dense matrix' or 'you don't get a matrix'; doing the runs using the ggnfs matrix-building is tending not to give me a matrix at all, but I am losing huge numbers of relations because they're not allowed to have more than three large algebraic primes.

I know that, asymptotically, filtering is cheap.


I may be confused by the sequence of events when you use the GGNFS suite; that *does* distinguish between factor-base primes and other primes, until it has built a matrix of height the size of the requested factor base, and then 'prunes' that matrix. You're describing filtering, as far as I can tell, as a process which takes a pile of relations and gives you a matrix, without ggnfs/matbuild's two-phase structure.

I'm using 'factor-base primes' to mean 'primes which label the rows of the matrix'; they have nothing to do with the sieving phase.

Last fiddled with by fivemack on 2007-05-09 at 18:58
fivemack is offline   Reply With Quote
Old 2007-05-09, 19:07   #16
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts
Default

Quote:
Originally Posted by fivemack View Post
What I'm saying is:

Suppose I have sieved against significantly too large a factor base size; say the n(L) primes less than L.

What happens if I run the matrix-construction step as if I had used a smaller factor base, say the n(S) primes less than S?



If I sieved allowing two large primes plus the special-Q, I will have lots of relations in which I have two large primes, plus the special-Q, plus one or two primes between S and L; the primes between S and L will seldom be singletons because the number of relations is significantly greater than n(L).

I wasn't sure whether the answer would be 'you get a uselessly dense matrix' or 'you don't get a matrix'; doing the runs using the ggnfs matrix-building is tending not to give me a matrix at all, but I am losing huge numbers of relations because they're not allowed to have more than three large algebraic primes.

I know that, asymptotically, filtering is cheap.
What does " run the matrix-construction step as if I had used a smaller factor base, say the n(S) primes less than S? " MEAN??

I can't make sense of it. Do you mean that while filtering, you
throw away relations that have (say) 3 or more primes larger than some
fixed bound? I can't imagine why such a thing should be necessary.
Once you start filtering, a relation is a relation is a relation.
The distinction between factor base primes and large primes VANISHES.
Why is this so hard?

You say "they're not allowed to have more than three large algebraic primes."
I ask: why not? Is this a restriction of the particular implementation you
are using? If so, then FIX IT. This restriction is not necessary. Indeed,
I can't think why it might even be put in filter code. The filtering code
SHOULD NOT CARE about the sizes of primes that appear in relations.
They should all be treated identically/

Are you complaining about limitations of your software or asking about
how to select parameters for good performance??

If GGNFS has unnecessary restrictions, then FIX them. You sound more as if
you are complaining about some brain dead restrictions of GGNFS than you
are asking about parameterizations.
R.D. Silverman is offline   Reply With Quote
Old 2007-05-09, 20:48   #17
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32·5·79 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
What does " run the matrix-construction step as if I had used a smaller factor base, say the n(S) primes less than S? " MEAN??
He means 'choose a factor base for sieving that is very large, then run the filtering for all primes whose size is some number that happens to be smaller than the largest factor base prime'.

Tom, you don't need a two-phase process to construct a matrix; you really can start with a pile of relations and produce a matrix directly. It's useful to have a two-phase process because filtering only deals implicitly with big primes, and the matrix can be squeezed down a little after it is formed and you can count the number of empty rows.

Whether a factor base exists in the background is a detail that is specific to the implementation, i.e. GGNFS has a relation structure that separates the primes found by sieving from those found by nonsieving means, and it has entries for three of the latter only.

Last fiddled with by jasonp on 2007-05-09 at 20:50
jasonp is offline   Reply With Quote
Old 2007-05-09, 21:58   #18
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

193616 Posts
Default

As far as I can see, GGNFS does not build the matrix from the input relations by filtering according to the model in Cavallar's paper of 2000; it uses an entirely different procedure, in which small primes and large primes are treated separately, and in which all the data structures are set up such that a relation can have no more than three 'large' primes on either side. I suspect what it's doing is closer to the 'structured Gaussian elimination' of the 1990s large sparse linear algebra papers.

The small-prime bound for this procedure is a configurable parameter, usually set to the factor-base bound for the sieving, and I was just wondering what happened if you changed that parameter.

I'm afraid we've been talking at cross purposes, and am sorry to have wasted your time; I agree that Cavallar's algorithm does not depend on the size of the primes appearing in the relation. The correct response to ggnfs's limitations is almost-surely to use msieve instead, and msieve's relationset->matrix step is something like Cavallar's algorithm, in which the parameter I was seeking to optimise in ggnfs's implementation doesn't exist.

Last fiddled with by fivemack on 2007-05-09 at 22:00
fivemack is offline   Reply With Quote
Old 2007-05-10, 12:14   #19
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11001001101102 Posts
Default

Sorry to have bothered you all; the more I look into this, the deeper the deficiencies of ggnfs's relations -> matrix stage look. It seems that substantial oversieving causes some very nasty slowdown in the matrix-tidying phase, which can't be sensible.

All glory to Jason for implementing something more capable!
fivemack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where do I send my PRP primes with large k? Trilo Riesel Prime Search 3 2013-08-20 00:32
48-bit large primes! jasonp Msieve 24 2010-06-01 19:14
lots of large primes Peter Hackman Factoring 2 2008-08-15 14:26
NFS with 5 and 6 large primes jasonp Factoring 4 2007-12-04 18:32
What is the use of these large primes Prime Monster Lounge 34 2004-06-10 18:12

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


Mon Feb 6 12:08:08 UTC 2023 up 172 days, 9:36, 1 user, load averages: 0.62, 0.65, 0.74

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”