mersenneforum.org Factoring humongous Cunningham numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

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

May 2003
Down not across

984010 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 6010 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 5816 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

Nov 2003

737510 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/?

Go right ahead.

 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

Nov 2003

53·59 Posts

Quote:
 Originally Posted by Andreas Schinde (P.S.: This should read 379 (1) 5.C181 ;-) )
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.

 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

22·5·281 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

Nov 2003

53·59 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 2·193 Posts 400 (16,80) 19995617469086942401.C134 19995617469086942401 = 4388625601 x 4556236801

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post wpolly Factoring 26 2016-07-29 04:34 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 00:15.

Thu Apr 2 00:15:18 UTC 2020 up 7 days, 21:48, 3 users, load averages: 0.94, 1.05, 1.15

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.