mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-07-20, 11:02   #12
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101110001012 Posts
Default

NFS does not use a base of primes, it uses a base of 'ideals'. These look like prime numbers, but are more general. They help determine whether the algebraic 'thing' I mentioned is a square; it is actually the product of ideals.

I'm not sure what you're asking, but theory gives an estimate of how big the base of ideals and the size of the matrix should be to minimize the running time of NFS. We use experiments and guesswork to improve that estimate.
jasonp is offline   Reply With Quote
Old 2011-07-20, 12:44   #13
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5×359 Posts
Default

Quote:
Originally Posted by jasonp View Post
Actually for a polynomial of degree d the algebraic part of the relation is b^d * AlgebraicPoly(a/b). d just happens to be 6 here.

I have no time to read Socrates in the original French, being in the middle of reading Shakespeare in the original Klingon.
Damn! I was just in the middle of reading Sartre in the original sanskrit!

You guys work way too hard at optimisation for the degree to "just happen" to be six....for example, six is two more than the degree of the largest polynomial with an algebraic formula in the coefficients for the roots. Or does finding and calculating with 7th degree polys carry a high cost that was found experimentally?
Christenson is offline   Reply With Quote
Old 2011-07-20, 14:51   #14
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·52·127 Posts
Default

Yes; you can just experiment with the degree of the polynomial.

Degree 5 is pretty much OK from 110 digits to 200 digits GNFS; degree 4 is better for smaller numbers, degree 6 is a bit better for bigger ones.
fivemack is offline   Reply With Quote
Old 2011-07-20, 15:24   #15
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by fivemack View Post
Yes; you can just experiment with the degree of the polynomial.

Degree 5 is pretty much OK from 110 digits to 200 digits GNFS; degree 4 is better for smaller numbers, degree 6 is a bit better for bigger ones.
And for RSA1024, it is likely/possible that a septic will be better than a sextic.
AFAIK, we have no software for generating septics.
R.D. Silverman is offline   Reply With Quote
Old 2011-07-20, 16:33   #16
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

100111011010002 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
And for RSA1024, it is likely/possible that a septic will be better than a sextic.
AFAIK, we have no software for generating septics.
To be more precise: AFAIK, we have no software for generating good septics. It's really really easy to generate bad ones.


Paul
xilman is offline   Reply With Quote
Old 2011-07-20, 16:39   #17
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·52·47 Posts
Default

It's true that nobody does GNFS with degree 7, but there is nothing special about degree 7 compared to degree 6. The first stage runs identically for any degree, you just have to find a target norm to shoot for. But the first stage only finds an algebraic polynomial whose top three coefficients obey the bound on the norm, and as the degree goes up the coefficients in the middle of the algebraic polynomial need to be forced to be smaller and smaller.

This is what stage 2 does; almost every degree 4 polynomial passes automatically and most degree 5 polynomials obey the bound after some fiddling. It starts to get difficult for degree 6, and doing the same with degree 7 and large amounts of skew means you'll have to go through millions of stage 1 candidates to find just one whose norm is decent. It might be so much work that it would be faster to modify stage 1 to directly generate candidates with more small high-order algebraic coefficients.

Brian Murphy's dissertation on polynomial selection has a pretty nice derivation of the formula for the NFS polynomial degree that is asymptotically optimal given the size of the number to be factored.

Last fiddled with by jasonp on 2011-07-20 at 16:43
jasonp is offline   Reply With Quote
Old 2011-07-21, 07:12   #18
JohnFullspeed
 
May 2011
France

2418 Posts
Default degree 7

Always with stupid questions
The goal of the polynomial is to get a maximum of relations
smooth with b
How the degree changes this probability

John
JohnFullspeed is offline   Reply With Quote
Old 2011-07-21, 07:54   #19
JohnFullspeed
 
May 2011
France

16110 Posts
Default 1500 years?

make this computation

