20170105, 03:16  #1 
Jan 2017
3 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! 
20170105, 04:34  #3 
Jun 2003
2^{2}×11×107 Posts 
Trial factoring is the wrong tool for numbers this size. You should use ECM.
Last fiddled with by axn on 20170105 at 04:35 Reason: speeling 
20170105, 04:49  #5 
Jan 2017
3_{16} Posts 
Thanks for your advice.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime numbers test primality  with proof written in invisible ink  Godzilla  Miscellaneous Math  40  20181017 00:11 
Looking for British written American history on Kindle  jasong  Homework Help  3  20150130 21:36 
Math of LLR(written by Jean Penne)  TTn  15k Search  3  20060106 00:08 
Help w/ python.  a216vcti  Programming  7  20051030 00:37 
Available Ranges suitable for P4s  garo  Lone Mersenne Hunters  1  20030910 21:10 