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

A Very nice piece of work. Kudos.

[QUOTE=R.D. Silverman;250316]A Very nice piece of work. Kudos.[/QUOTE]Indeed. thanks, Tom, for drawing it to our attention.

Paul

[QUOTE=jasonp;250291]I have no idea how one can find a SNFS polynomial pair with a nonlinear rational poly.[/QUOTE]
That seems easy. If you take [TEX]f(x)=ax^b-1[/TEX] and [TEX]g(x)=x^c-d[/TEX], then the resultant is [TEX]a^cd^b-1[/TEX]. OTOH finding an optimal pair may be harder. For example, [TEX]f(x)=2^{134}x^3-1[/TEX], [TEX]g(x)=x^4-2^{175}[/TEX] is one pair that could be used to factor [TEX]2^{1061}-1[/TEX], but there are many others (like [TEX]f(x)=2^{152}x^3-1[/TEX], [TEX]g(x)=x^4-2^{151}[/TEX]), and choosing the best of these might be quite difficult.

In the M1061 case, how do the norms compare across the choices available? I realize it's kind of a judgment call because smaller degree starts off with large coefficients but grows more slowly as the sieving region moves away from the origin.

How did the resultant get into this discussion? Is this the secret decoder ring, and any two polynomials can be used to NFS factor their resultant?

I've reread C&P to see if I missed it, but I don't see resultant mentioned. C&P says "f(x) and g(x) and an integer m with f(m) = g(m) = 0 (mod n)." Your examples fit this, with m=2^309 and m=2^303, so you got to the same place.

Any recommended resources to learn the relevant facts about resultants?

[QUOTE=wblipp;250723]How did the resultant get into this discussion? Is this the secret decoder ring, and any two polynomials can be used to NFS factor their resultant?[/QUOTE]
Almost. Let f(x) and g(x) be any polynomials and N any integer; then Res(f,g)=0 (mod N) if and only if f and g have a common factor modulo N. That doesn't guarantee it's a linear factor (which you need for NFS), but that's easy to check once you have the polynomials (take their GCD).

[QUOTE=jasonp;250689]In the M1061 case, how do the norms compare across the choices available? I realize it's kind of a judgment call because smaller degree starts off with large coefficients but grows more slowly as the sieving region moves away from the origin.[/QUOTE]
I don't know, but I guess that double nonlinear polynomials may not be very competitive with Cunningham numbers; the regions where each polynomial has small norms are pretty much orthogonal, so the combined region of smallness is small. Homogeneous Cunningham numbers look like better candidates; [TEX]a^d-b^d[/TEX]can be sieved with [TEX]f(x)=x^d-a[/TEX] and [TEX]g(x)=x^d-b[/TEX], and they have nearly identical regions of small norms, so it should be quick to get the needed relations. The [TEX]x^y-y^x[/TEX] numbers also appear promising.

Pascal or William,

Do either of you have the full factorization of: [(195163150047313020008802835877656364030813707064261)^5-1]/[195163150047313020008802835877656364030813707064261-1] ?

Thanks,
Zeta-Flux

The only factors I have are 5, 11, and 5582516651485570586701.
This number is in the tree of 97, so it is not needed for me: the factor 11 is forbidden at this point of the proof.
Thus, the composite cofactor might have received only few ECM. I started ECM on it at 3e6.

Does anyone happen to have an implementation of Bernstein's factoring with product trees lying around somewhere? It doesn't have to be exceptionally fast, just work. I want to divide known factors out of t1200.txt.

[QUOTE=akruppa;250929]Does anyone happen to have an implementation of Bernstein's factoring with product trees lying around somewhere? It doesn't have to be exceptionally fast, just work. I want to divide known factors out of t1200.txt.[/QUOTE]I've downloaded t1200.txt and converted it to my standard format. From there, the toolkit which I've developed over the last 10 years or so will be able to process it in a bunch of different ways. Right now ECM with B1=10k is running on the file, not because any factors are expected but just to ensure the format conversion worked properly.

Already sent you an email about what you mean by "known factors".

Paul