Msieve / lattice siever with degree 7/8 poly

[R.D. Silverman]

Originally Posted by fivemack

[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.

"Easier" is in the eye of the beholder.

For myself, I just look at the (size of the) norms.

[Andi47]

Originally Posted by R.D. Silverman

The optimal polynomial degree is
d = (3 log N/loglog N)^1/2.

Huh? Seems I am getting something wrong here:

I assume N means the number to be factored?

"3 log N" - meaning 3*log(N)? log to which base? e? 10? Or log(N, base 3)?

loglog N = log(log(N))? Base e? Base 10?

When I type into excel: "=(LOG(B4;3)/LOG(LOG(B4;EXP(1));EXP(1)))^0,5", with B4 being 1e100, I get d=6.2075... - but according to experimental data, quartics are slightly faster than quintics for 100-digit-GNFS. So it seems I got something wrong, but I don't see, what?

[jasonp]

Originally Posted by Andi47

loglog N = log(log(N))? Base e? Base 10?

Yes. The base of the logarithm doesn't matter, because one base is a constant factor different from any other base, and asymptotic notation doesn't care about constant factors. This is why you see the complexity for many divide-and-conquer algorithms expressed in terms of log(N) (meaning base e), when the derivation of the algorithm aways assumes a base-2 logarithm.

[Andi47]

Originally Posted by jasonp

Yes. The base of the logarithm doesn't matter, because one base is a constant factor different from any other base, and asymptotic notation doesn't care about constant factors. This is why you see the complexity for many divide-and-conquer algorithms expressed in terms of log(N) (meaning base e), when the derivation of the algorithm aways assumes a base-2 logarithm.

So the correct formula (in Excel-format) would be

=(LOG(B4;3)/(LOG(LOG(B4;2);2)))^0,5

?

(for 10^100, this one gives a value of 5.002. Note: In Excel, LOG(x;y) means "log of x to the base y".)

(BTW: Reading "3 log N" as "3*log(N) to the base 2" gives a value of ~10.9; taking all log's to base 10 gives 12.2 for the same input - so I assume, that this would be very wrong??)

[axn]

Originally Posted by R.D. Silverman

The optimal polynomial degree is
d = (3 log N/loglog N)^1/2

Wikipedia says that should be 1/3 and not 1/2 - http://en.wikipedia.org/wiki/Special..._of_parameters

[R.D. Silverman]

Originally Posted by Andi47

Huh? Seems I am getting something wrong here:

I assume N means the number to be factored?

"3 log N" - meaning 3*log(N)? log to which base? e? 10? Or log(N, base 3)?

loglog N = log(log(N))? Base e? Base 10?

When I type into excel: "=(LOG(B4;3)/LOG(LOG(B4;EXP(1));EXP(1)))^0,5", with B4 being 1e100, I get d=6.2075... - but according to experimental data, quartics are slightly faster than quintics for 100-digit-GNFS. So it seems I got something wrong, but I don't see, what?

I had a TYPO. The exponent is not 1/2, it is 1/3.

MEA CULPA.

[R.D. Silverman]

Originally Posted by axn

Wikipedia says that should be 1/3 and not 1/2 - http://en.wikipedia.org/wiki/Special..._of_parameters

And it would be correct.

[chris2be8]

Originally Posted by R.D. Silverman

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

I have read that, but it doesn't give answers to the exact questions I asked. I was wanting a rough estimate as to how large a number has to be before it's worth testing the octic against the quartic (assuming both are the same size). Chris K

[R.D. Silverman]

Originally Posted by chris2be8

I have read that, but it doesn't give answers to the exact questions I asked. I was wanting a rough estimate as to how large a number has to be before it's worth testing the octic against the quartic (assuming both are the same size). Chris K

Take a 'typical' lattice point. Look at the size of the product of the two
norms at that lattice point for each of the quartic and octic cases.

For the octic, you definitely want to do the special-q on the algebraic side.

[Batalov]

Note that for 2,2190L the targets for octic and quartic were of different difficulty; so for that quartic/octic crossover comparison it is not the poster case.

Also note that all 'currently doable' reciprocal octics are better re-dressed as quartics (e.g. the case of any 2L/M with index divisible by 5, and any 10L/M, all of them in the current list); and any even quartic (essentially, quadratic) can be made into a sextic, and all other quartics can be made into octics which will not make sense until diff.>>300.

There is a dead zone in quartics above diff.233. Take for example the attractive 2,2334M which has no known non-alg. factors. Sieve tests show that it goes worse than a sextic of diff.270, and above this size this situation is going to get worse and worse.

Always do simulation runs (a.k.a. "sims").


My 2 cents. --Serge

[chris2be8]

Thanks Serge, that was what I wanted to know. Chris K