mersenneforum.org any suitable sieve written in C or Python?
 Register FAQ Search Today's Posts Mark Forums Read

 2017-01-05, 03:16 #1 Shen   Jan 2017 38 Posts any suitable sieve written in C or Python? It is well known that if q | 2^p - 1, then q = 2px + 1 and q = 8r +(-) 1. when I do some research on Fp (Fibonacci prime), I guess : 1: if q | Fp, then q = 2px + (-1)^x 2: F(2n+1) must have a prime factor q, q = 2(2n+1)x + (-1)^x 3: ... At this moment , I try to factor C261 ( F1565 = F5* F313 * C261), which has 261 digital. If guess is right, then C261 must have a prime factor = 2*1565*x + (-1)^x. The GIMPS factoring code creates a modified sieve of Eratosthenes with each bit representing a potential 2kp+1 factor. The sieve then eliminates any potential factors that are divisible by prime numbers below 40,000 or so. Also, bits representing potential factors of 3 or 5 mod 8 are cleared. This process eliminates roughly 95% of potential factors. Since I don't know assemble language, I could not understand such code. I tried to code it by myself, but the code efficiency is very low. I have no other good choice but ask for help : Could someone provide a efficient sieve ? Thanks a lot!
 2017-01-05, 04:19 #2 carpetpool     "Sam" Nov 2016 2×163 Posts Didn't you get the idea from here?
2017-01-05, 04:34   #3
axn

Jun 2003

484510 Posts

Quote:
 Originally Posted by Shen At this moment , I try to factor C261 ( F1565 = F5* F313 * C261), which has 261 digital. If guess is right, then C261 must have a prime factor = 2*1565*x + (-1)^x.
Trial factoring is the wrong tool for numbers this size. You should use ECM.

Last fiddled with by axn on 2017-01-05 at 04:35 Reason: speeling

2017-01-05, 04:42   #4
carpetpool

"Sam"
Nov 2016

2×163 Posts

Quote:
 Originally Posted by axn Trial factoring is the wrong tool for numbers this size. You should use ECM.
YAFU?

 2017-01-05, 04:49 #5 Shen   Jan 2017 3 Posts Thanks for your advice.

 Similar Threads Thread Thread Starter Forum Replies Last Post Godzilla Miscellaneous Math 40 2018-10-17 00:11 jasong Homework Help 3 2015-01-30 21:36 TTn 15k Search 3 2006-01-06 00:08 a216vcti Programming 7 2005-10-30 00:37 garo Lone Mersenne Hunters 1 2003-09-10 21:10

All times are UTC. The time now is 10:18.

Sun Jan 24 10:18:15 UTC 2021 up 52 days, 6:29, 0 users, load averages: 2.22, 2.04, 1.99