mersenneforum.org Factoring humongous Cunningham numbers
 Register FAQ Search Today's Posts Mark Forums Read

2006-04-11, 18:07   #23
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·5,791 Posts

Quote:
 Originally Posted by smh Can somenody explain me how to create a SNFS polynomial for these numbers?
Here's a clue: it should be all you need.

Given a^n \pm b^n == 0 mod N, divide by b^n to get (a/b)^n \pm 1 == 0 mod N. You've now got exactly the same form as for the regular Cunningham tables.

Purists can witter on about multiplicative inverses and whether they exist mod N. Such purists will also realize that if the inverse can't be found by the extended GCD algorithm a factorization of N is at hand anyway.

Paul

 2006-04-11, 20:00 #24 Jushi     Sep 2005 UGent 748 Posts Bob, would you mind if I also put a copy online at my page http://cage.ugent.be/~jdemeyer/cunningham/?
 2006-04-12, 07:19 #25 Pascal Ochem     Apr 2006 2×53 Posts The factors of the C98 from 3^349-2^349 are: 4168235213414369860712355318929423366202629 (pp43) 6054961803389403532431183517420804533418860819773628313 (pp55)
2006-04-12, 08:16   #26
Andi47

Oct 2004
Austria

2·17·73 Posts

Quote:
 Originally Posted by Pascal Ochem The factors of the C98 from 3^349-2^349 are: 4168235213414369860712355318929423366202629 (pp43) 6054961803389403532431183517420804533418860819773628313 (pp55)
pp = possible prime?

Edit: Primo certifies both factors as prime within a split second

Last fiddled with by Andi47 on 2006-04-12 at 08:20

2006-04-12, 10:37   #27
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010010002 Posts

Quote:
 Originally Posted by Jushi Bob, would you mind if I also put a copy online at my page http://cage.ugent.be/~jdemeyer/cunningham/?

 2006-04-12, 12:16 #28 Andi47     Oct 2004 Austria 2×17×73 Posts Done 648 curves on 3^379+2^379 using GMP-ECM at B1=1e6 and B2=default, no factor found. Together with Silverman's ~300 curves this should have finished the 35 digit range. (P.S.: This should read 379 (1) 5.C181 ;-) ) Now running a some curves with B1=3e6 at this number. I have also done 300 curves on the C144 of 3^395-2^395, no factor found. Last fiddled with by Andi47 on 2006-04-12 at 12:20
2006-04-12, 12:46   #29
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts

Quote:
 Originally Posted by Andreas Schinde (P.S.: This should read 379 (1) 5.C181 ;-) )
Not really.

N (a,b,c...) means that 3^N + 2^N has the algebraic factors
3^a + 2^a, 3^b + 2^b, etc.

So

379 (1) C181 means that 3^379 + 2^379 has the algebraic factor
of 3^1 + 2^1. 5 is an algebraic factor. Algebraic factors do not get
directly listed. The exponents for the algebraic factors are listed inside
the parentheses.

 2006-04-12, 15:42 #30 Greenbank     Jul 2005 2·193 Posts Ah, I did wonder. Knowledge gained and all of that...
2006-04-12, 15:56   #31
rogue

"Mark"
Apr 2003
Between here and the

152538 Posts

Quote:
 Originally Posted by R.D. Silverman Not really. I follow the Cunningham format: N (a,b,c...) means that 3^N + 2^N has the algebraic factors 3^a + 2^a, 3^b + 2^b, etc. So 379 (1) C181 means that 3^379 + 2^379 has the algebraic factor of 3^1 + 2^1. 5 is an algebraic factor. Algebraic factors do not get directly listed. The exponents for the algebraic factors are listed inside the parentheses.
Bob, I had a question on regarding your data. Do you care if all of the factors found are prime or not? I'm asking because I believe that one of the factors you listed above was composite.

2006-04-12, 16:23   #32
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts

Quote:
 Originally Posted by rogue Bob, I had a question on regarding your data. Do you care if all of the factors found are prime or not? I'm asking because I believe that one of the factors you listed above was composite.
It is quite possible. I have not checked them.

Which factor?

 2006-04-12, 17:49 #33 Greenbank     Jul 2005 1100000102 Posts 400 (16,80) 19995617469086942401.C134 19995617469086942401 = 4388625601 x 4556236801

 Similar Threads Thread Thread Starter Forum Replies Last Post wpolly Factoring 29 2022-10-25 00:46 Xyzzy Cunningham Tables 42 2014-04-02 18:31 jasong GMP-ECM 6 2006-06-30 08:51 jasong Factoring 1 2006-04-03 17:18 jasong Factoring 27 2006-03-21 02:47

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

Sun Dec 4 12:00:54 UTC 2022 up 108 days, 9:29, 0 users, load averages: 1.19, 0.92, 0.90