64 334 489 730 relations computed in 1500 years
1500 * 365 = 547 500 days
547 500 * 24 = 13 140 000 hours
13140000 * 60 = 788 400 000 minutes
64334489730 / 788400000= 81/mn
less one second to compute f(x) ,factories
and remove bad. It' impossible !!!! (for me....)

I think that 1500 years is not good: it's more!!!!!!!!
The total time must be compute by T* 64334489730 where T is this average time between the find of two relations
You surely have this time to distribute the code;
or you distribute the code using time or using the number of relation
i/e the PrimeGrid code search by segments of X minutes
or search Y relations

John
JohnFullspeed is offline   Reply With Quote
Old 2011-07-21, 11:51   #20
Chris Card
 
Chris Card's Avatar
 
Aug 2004

8116 Posts
Default

Quote:
Originally Posted by JohnFullspeed View Post
Always with stupid questions
The goal of the polynomial is to get a maximum of relations
smooth with b
How the degree changes this probability

John
One factor is that polynomials with smaller coefficients can be found if the degree is higher. Then the relation norms are smaller (on average), and so they are more likely to be smooth.

Chris
Chris Card is online now   Reply With Quote
Old 2011-07-21, 13:13   #21
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×52×47 Posts
Default

The smaller coefficients make it easier to find smooth numbers, but as (a,b) gets larger the higher degree will force the norm to increase more quickly (x^6 vs x^5). So you get a boost for small (a,b) but pay for it with large (a,b). The optimal degree is a compromise between these two forces.
jasonp is offline   Reply With Quote
Old 2011-07-21, 13:54   #22
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11101001000002 Posts
Default

Quote:
Originally Posted by jasonp View Post
The smaller coefficients make it easier to find smooth numbers, but as (a,b) gets larger the higher degree will force the norm to increase more quickly (x^6 vs x^5). So you get a boost for small (a,b) but pay for it with large (a,b). The optimal degree is a compromise between these two forces.
It isn't quite this simple. Larger degrees also result in the rational
norm being smaller because the polynomial root becomes smaller.

Note also, that lattice sieving on the rational side ameliorates somewhat
the (effect of) degree increase on the algebraic.

Consider the rational side norm. We want norm(a + b N)/special_q
to be smooth. This suggests that the rational norms decrease with q.
They do, but only with sqrt(q) and not q itself.


The way lattice sieving works is by finding a reduced
lattice for the special_q. The average coefficient size of this reduced
lattice is about sqrt(q). Let [(a1, b1), (a2, b2)] be the reduced lattice.
The sieve works over the norms: i *(a1,b1) + j *(a2,b2) as i,j vary over a
(rectangular) sub-lattice. The norms depend on (a1, a2, b1, b2) and these
are roughly proportional to sqrt(q).

OTOH, while this reduces the effectiveness of special_q on the rational
side [norms we want smooth reduce by sqrt(q) instead of by q as q
increases]

This HELPS on the algebraic side. There is what I call a ying-yang effect in NFS.

Push the norms down on one side and it increases on the other. Optimum
is found when the norms are as nearly equal as possible. Normally,
if one pushes the rational norm down by a factor k, it pushes the
algebraic norm up by k^d. But since special_q on the rational
only pushes the norm down by sqrt(q) instead of q, it only pushes
the algebraic norm up by q^(d/2) instead of q^d.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Two questions: Dubslow GPU Computing 1 2011-08-05 18:22
Questions about the QS Carmichael Factoring 8 2007-04-10 11:30
Questions OmbooHankvald Prime Sierpinski Project 2 2005-08-01 20:18
LLR questions OmbooHankvald Math 6 2005-06-23 11:42
A few questions :) xtreme2k Lounge 59 2002-10-31 06:20

All times are UTC. The time now is 11:02.

Tue Jul 14 11:02:53 UTC 2020 up 111 days, 8:35, 0 users, load averages: 2.06, 1.89, 1.73

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.