mersenneforum.org Homogeneous Cunningham snfs poly selection?
 Register FAQ Search Today's Posts Mark Forums Read

 2008-08-11, 10:03 #1 nuggetprime     Mar 2007 Austria 2·151 Posts Homogeneous Cunningham snfs poly selection? 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
 2008-08-11, 13:05 #2 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 10110011000112 Posts
 2008-08-11, 13:39 #3 bsquared     "Ben" Feb 2007 CDF16 Posts 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. Last fiddled with by bsquared on 2008-08-11 at 13:40 Reason: c0, not c1
 2008-08-11, 13:44 #4 ValerieVonck     Mar 2004 Belgium 34516 Posts Hi, I tried with the following: Code: 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 Code:  76454998044382118209179706836357299485120398118720870657181486936302021736154666930305964717030600697798632171689 Code: 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! Last fiddled with by ValerieVonck on 2008-08-11 at 13:52
 2008-08-11, 14:22 #5 nuggetprime     Mar 2007 Austria 30210 Posts 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
2008-08-11, 14:39   #6
bsquared

"Ben"
Feb 2007

5×659 Posts

Quote:
 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.

Last fiddled with by bsquared on 2008-08-11 at 14:51

2008-08-11, 16:04   #7
R.D. Silverman

Nov 2003

161008 Posts

Quote:
 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.

2008-08-11, 16:06   #8
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 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.

2008-08-11, 18:12   #9
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2·3·5·337 Posts

Quote:
 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

 2008-08-11, 18:14 #10 nuggetprime     Mar 2007 Austria 2·151 Posts @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
2008-08-11, 18:28   #11
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post BudgieJane YAFU 5 2017-05-19 23:54 wpolly Factoring 26 2016-07-29 04:34 frmky YAFU 1 2016-04-14 13:35 frmky Factoring 14 2012-07-23 01:57 bsquared Factoring 3 2007-02-28 14:22

All times are UTC. The time now is 05:30.

Wed Oct 21 05:30:01 UTC 2020 up 41 days, 2:40, 0 users, load averages: 1.73, 1.51, 1.46