-
Notifications
You must be signed in to change notification settings - Fork 0
gkubaryk/mersenne
Folders and files
Name | Name | Last commit message | Last commit date | |
---|---|---|---|---|
Repository files navigation
'Mersenne' - Ruby script for analyzing factors found for mersenne.org The initial purpose of this script was to analyze factors that I found using mprime, a tool from mersenne.org to aid in the Great Internet Mersenne Prime Search, or GIMPS. Although the primary purpose of the GIMPS project is to find values of p for which 2^p - 1 is prime, the Fermat probable prime (PRP) test to determine primality is computationally expensive. Previously, the Lucas-Lehmer (LL) test was used, but due to lack of error detection, at least two such primality tests needed to be performed: the project needed matching outputs before the result could be considered to be official, and if the first two tests did not match, another one would have needed to be performed. Nowadays with the PRP, a proof certificate can be generated and independently verified with less than 1% of the CPU and wall time compared to a second LL test. An obvious way to avoid a primality test is to search for factors of the candidate numbers before running any PRP/LL tests. Some people also enjoy finding factors for "small" known-composite Mersenne numbers. This script currently requires a human to copy/paste entries from their mersenne.org results page. The page presents the data in a table, and the data file for this program is a tab separated file, similar to a CSV file. At present, the capabilities of this script: * Find the bit size and k-value for each factor. (All factors of Mersenne numbers can be written as: 2kp+1) * Present the data in a semi-pretty format. In the future, what will it do? Time will tell. Feel free to offer ideas! Mathematics: Although this script does not sort the factors based on how they were found, it seems relevant to mention that there are three ways to find a factor for the GIMPS project: 1. Trial factoring Brute force a given bit level (i.e., between 2^67 and 2^68) Best done by a GPU: can be done orders of magnitude faster than a CPU 2. P-1 factoring Searches for "smooth" factors below given bounds A factor's "smoothness" is determined by the prime factorization of k Stage 1 finds factors where k is a product of primes under B1 Stage 2 finds factors searching each k from Stage 1 each multiplied by a single additional product between B1 and B2 Needs a decent CPU or GPU, and for stage 2, a surplus of RAM Newer mprime can do a much larger B2 than before, without extra resources 3. ECM factoring Uses elliptic curves to find factors for small Mersenne numbers This is the probabilistic method of the three: the rest are deterministic For more information about the mathematics behind this stuff, see: https://mersenne.org/various/math.php https://mersenne.org/various/works.php
About
Script for analyzing factors found for mersenne.org
Resources
Stars
Watchers
Forks
Releases
No releases published
Packages 0
No packages published