mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2017-01-05, 03:16   #1
Shen
 
Jan 2017

3 Posts
Smile 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!
Shen is offline   Reply With Quote
Old 2017-01-05, 04:19   #2
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22·79 Posts
Post

Didn't you get the idea from here?
carpetpool is offline   Reply With Quote
Old 2017-01-05, 04:34   #3
axn
 
axn's Avatar
 
Jun 2003

5·23·41 Posts
Default

Quote:
Originally Posted by Shen View Post
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
axn is online now   Reply With Quote
Old 2017-01-05, 04:42   #4
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22·79 Posts
Post

Quote:
Originally Posted by axn View Post
Trial factoring is the wrong tool for numbers this size. You should use ECM.
YAFU?
carpetpool is offline   Reply With Quote
Old 2017-01-05, 04:49   #5
Shen
 
Jan 2017

310 Posts
Default

Thanks for your advice.
Shen is offline   Reply With Quote
Reply

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 2018-10-17 00:11
Looking for British written American history on Kindle jasong Homework Help 3 2015-01-30 21:36
Math of LLR(written by Jean Penne) TTn 15k Search 3 2006-01-06 00:08
Help w/ python. a216vcti Programming 7 2005-10-30 00:37
Available Ranges suitable for P4s garo Lone Mersenne Hunters 1 2003-09-10 21:10

All times are UTC. The time now is 01:58.

Mon Oct 26 01:58:49 UTC 2020 up 45 days, 23:09, 0 users, load averages: 1.73, 1.75, 1.68

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.