|
2013-11-13, 13:34
|
#177 | |
Nov 2003
22·5·373 Posts |
Quote:
Hardy & Wright: Introduction to Number Theory Crandall & Pomerance : Prime Numbers, a Computational Perspective Knuth: TAOCP, VOl 2. Read them from cover to cover. DO THE EXERCIZES. If you have trouble with the text or exercizes, ASK. If you want additional references we can provide them. I assume that as part of your degree that you did take at least one course in modern algebra and one in linear algebra and that you have some mathematical maturity. What is it that you don't understand about my post? |
|
|
|
|
2013-11-13, 22:13
|
#178 | |||||
Feb 2012
Paris, France
7×23 Posts |
I think we are going a little bit off topic.. anyway here is my answer.
Quote:
Thanks for the references. Quote:
Quote:
Quote:
Quote:
You wrote that you compute the actual factorizations of the smooth relations via a re-sieve, does it mean that you relaunch the siever on the same range? You also wrote that you store the factors found during the re-sieve in a hash table. I suppose you use a program to do so? How do you know whether an overflow occurs when storing the factors in the hash-table? |
|||||
|
|
|
|
2013-11-13, 23:48
|
#179 | |
|
Nov 2003
22·5·373 Posts |
Quote:
How much do you know about how NFS works? You need to gain a basic understanding of what it does before we can have further discussion. We have two fields: One is typically Q, another is Q(alpha) for some alpha a root of an irreducible polynomial f. We also have an integer N that we are trying to factor and a second polynomial g. f and g share a common root M mod N, so there is a ring homomorphism phi from alpha to M over Z/NZ. This yields a congruence (a + bM) = (a + b phi(alpha)) mod N. Thus the congruence has "two sides" We look for lattice points (a,b) such that the norm of a + bM and the norm of a + b alpha are simultaneously smooth. We sieve over (a,b) for one set of norms/polynomial, and over a sub-lattice of (a,b) for the other polynomial such that the norms in the sub-lattice are always divisible by the special q. The siever isn't 'relaunched'. It is all one program. Once we find points whose norm might be smooth, we need to reconstruct the factorization. This is partially done by running the sieve again, but instead of adding log(p) to lattice locations, we store p itself in a hash table. If you do not know what a hash table is, or how it works you have more reading to do. Read the Knuth volume (3?) that discusses it. One gets a hash overflow when there isn't enough vacant space in the table to store more primes. An NFS siever is complicated. You might first want to learn how QS works. |
|
|
|
|
|
2013-11-14, 01:36
|
#180 | |
"William"
May 2003
New Haven
2·7·132 Posts |
Quote:
 
|
|
|
|
|
|
2013-11-14, 05:28
|
#181 | |
|
Romulan Interpreter
Jun 2011
Thailand
966410 Posts |
Quote:
+1. (I like this new Mr. Silverman! ...  )
|
|
|
|
|
|
2013-11-14, 07:44
|
#182 | ||
|
Romulan Interpreter
Jun 2011
Thailand
26×151 Posts |
Quote:
Quote:
|
||
|
|
|
|
2013-11-14, 14:09
|
#183 | |||
|
Feb 2012
Paris, France
7×23 Posts |
Quote:
looking into the QS is what I was doing over the last few days mainly by the reading the Crandall & Pomerance and I think I got the idea. Quote:
"sieving on the algebraic side", it comes from the congruence a + bM = (a + b phi(alpha)) mod N. I can directly map that to the corresponding command line options in the GGNFS siever. I know what an hash-table is but I don't see how it can overflow I think it depends on the implementation.. If we temporarily forget about the hash-table, is what you wrote equivalent to setting a bound B on the number of primes obtained by re-sieving and saying that an overflow occurs iff the number of primes becomes >= B. If so, how is B computed? Generally speaking I have a hard time finding the correspondence between the theory and all those values in the poly file. I've seen various posts were people talk about sieving on both sides but AFAIK factmsieve.py(*) sieves only one side. (*) Brian Gladman's python script I've been using for months as a fire and forget tool for my factorizations. Quote:
|
|||
|
|
|
|
2013-11-14, 14:28
|
#184 | |||
|
Nov 2003
22·5·373 Posts |
Quote:
to store than space allows one gets an overflow. Why is this a mystery? One can also get an "overflow" as the table starts to get full. If a collision occurs it has to be resolved. There are a variety of ways to do this. But once the table starts to get full one spends TOO MUCH TIME resolving the *()!#&*@#&* collisions. It isn't worth it. Yes. I could re-code to dynamically allocate more space for the table as it starts to get full. I never thought it worth the effort. Quote:
Quote:
side, but both sides get sieved. Perhaps you might want to read "Development of the Number Field Sieve", by Lenstra et.al.? |
|||
|
|
|
|
2013-11-14, 14:29
|
#185 | |
|
(loop (#_fork))
Feb 2006
Cambridge, England
642410 Posts |
Quote:
You have regardless to end up with X,Y where f_algebraic and f_rational are only divisible by moderately-sized primes. |
|
|
|
|
|
2013-11-14, 14:45
|
#186 |
|
Tribal Bullet
Oct 2004
3×1,181 Posts |
Regarding the confusion about using hashtables: Sieving in NFS requires finding places where the values of two polynomials are simultaneously divisible by small factors. The goal is never to find all such places but to maximize the number of such places found per unit time. All those sieving parameters are there to set up approximations that reduce the work in return for missing a few 'hits' that we would otherwise find.
Hits are expected to be rare. Rather than evaluating the sieve for both polynomials simultaneously, we can evaluate one sieve, remember any (approximate) hits found, and then evaluate the other sieve at only those locations. Another possibility is to run both sieves but not bother to remember the list of primes dividing each hit. Then for simultaneous hits in both sieves we can go back and reconstruct the list of primes later. These techniques both benefit from using hashtables; putting too many hits in the hashtable is not impossible, but it does mean the approximations used are too loose and you will spend too much time sorting usable hits from unusable ones. This is the 'overflow' condition Bob refers to. |
|
|
|
|
2013-11-14, 18:33
|
#187 | |
"Jonathan"
Jul 2010
In a tangled web...
21510 Posts |
Quote:
For the parameters, you'll notice that about half end in "r" and half end in "a". The "r" ones apply to the 'rational' sieving and the "a" ones apply to the 'algebraic' sieving. Concretely, if you are manually calling the siever or modifying the scripts, you will have know that the "-a" parameter is for specifying 'algebraic' sieving and "-r" for 'rational' sieving. Hope that helps a bit .For what that means mathematically, you will have to listen RDS, Fivemack, jasonp, etc. |
|
|
|
|
 |
| Thread Tools | |
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Vanishing Fermat Quotients and Brent's List | Zeta-Flux | Factoring | 74 | 2010-04-07 22:03 |
| Brent-Suyama extension of P-1 factoring | S485122 | Math | 1 | 2009-08-23 15:21 |
| Brent-Montgomery-te Riele numbers | FactorEyes | Factoring | 23 | 2008-02-22 00:36 |
| brent suyama extension in P-1 | bsquared | Factoring | 9 | 2007-05-18 19:24 |
| Brent's p-1 - How to deal with memory problems? | jhillenb | Factoring | 4 | 2005-01-11 23:50 |
