SNFS Polynomial selection help?

[chris2be8]

Hello,

I may have some free time to look at this over the vacation. Would it be a good idea to calculate the norms on each side and then calculate alim, lpba and mfba from the algebraic norm and rlim, lpbr and mfbr from the rational norm? I assume I would need to choose the lattice siever first.

If so how do the intermediate coefficients affect the algebraic norm? And would the same formula work for both SNFS and GNFS (the latter has much large norms because of the larger coefficients)?

Chris

[chris2be8]

Originally Posted by Dubslow

What's akruppa's "phi" program that chris2be8 rcv mentioned in the Brent thread? Is the source available somewhere? Thanks guys!

You can get it from http://mersenneforum.org/showthread.php?t=8739 (it's one of the similar threads listed at the bottom of the Factoring homogeneous Cunningham numbers thread).

I compiled it with:
tar xvf phi.0.1.3.tar.gz
gcc phi.c -lgmp -lm -o phi

To generate a poly for (24^67+5^67)/13493315083 I ran:
./phi 134 24 5 22081803097132032256486568519444965996380746891798405755052870029145047511501470103

To generate one for a Cunningham number make b 1. Eg for (696938683170582386201^7-1)/54493764266182201718944448414756968251400:
./phi 7 696938683170582386201 1 1465599082456478076946725891545432506127193661953458301768102866613525151251968270225872723103940096294781

Caveat. I've not actually tried to factor a number with a poly generated by phi yet, I've just been playing with it.

Chris

[chris2be8]

After writing a script to use phi to generate polys for small homogeneous Cuningham numbers in factordb I hit this for some of them:

 phi 90 651 284 5663790649054676349338442606968436807926027172815764988867085841323599706880692753280562939159184291693007
Error: M=4939198685746927329490603692403676994091362962214535817635398875355996312522831784528147891822096002650174 is not a root of f(x) % N
f(x) = 1*x^4 +1*x^3 +-4*x^2 +-4*x^1 +1*x^0 +
Remainder is 1460793462638548321254957033717288119958870231323027169252484192090120338962999641282858053293770771101570
651^45+284^45
Please report this bug.

phi 240 23 22 3459763235540435515380117787482876803411779315115972153149434378979474683803167421333756323264743057977761
Error: M=5703809342686635137462648724698972850980174560505230532251746794376233302978558305846851719111509347397106 is not a root of f(x) % N
f(x) = 1*x^4 +1*x^3 +-4*x^2 +-4*x^1 +1*x^0 +
Remainder is 2848028061511906099979356783663176189183847581835755485999276693372124292261373507114546936316885785599299
23^120+22^120
Please report this bug.

It only seems to happen for exponents with a small odd factor, 3 or 5. It doesn't always happen though, some multiples of 3 and 5 work.

But I've generated enough polys to make it useful despite that. I've not tried to use any of the polys it generates yet, I'll see what happens when they reach the top of the queue.

Chris

PS. Should phi be moved to the factoring tools thread? And are there any other tools to generate SNFS polys that should be listed in it.

[jyb]

Originally Posted by chris2be8

After writing a script to use phi to generate polys for small homogeneous Cuningham numbers in factordb I hit this for some of them:

 phi 90 651 284 5663790649054676349338442606968436807926027172815764988867085841323599706880692753280562939159184291693007
Error: M=4939198685746927329490603692403676994091362962214535817635398875355996312522831784528147891822096002650174 is not a root of f(x) % N
f(x) = 1*x^4 +1*x^3 +-4*x^2 +-4*x^1 +1*x^0 +
Remainder is 1460793462638548321254957033717288119958870231323027169252484192090120338962999641282858053293770771101570
651^45+284^45
Please report this bug.

phi 240 23 22 3459763235540435515380117787482876803411779315115972153149434378979474683803167421333756323264743057977761
Error: M=5703809342686635137462648724698972850980174560505230532251746794376233302978558305846851719111509347397106 is not a root of f(x) % N
f(x) = 1*x^4 +1*x^3 +-4*x^2 +-4*x^1 +1*x^0 +
Remainder is 2848028061511906099979356783663176189183847581835755485999276693372124292261373507114546936316885785599299
23^120+22^120
Please report this bug.

It only seems to happen for exponents with a small odd factor, 3 or 5. It doesn't always happen though, some multiples of 3 and 5 work.

But I've generated enough polys to make it useful despite that. I've not tried to use any of the polys it generates yet, I'll see what happens when they reach the top of the queue.

