Homogeneous Cunningham snfs poly selection?

[nuggetprime]

Today I've reserved the homogeneous cunningham number 11^151+2^151 for SNFS.
Now i have to select the snfs polynomial. How do I compute it? for a^b+c it's clear to me, but not for a^n+b^n. Hopefully you can help me.

Regards,
nuggetprime

[henryzz]

http://www.mersenneforum.org/showthread.php?t=8739

[bsquared]

for a^n +/- b^n, first divide through by b^n to get (a/b)^n +/- 1

The algebraic polynomial for this is exactly the same as for a regular cunningham, and the rational poly is also just x - m. You don't need to explicitly do the modular division to form the polynomial.

Example, 12^179 - 7^179:

target degree 5, so multiply by (12*7) to tweak the exponent
7*12^180 - 12*7^180

divide through
7*(12/7)^180 - 12

now m = (12/7)^36 so we have on the algebraic side
7*m^5 - 12

and the linear side is
x - m => x - (12/7)^36 =>
(7^36)*x - 12^36

in ggnfs format this is
c5: 7
c0: -12
Y1: 2651730845859653471779023381601
Y0: -708801874985091845381344307009569161216

hope this helps.

[ValerieVonck]

Hi,

I tried with the following:

phi -deg5 -ggnfs 10 163 764549980
44382118209179706836357299485120398118720870657181486936302021736154666930305964
717030600697798632171689
     23 [main] phi 1064 handle_exceptions: Exception: STATUS_ACCESS_VIOLATION
    625 [main] phi 1064 open_stackdumpfile: Dumping stack trace to phi.exe.stack

I have cygwin1.dll & cyggmp3.dll in the same dir :s
10^163-7^163

 76454998044382118209179706836357299485120398118720870657181486936302021736154666930305964717030600697798632171689

Exception: STATUS_ACCESS_VIOLATION at eip=100116B0
eax=10011690 ebx=00000000 ecx=0000000C edx=610E207F esi=004016C8 edi=610E21A0
ebp=0022EBE8 esp=0022EBB0 program=C:\Documents and Settings\vonckce\Desktop\test\phi.exe, pid 1064, thread main
cs=001B ds=0023 es=0023 fs=0038 gs=0000 ss=0023
Stack trace:
Frame     Function  Args
0022EBE8  100116B0  (0022EE00, 00000000, 0000000A, 004016F7)
0022EE78  00401AD0  (00000004, 100301E8, 10030090, 61089F80)
0022EFD8  61004DD2  (0022EFF0, FFFFFFFF, 0022F22C, 7C2D3C67)
0022FF88  6100594F  (00000000, 00000000, 00000000, 00000000)
End of stack trace

Can please help me with error???

Thank you in advance!

[nuggetprime]

Ok, I've made now a poly for my c151:
c0=14641
c5=8
m=(11/2)^31
but there's one problem:
How do I compute Y0 and Y1?

Thanks
--nugget

[bsquared]

Originally Posted by nuggetprime

Ok, I've made now a poly for my c151:
c0=14641
c5=8
m=(11/2)^31
but there's one problem:
How do I compute Y0 and Y1?

Thanks
--nugget

Well, first I'll suggest a correction to the algebraic side poly. One can adjust the exponent either direction (see the SNFS wiki page for more details: http://www.mersennewiki.org/index.ph...mial_Selection)

so instead of multipling by (11*2)^4, just factor out an 11 and a 2 like so:
11*11^150 + 2*2^150
so that you have
11*m^5 + 2, with m = (11/2)^30
Generally you want to pick the direction of adjustment to minimize the coefficients of the polynomial.

The rational side is just x - m which is
x - (11/2)^30

simplify by multiplying the expression by 2^30 to get
(2^30)*x - 11^30

so Y1 = 2^30 and Y0 = -11^30

A program like pari/gp can evaulate multiple precision expressions like 11^30, or else try here: http://gmplib.org/#TRY

p.s. This can also be approached with a degree 4 polynomial, because 4 divides 152 which is also close to 151. The degree can make a difference depending on the size of the number to be factored. There are fuzzily defined points at which it is better to have a higher degree (if possible); with a difficulty of 157, either 4 or 5 should work fine.

[R.D. Silverman]

Originally Posted by nuggetprime

Today I've reserved the homogeneous cunningham number 11^151+2^151 for SNFS.
Now i have to select the snfs polynomial. How do I compute it? for a^b+c it's clear to me, but not for a^n+b^n. Hopefully you can help me.

Regards,
nuggetprime

What is it that compels people to dive into a research project
without first acquiring the necessary background? Your question
has been addressed in a number of publications (books & papers).

Perhaps you might deign to do (gasp!) a WEB SEARCH?

My paper: "Optimal Parameterization of SNFS" contains an answer to
your question, as well as to a number a questions that you did not
ask (but should have). I can provide other specific references.

[R.D. Silverman]

Originally Posted by bsquared

p.s. This can also be approached with a degree 4 polynomial, because 4 divides 152 which is also close to 151. The degree can make a difference depending on the size of the number to be factored. There are fuzzily defined points at which it is better to have a higher degree (if possible); with a difficulty of 157, either 4 or 5 should work fine.

NO!!!!! Degree 4 will be quite a bit slower than degree 5.
Hint: compare the sizes of the rational & algebraic norms.

[xilman]

Originally Posted by R.D. Silverman

What is it that compels people to dive into a research project
without first acquiring the necessary background? Your question
has been addressed in a number of publications (books & papers).

As a learning exercise with (at least) three results perhaps?

The first result is the acquisition of knowledge. Reading books, papers and web pages will also provide this and probably with rather better understanding.

The second result is the acquisition of skill in performing a factorization in practice. Anyone who has tried a NFS factorization knows that skill is required in addition to theory.

The third result is a factorization. To that end, it serves as a form of course credit to demonstrate to others that something has been achieved.


Paul

[nuggetprime]

@bsquared: Thanks for the friendly and helpful explanation.
@R.D.Silverman: Thanks for the hint on your paper. I found a postscript paper of it somewhere on the web. But it's containing lots of artefacts(is this often so with postscript documents?). Anyway, I'm knowing now how to select a^n+/-b^n polynomials.

Best regards,
nuggetprime

[R.D. Silverman]

Originally Posted by xilman

The second result is the acquisition of skill in performing a factorization in practice. Anyone who has tried a NFS factorization knows that skill is required in addition to theory.

The third result is a factorization. To that end, it serves as a form of course credit to demonstrate to others that something has been achieved.


Paul

I disagree. It takes virtually no skill to run a computer program
designed and written by others. One needs to learn how the algorithm
works and how/why parameters are selected before running code.

A factorization achieved by blindly running someone else's code
deserves no credit or recognition whatsoever. The only thing achieved
is the burning of some cpu cycles.