mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-08-11, 10:03   #1
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2·151 Posts
Default 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
nuggetprime is offline   Reply With Quote
Old 2008-08-11, 13:05   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

130348 Posts
Default

http://www.mersenneforum.org/showthread.php?t=8739
henryzz is offline   Reply With Quote
Old 2008-08-11, 13:39   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

324610 Posts
Default

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
bsquared is offline   Reply With Quote
Old 2008-08-11, 13:44   #4
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

33·31 Posts
Default

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
ValerieVonck is offline   Reply With Quote
Old 2008-08-11, 14:22   #5
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

4568 Posts
Default

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
nuggetprime is offline   Reply With Quote
Old 2008-08-11, 14:39   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·3·541 Posts
Default

Quote:
Originally Posted by nuggetprime View Post
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
bsquared is offline   Reply With Quote
Old 2008-08-11, 16:04   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23×32×103 Posts
Default

Quote:
Originally Posted by nuggetprime View Post
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 is offline   Reply With Quote
Old 2008-08-11, 16:06   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23×32×103 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
R.D. Silverman is offline   Reply With Quote
Old 2008-08-11, 18:12   #9
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

23×1,249 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
xilman is offline   Reply With Quote
Old 2008-08-11, 18:14   #10
nuggetprime
 
nuggetprime's Avatar
 
Mar 2007
Austria

2×151 Posts
Default

@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
nuggetprime is offline   Reply With Quote
Old 2008-08-11, 18:28   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23·32·103 Posts
Default

Quote:
Originally Posted by xilman View Post

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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
snfs for homogeneous cunninghams with a,b>12 BudgieJane YAFU 5 2017-05-19 23:54
New phi for homogeneous Cunningham numbers wpolly Factoring 26 2016-07-29 04:34
Fix for homogeneous cunningham polynomials frmky YAFU 1 2016-04-14 13:35
GNFS poly selection frmky Factoring 14 2012-07-23 01:57
poly selection in MPQS bsquared Factoring 3 2007-02-28 14:22

All times are UTC. The time now is 07:46.

Sun May 31 07:46:44 UTC 2020 up 67 days, 5:19, 1 user, load averages: 1.67, 1.49, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.