Msieve / lattice siever with degree 7/8 poly

[miklin]

Here still easy changes for Pol5 Experimental. Now Pol5 equally works Unix FreeBSD, Linux DEBIAN, together with for windows. Thus I in all cases collect the program without the assembler. To sense from it practically is not present.

For windows in root VC9 it is necessary to make still a file rint.h

rint.h

#ifndef __RINT_H__
#define __RINT_H__

double rint(double);
float rintf(float);

#endif

[XYYXF]

Originally Posted by xilman

Because they are hopelessly inefficient for numbers of the size presently amenable to SNFS.

Exercise: for an integer from one of the classes you describe, with SNFS difficulty 300 digits or under, compare the norms of the linear and octic sides for a typical sieving point. Post your results here.


Paul

Let's take a 241-digit composite number (a wanted one from the XYYXF project)

125^84 + 84^125

and compare the following poly's:

C241 = 25*(5^50)^5 + (84^25)^5
84*C241 = 84*(5^42)^6 + (84^21)^6
84*С241 = 84*(5^36)^7 + (84^18)^7

I guess the second would be the best one...

[Batalov]

=>

[bdodson]

Originally Posted by xilman

Because they are hopelessly inefficient for numbers of the size presently amenable to SNFS.

Exercise: for an integer from one of the classes you describe, with SNFS difficulty 300 digits or under, compare the norms of the linear and octic sides for a typical sieving point. Post your results here.


Paul

OK, now that we have

2,2190L c163 = p75 . p89

done with octic polyn (and better than the alternatives, including
gnfs), what happened to the norm comparison? -Bruce

(cf. http://mersenneforum.org/showthread.php?t=12481 from the Cunningham
thread, which has Serge's version)

[xilman]

Originally Posted by bdodson

OK, now that we have

2,2190L c163 = p75 . p89

done with octic polyn (and better than the alternatives, including
gnfs), what happened to the norm comparison? -Bruce

(cf. http://mersenneforum.org/showthread.php?t=12481 from the Cunningham
thread, which has Serge's version)

Fair point. I concede that in very special circumstances septics and octics can be better than the very unpalatable alternatives and that the size of the norms is not the only criterion to use. However, that number demonstrates a "very special circumstances nicely, as was made clear all along.


Paul

[chris2be8]

Roughly where would be the crossover point where an octic would be faster that a quartic? Also, where would be the crossover points between GNFS and septics or octics? This assumes they are above the point where QS is better than NFS. Chris K

[R.D. Silverman]

Originally Posted by chris2be8

Roughly where would be the crossover point where an octic would be faster that a quartic? Also, where would be the crossover points between GNFS and septics or octics? This assumes they are above the point where QS is better than NFS. Chris K

Go read my paper Optimal Parameterization of SNFS in J. Math. Cryptology

[fivemack]

You keep saying this; the paper isn't terribly easy to get hold of, and the question of where exactly the crossovers lie is one that relies on properties of the lattice-sieving software measuring which is much harder than figuring out the positions of the crossovers empirically - for example, I suspect the paper assumes you can pick the area to sieve arbitrarily, whilst with the tools that everyone uses you have a choice of three areas.

[Mini-Geek]

Originally Posted by fivemack

You keep saying this; the paper isn't terribly easy to get hold of,

Actually, this one is easy to find (though many other papers are not). A simple Google search of the title, exactly as he gave it, lists a PDF of it at number 4.
I'm not at all refuting the rest of your statement though.

[R.D. Silverman]

Originally Posted by fivemack

You keep saying this; the paper isn't terribly easy to get hold of, and the question of where exactly the crossovers lie is one that relies on properties of the lattice-sieving software measuring which is much harder than figuring out the positions of the crossovers empirically - for example, I suspect the paper assumes you can pick the area to sieve arbitrarily, whilst with the tools that everyone uses you have a choice of three areas.

Of course the paper is available! Just ask me and I will send a pdf.

And the fact that the tools are self-limiting has nothing to do with
the best choice of degree. Tools can be changed.

Your use of the words "exactly where the crossovers lie" is nonsense.
There is no exact point. The optimal polynomial degree is
d = (3 log N/loglog N)^1/2. This is never an integer for integer N.

There is (say) a fairly narrow range where (say) degree 6 is optimal.
But "degree 6" can mean anything from degree 5.5 to degree 6.5.
or maybe even from degree 5.4 to (say) 6.7.

There is no sharp delineation in going from degree 6 to degree 7.
d, as a function of N, changes VERY slowly.

Optimization of things like the sieve region affect ONLY the o(1) in the
exponent for the function that gives run time as a function of N.
It has virtually no effect on the choice of degree.

For N ~ 2^1024, d should be "about" 6.86. Degree 7 might be
better than degree 6. Or it might not. For N = 2^768, d is 6.33.

To get d ~ 8 requires N > 2^1536.

[fivemack]

[QUOTE=R.D. Silverman;194530]Your use of the words "exactly where the crossovers lie" is nonsense.
There is no exact point. The optimal polynomial degree is
d = (3 log N/loglog N)^1/2. This is never an integer for integer N. [/QUOTE]

But, in the common SNFS case where you're dealing with something that has algebraic factors, you have a number of (N,d) pairs and have to decide which one to use; N may well be large enough for the optimal degree to be six, but have no degree-6 polynomial with small coefficients.

I would say that the question of whether to use a quartic and complexity 220 digits or an octic and complexity 175 digits for SNFS is one where o(1) terms are the only determining factor, and experiment is much easier than carrying the analytic approach to a sufficient level of exactness.