mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-05-27, 20:14   #1
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

22×149 Posts
Default How To Calculate SNFS Poly?

How do I calculate a SNFS poly? Is there an easy formula based on N?

Last fiddled with by Stargate38 on 2015-05-27 at 20:17
Stargate38 is offline   Reply With Quote
Old 2015-05-27, 20:21   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

104A16 Posts
Default

Give an example of the form of the number you wish to factor. There are many cases.
VBCurtis is offline   Reply With Quote
Old 2015-05-27, 20:35   #3
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

59610 Posts
Default

(n2p+1)/(n2+1) with prime p
n2[SUP]x[/SUP]+1
an±bn (take out algebraic factors first)

i.e. 46074500107087988+1 (known factor before I factored it: 449). I wasted 2-3 CPU-days doing GNFS on it, before I realized that I could have done it in a matter of hours with SNFS.

Last fiddled with by Stargate38 on 2015-05-27 at 20:42
Stargate38 is offline   Reply With Quote
Old 2015-05-27, 21:30   #4
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

Have you read the Mersenne Wiki article on polynomial selection?
wblipp is offline   Reply With Quote
Old 2015-05-27, 21:47   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100111110002 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
How do I calculate a SNFS poly? Is there an easy formula based on N?
Optimal Parameterization of SNFS. J. Math. Cryptology
R.D. Silverman is offline   Reply With Quote
Old 2015-05-27, 21:52   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23×32×103 Posts
Default

Quote:
Originally Posted by Stargate38 View Post
(n2p+1)/(n2+1) with prime p
n2[SUP]x[/SUP]+1
an±bn (take out algebraic factors first)

i.e. 46074500107087988+1 (known factor before I factored it: 449). I wasted 2-3 CPU-days doing GNFS on it, before I realized that I could have done it in a matter of hours with SNFS.
May I suggest that it would be helpful if you would learn how to perform polynomial algebra??

For your first question (n^2p + 1)/(n^2+1) may I suggest performing the division and looking at the
result? One gets a dense polynomial of degree 2p-2........

n^(2^x) + 1 is algebraically prime.

for a^n +/- b^n, start by factoring it, completely. Or are you asking about the primitive cofactor?

Last fiddled with by R.D. Silverman on 2015-05-27 at 21:54
R.D. Silverman is offline   Reply With Quote
Old 2015-05-27, 22:12   #7
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Yafu can do automatic snfs poly selection for the example as well as the second two forms (though I don't know if it can take advantage of the power of 2 exponent, or if that's even possible).

Last fiddled with by Dubslow on 2015-05-27 at 22:13
Dubslow is offline   Reply With Quote
Old 2015-05-27, 23:09   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

23×32×103 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Yafu can do automatic snfs poly selection for the example as well as the second two forms (though I don't know if it can take advantage of the power of 2 exponent, or if that's even possible).
Another example of: "don't think, just throw a computer at it".

The OP asked HOW. Suggesting to use a black box does not answer that question.

Indeed. Your statement "I don't know........possible." suggests that you should not
have even tried to answer this question.

(Hint: Once you have decided the degree for the SNFS algebraic polynomial for 2^2^n+1,
it is trivial first year algebra to find the representation).
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SNFS poly for b^n-1, n prime? ryanp Factoring 6 2013-07-19 17:23
Ooops....SNFS poly for primes? schickel FactorDB 0 2011-12-16 18:07
SNFS Poly creation for n=2*x^2 - 1 JoeCrump Factoring 3 2009-10-29 21:00
Homogeneous Cunningham snfs poly selection? nuggetprime Factoring 22 2008-08-15 10:01
How do you calculate? fropones Lone Mersenne Hunters 1 2003-05-27 23:01

All times are UTC. The time now is 22:12.

Sun May 24 22:12:14 UTC 2020 up 60 days, 19:45, 0 users, load averages: 1.39, 1.32, 1.35

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.