A new moderator has just completed part of his mandatory moderator training program, which includes permanently deleting a couple dozend messages. Thank you for posting, thus providing the prerequisite training materials. Feel free to repost.

Edit: new thread [URL=http://www.mersenneforum.org/showthread.php?t=15130]here[/URL].

[QUOTE=jrk;249918]The siever source was modified to allow specialQ below the factor base bound.[/QUOTE]
Could this fix be added to svn? Many of us would like to be able to sieve below the fb bound.

[QUOTE=henryzz;249966]Could this fix be added to svn? Many of us would like to be able to sieve below the fb bound.[/QUOTE]

I'll leave it on my TO-DO list, but the current method is too much of a hack. i.e. it needs to be better first.

Keep in mind that this is really only useful if you can get away with sieving relatively few specialQ within the factorbase. If you're going to require a huge range of Q in the factorbase then it is probably better to use larger Q instead. So for jobs bigger than ~c140 this probably won't help much.

[QUOTE=jrk;249918]Logfile is attached.[/QUOTE]

I notice the log says "Msieve v. 1.49". I downloaded what I though was the latest SVN last Friday, that's 1.48. Have I missed something useful?

Chris K

[QUOTE=chris2be8;250145]I notice the log says "Msieve v. 1.49". I downloaded what I though was the latest SVN last Friday, that's 1.48. Have I missed something useful?

Chris K[/QUOTE]

If you downloaded from the "files" section of the site, you get 1.48, which is the latest release version and is recommended. Jason bumps the version number in SVN after each release, so if you "svn checkout" you get something that currently says 1.49, but this occasionally leads to headaches as things might be broken.

[QUOTE=jasonp;172522]The 'm' line is not necessary with GGNFS, it computes the common root by itself. When we get to nonlinear rational polynomials (if ever) this will definitely have to change.[/QUOTE]

If by non-linear rational polynomials you mean quadratic and higher
degree polynomials with arbitrary rational coefficients, what's the
problem with GGNFS that makes this not-yet-implemented?

This is just a general intro question.

[QUOTE=davar55;250216]If by non-linear rational polynomials you mean quadratic and higher
degree polynomials with arbitrary rational coefficients, what's the
problem with GGNFS that makes this not-yet-implemented?
[/QUOTE]
No, I don't mean that. NFS polynomials are determined by trying to express the number N to be factored as two polynomials with integer coefficients, and you need to find a common root of the two polynomials mod N. When one of the polynomials is linear this procedure is easy: for 2^128 + 1 you can have an algebraic polynomial of 4*x^3+1 and a rational polynomial of x - 2^42. Even when N doesn't have a special form you can brute-force the problem by picking a base of m and expressing the input in base m, then fiddling with m a little bit to make the algebraic polynomial coefficients smaller.

You can't use that procedure if you let the rational polynomial have degree higher than 1. In that case the polynomials have to be built using lattice reduction and the choice of m is much more difficult. Making nonlinear rational polynomials is actually an active research area, one of several associated with NFS polynomial selection.

[QUOTE=jasonp;250223]No, I don't mean that. NFS polynomials are determined by trying to express the number N to be factored as two polynomials with integer coefficients, and you need to find a common root of the two polynomials mod N. When one of the polynomials is linear this procedure is easy: for 2^128 + 1 you can have an algebraic polynomial of 4*x^3+1 and a rational polynomial of x - 2^42. Even when N doesn't have a special form you can brute-force the problem by picking a base of m and expressing the input in base m, then fiddling with m a little bit to make the algebraic polynomial coefficients smaller.

You can't use that procedure if you let the rational polynomial have degree higher than 1. In that case the polynomials have to be built using lattice reduction and the choice of m is much more difficult. Making nonlinear rational polynomials is actually an active research area, one of several associated with NFS polynomial selection.[/QUOTE]It's easy enough to find two quadratics --- Peter Montgomery showed how to do that about 15 years ago. The problem is that two quadratics aren't actually of much use in most cases.

As you say, finding pairs (or, multiples in general) of non-linear polynomials with small coefficients and a common root is still an interesting but unsolved problem.


Paul

[QUOTE=xilman;250253]It's easy enough to find two quadratics --- Peter Montgomery showed how to do that about 15 years ago. The problem is that two quadratics aren't actually of much use in most cases.

Paul[/QUOTE]

Do ggnfs and msieve support them? If so what do the parameters in name.poly look like? They would be useful for numbers in t1200.txt where the exponent is 2, so we get a quadratic to start with.

Chris K

PS. Thanks to JRK for the explanation of msieve 1.49.

Msieve currently does not support nonlinear rational polynomials, but (if I understand the math correctly) only the square root would need a minor change to fix that. I'll make the change if you show me a polynomial pair that is more efficient with a nonlinear rational polynomial.

Part of the problem is that polynomial pairs with linear rational polynomials can be optimized in a manner that is well understood, and those optimization methods do not work nearly as well if the rational polynomial is not linear. To replace degree-5/degree-1 with degree-3/degree-3 is now possible thanks to recent work by Paul Zimmermann and one of Chris Monico's grad students; the size of the norms in the latter is more balanced. But the former has lots of potential to optimize its root properties, and lots of ways to generate many candidates for the optimization to work on, while polynomials of equal degree basically need to be enumerated by brute force until a good one pops out.

So right now for GNFS polynomials, the standard practice has set the bar quite high. I have no idea how one can find a SNFS polynomial pair with a nonlinear rational poly.

The two-cubics paper is at [url]http://hal.archives-ouvertes.fr/docs/00/54/04/83/PDF/polyselect.pdf[/url]