Chris

PS. Should phi be moved to the factoring tools thread? And are there any other tools to generate SNFS polys that should be listed in it.

The problem is that you haven't divided out the algebraic factors of your composite. phi assumes that the algebraic factors which it uses have already been divided out of the number you give it, and it gets a bit cranky if they haven't (as you've discovered). In your case, the primitive part of (651^45 + 284^45) is

(651^45 + 284^45)(651^3 + 284^3)
------------------------------------------
(651^15 + 284^15)(651^9 + 284^9)

This is 36335593171252413192330852330921185601404243579981300933923610467681, a number far smaller than the one you were apparently trying to factor. If you feed it to phi it will work just fine. (Though of course you probably don't want to bother finding an SNFS polynomial for a 68-digit number, particularly one that happens to have a 12-digit factor.)

Bottom line: before doing any factoring work you should always make sure you've found algebraic factors first.

[jyb]

By the way, Chris, you may want to have a look at this:

http://mersenneforum.org/showpost.ph...29&postcount=5

It looks like you're probably "the guy" being referenced.

[chris2be8]

Thanks for pointing me in the right direction. I had written code to check for algebraic factors, but forgot perl uses ** for exponentiation instead of ^. It's odd that $alg_n = $aa^$alg_exp; does not produce any error message though, even with use warnings and use strict.

NB. I'm not adding homogeneous Cunningham numbers to factordb, I'm factoring the ones someone else had added. So I'm not "the guy".

Chris

[jyb]

Originally Posted by chris2be8

Thanks for pointing me in the right direction. I had written code to check for algebraic factors, but forgot perl uses ** for exponentiation instead of ^. It's odd that $alg_n = $aa^$alg_exp; does not produce any error message though, even with use warnings and use strict.

NB. I'm not adding homogeneous Cunningham numbers to factordb, I'm factoring the ones someone else had added. So I'm not "the guy".

Chris

Okay. BTW, one thing you should be aware of if you're using phi: for exponents that are divisible by 3 (but not 15 or 21), phi will want to make a quartic, rather than a sextic. And if you try to force it to make a sextic (with -deg6) then it won't use the algebraic factor at all, so the SNFS difficulty will be 50% larger than it should be.

That might be fine for the numbers you're doing, if they're relatively small. But if you get to bigger numbers, quartics would be a pain. You can always make the polynomial by hand, of course. But I've modified phi for my own use so that it will use the algebraic factor when you force it to use a sextic polynomial.

[BudgieJane]

Originally Posted by chris2be8

NB. I'm not adding homogeneous Cunningham numbers to factordb, I'm factoring the ones someone else had added. So I'm not "the guy".

Chris

So what are the rules for adding homogeneous Cunningham numbers to factordb?

[henryzz]

Originally Posted by BudgieJane

So what are the rules for adding homogeneous Cunningham numbers to factordb?

Add the algebraic factors so work isn't wasted is a good start.

[chris2be8]

Has anyone got a poly they know the algebraic and rational norms for? I've written code to calculate them, but I'm not sure of the results. All the SNFS polys I've tried the rational norm comes out higher, even the sextic 48165336887100010891^7-1 with siever gnfs-lasieve4I12e gets:

-> Algebraic norm is 9.37094598944445e+21. Rational norm is 9.86426099447808e+22.

Which seems odd. I would expect a SNFS 118 digit sextic to have the algebraic norm larger.

Chris

[R.D. Silverman]

Originally Posted by chris2be8

Has anyone got a poly they know the algebraic and rational norms for? I've written code to calculate them, but I'm not sure of the results. All the SNFS polys I've tried the rational norm comes out higher, even the sextic 48165336887100010891^7-1 with siever gnfs-lasieve4I12e gets:

-> Algebraic norm is 9.37094598944445e+21. Rational norm is 9.86426099447808e+22.

A norm is evaluated at some lattice point. What point is being
used to give these numbers (above)?

The algebraic norm will vary widely over the lattice.

A "typical" lattice point is (say) [10^6, 10^6]. From this, we expect the
rational norm at this point to be about 10^6 * (10 ^(118/6)) ~ 4 x 10^25. The algebraic norm will be about (10^6)^6 ~ 10^36.
The product of these norms is ~ 4 x 10^61

A sextic is too high a degree for numbers this size.

Which seems odd. I would expect a SNFS 118 digit sextic to have the algebraic norm larger.

Chris

You are correct.