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

1001111102 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

10010101010012 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 offline   Reply With Quote
Old 2017-01-05, 04:42   #4
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

2×3×53 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

3 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 23:41.

Thu Nov 26 23:41:33 UTC 2020 up 77 days, 20:52, 4 users, load averages: 1.09, 1.07, 1.11

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.