20080811, 10:03  #1 
Mar 2007
Austria
12E_{16} 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 
20080811, 13:05  #2 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×2,897 Posts 

20080811, 13:39  #3 
"Ben"
Feb 2007
3,361 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 20080811 at 13:40 Reason: c0, not c1 
20080811, 13:44  #4 
Mar 2004
Belgium
839 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 10^1637^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 20080811 at 13:52 
20080811, 14:22  #5 
Mar 2007
Austria
2·151 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 
20080811, 14:39  #6  
"Ben"
Feb 2007
D21_{16} Posts 
Quote:
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 20080811 at 14:51 

20080811, 16:04  #7  
Nov 2003
16444_{8} Posts 
Quote:
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. 

20080811, 16:06  #8  
Nov 2003
2^{2}·5·373 Posts 
Quote:
Hint: compare the sizes of the rational & algebraic norms. 

20080811, 18:12  #9  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3^{3}×389 Posts 
Quote:
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 

20080811, 18:14  #10 
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 
20080811, 18:28  #11  
Nov 2003
16444_{8} Posts 
Quote:
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. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
snfs for homogeneous cunninghams with a,b>12  BudgieJane  YAFU  5  20170519 23:54 
New phi for homogeneous Cunningham numbers  wpolly  Factoring  26  20160729 04:34 
Fix for homogeneous cunningham polynomials  frmky  YAFU  1  20160414 13:35 
GNFS poly selection  frmky  Factoring  14  20120723 01:57 
poly selection in MPQS  bsquared  Factoring  3  20070228 14:22 