Rationale
Theorem
Implementation
Optimising
Links
psieve is designed to be run in a command prompt on 32-bit Windows platforms only. Source code is available upon request.
This page is dedicated to hosting versions of PSieve, a program that builds sieves on the exponent n for numbers of the forms k.2^n+1 and k.2^n-1. The sieve program may also be used to find and prove values of k for which the numbers of the relevant form are always composite. Such k are called Sierpinski numbers for k.2^n+1, and Riesel numbers for k.2^n-1. With a command-line option, sieves can also be produced to accelerate the searches for twin primes of the form p=k.2^n-1 and p+2 simultaneously, and for Sophie Germain primes of the forms p=k.2^n-1 and 2p+1.
Please note that PSieve was designed as a theoretical tool, and while it may be used to sieve values of k and n for later testing, there are more efficient and effective ways to do that process.
You will notice that Marin Mersenne is peering out at you from the background. Oddly enough, Mersenne numbers are intricately bound into this problem as well!
PSieve implements a theorem that is reasonably easy to prove, which I will state here for the k.2^n+1 case. (The other case is very easily derived and simply results in a change of signs in the theorem).
For a given k, define g(x,r)=gcd(2^x-1,2^r+k), over the range 0<=r<x. If n+r=0 mod x, then g(x,r) divides k.2^n+1.
It follows then that a means of finding factors of k.2^n+1 involves looping over x and r, and performing the gcd calculation. If the gcd turns out to be greater than 1, all n congruent to -r mod x have k.2^n+1 divisible by the gcd. It also follows that since we loop on x, we find possible factors not in numerical order, but in some 'order of likelihood' - g(x,r) is a factor of k.2^n+1 for one value of n in every x. This means an efficient sieve can be built reasonably quickly, It also means that some prime factors that are never factors of k.2^n+1 are not even considered, and factors that only occur in tandem with others also need not be tested. The sieve is in many ways optimal for a particular k.
The Mersenne number M(x)=2^x-1 is very conspicuous in the form for g(x,r), and it's worth noting that g(x,r) will be a factor of M(x), although it is very unlikely this method would help in the factorization of M(x).
This theorem has been implemented directly in the psieve program, which has several command line options allowing for constuction of sieves of various number types. The basic command format is
psieve3 <number> [-p] [-r] [-s] [-g] [-t] [-c] [-n] [-e] [-q] [-m<number>] [-l<number>] [-x<number>] [-o<number>] [-i<number>] [-b<number>] [-j<number>] [-w<filename>] [-a<number>] [-d] [-f<filename>,<start>,<count>] [-?]
where the individual options have meaning as follows:
<number> The value of k to test. This may be a multiple-precision number and can be any odd integer. Required.
The single letter options are all mutually exclusive, and only the last will be applied.
-p Sieve 'Proth numbers' of the form k.2^n+1. This is the default, and allows looking for Sierpinski numbers.
-r Sieve numbers of the form k.2^n-1, looking for Riesel numbers k for which k.2^n-1 is always composite.
-s or -g Sieve Sophie Germain prime pairs of the form k.2^n-1, k.2^(n+1)-1. The alternative syntax -s<number> or -g<number> will allow a search for Cunningham chains of the first kind of a given length.
-t Sieve twin primes of the form k.2^n-1, k.2^n+1.
-c Sieve 'Cunningham chains of the second kind', prime pairs of the form k.2^n+1, k.2^(n+1)-1. The alternative syntax -c<number> will allow a search for Cunningham chains of the second kind of a given length.
-n Sieve 'BiTwin links' - a term I first encountered at this excellent page by Henri Lifchitz. Such numbers would simultaneously give two 'adjacent' twins, a Cunningham chain of the second kind of length 1 and a Sophie Germain pair. Again, an alternative syntax -n<number> has been added to allow for search of more than 2 twins in succession.
-e Estimate the effectiveness of the sieve thus calculated. This is done by checking how many n from a range of 10000 are rejected by the sieve, and is a good measure of just how much primality testing is involved in testing this value of k in proth.exe, for example. This calculates what is often termed the 'weight' of a particular k value, relative to others.
-q Quiet mode, where no progress indicators are output. This is ideal for redirection of results to a file.
-m<number> Only consider sieve lengths a divisor or multiple of this number. This allows quick proofs of the existence of Sierpinski and Riesel numbers, and can be used to create a table of all the values of n modulo m that need to be considered in the search for primes. The default is no such restriction. The idea is an initial run with a low limit and no -m flag will output suggestions for a good modulus. On future runs, use the suggested modulus in the -m flag and increase the limit. This should help you narrow the search for moduli that apply to Sierpinski numbers. If a Sierpinski or Riesel number is found, running the program again with the modulus in the -m flag will output only the factors needed for a proof.
Up to 16 such moduli may be applied concurrently, letting numbers pass through if they are divisors or multiples of any of the moduli. By combining this with the -x flag, very good sieves can be built over several short runs of the program.
-x<number> Exclude sieve lengths that are divisors of this number. This can be used to attempt to find other moduli apart from the most obvious ones when trying to eliminate primes by considering n modulo some number. For instance, if you discover 72 is a good modulus to test n by, on a future run use -x72 to attempt to find another modulus of different period. As with the -m flag, up to 16 such moduli may be excluded.
-o<number> This option allows the moduli that are included and excluded by the -m and -x flags to be overridden up to a given limit. For instance, it is feasible to construct a command line such as psieve 3 -p -m72 -l10000 -o256, which translates as 'scan for a sieve of numbers of the form 3.2^n+1, scan all multiples and divisors of 72 up to a limit of 10000, and include all values up to 256'. This option is useful as the smallest limits are capable of producing the most efficient sieves, so you'd like to include all the results you can for small sieve lengths, yet you still want to include the occasional larger values.
-l<number> Limit the number of bits in numbers considered by the gcd algorithm. The sieve creation can get very slow and execution time raises as L^4. The default is 256 which outputs a reasonable sieve reasonably quickly. High values of l require large amounts of memory as well as computation time and are not recommended unless used in conjunction with the -m flag. (Earlier versions defaulted to a limit of 1000 which was hardly efficient or effective).
-i<number> Defines an increment which is added to k after each value is tested. The default is not to use this mode, but at the moment any increment up to 32 bits is possible. This allows for exhaustive testing of Sierpinski and Riesel numbers. In increment mode factors are not output, only the best percentages of numbers eliminated by a given modulus.
-b<number> (Version 3+ only). This allows a choice of 'base' b so psieve can produce analogous results for numbers of the form k.b^n+-1. Be aware that the Sophie Germain and Cunningham modes will not work correctly with a base other than 2 - they will sieve for prime pairs of the form (p,bp+1) and (p,bp-1) instead.
-j<number>. Used in tandem with the -i increment and -e estimator mode, this command switch keeps track of the values of k for which the 'unsieved' count is greatest. The program defaults to 10, but a numeric parameter sets precisely how many values of k are kept. At each iteration, the program will output the best k and their unsieved count to the file specified by the -w parameter. This measure has recently became known as the 'weight' of k, and seems very good at predicting the number of primes a given k will yield. An optimization causes psieve to stop factoring if it is discovered a k's weight is too small to make the highest list. Several primality testers have used similar theories to maximize their number of database entries.
-w<filename> When used with the -i increment mode, this will output the values of k and their weights to the given file.
-a<number>. Used with the -j mode, this option automatically varies the increment set by the -i flag during a search. Every time a new value of k is added to the list of the 'best weights', the best values of k are checked for common factors. The number of values tested is set by this flag. If they do have a common factor, psieve assumes it is only worth testing other values of k with this factor and corrects the increment value accordingly. By using this judiciously, a large number of values of k can be tested and a list of some with very large weights can quickly be found.
-d. This mode performs an optimized search for many small prime divisors in the sieve. The first 50,000 prime numbers are tested for divisibility. This greatly improves the efficiency of psieve's main search mode. Currently, however, this optimization works only for numbers of the form k.b^n+1 (-p flag).
-f<filename>,<start>,<count> . This flag allows the production of a file suitable for parsing with the File option in Proth. After the sieve is constructed, or, if an auto-optimize mode was used, the sieve for the best k value, values of n beginning from <start> are tested with the sieve then output to the given filename. <count> values will be output - BEWARE, if for instance this option is used with Sierpinski numbers, the program will loop forever waiting for a value of n to pass through the sieve! This option can save trial factoring tests in Proth and also make sure proth.exe only tests the only n necessary for the more restrictive modes. The -f flag will append to the existing file. This allows a run of psieve to discover several good values of k in its 'increment' mode, then successive runs with the -f mode will create a file ready to be tested.
-?. This flag outputs a brief banner of psieve's (now rather unwieldy) list of command-line options!
The program will output a number of congruences which, if n satisfies, then a factor is known. In the Sophie Germain and twin prime cases the appearance of a congruence and factor denotes at least one of the two numbers under consideration has the given factor. At points in the output, the program will also output its suggestions for a good modulus to filter n by (including the percentage of values of n known to be verifiably composite using this modulus), and in particular if a modulus is found for which every value of n has a factor, this is stated.
As pointed out, the sieve gets very slow as the bit-count of the numbers passed to the gcd algorithm increases, something which is possible to counter to some extent. Since the values x are considered in order, it is only necessary to consider those factors of M(x) which have not previously been seen. This factoring-out decreases the number of bits in one argument to the gcd algorithm. It is also possible to remove discovered factors from the 2^r+k (or 2^r-k in the Riesel case) and in fact if all factors are discovered, that value of r could be removed from consideration for all future values of x. Such optimizations are not great but do to some extent assist in the process.
Paul Jobling achieved a reasonable optimization by using off-the-shelf math libraries that include FFT multiplication methods. This improved the general program speed by about 30%. I am currently looking at methods of selecting the FFT to maximize its usefulness in psieve, for instance, some optimizations can be made when the FFT is used with Mersenne numbers.
Generally though a large optimization will only be possible if a gross improvement of the basic algorithm can be found. I am looking at a method that will partially factorize 2^r+k, though I am open to any suggestions! Please e-mail me with any ideas.
Joe McLean's Researches into k.2^n+1 (Joe made heavy use
of pisieve3 in his investigations)
Chris Caldwell's
Prime Pages
Yves Gallot's
Proth Search Page
Riesel's
List of primes k.2^n+1 for k<300
Henri
Lifchitz's Generalization of Euler-Lagrange for Sophie Germains
and Cunningham Chains
Warut
Roonguthai's Cunningham Chains page
Search
the Database of the Largest Known Primes
This page last updated by Chris Nash on February 19, 2000.