Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummers-lowrise
|
Message boards :
Number crunching :
Primality algorithms
| Author |
Message |
|---|
|
|
|
Recently, I've begun to understand some basic primality testing algorithms: Pepin's Test and Lucas' Converse of Fermat's Little Theorem.
Obviously, I still have more to learn, but I'm wondering which algorithms PrimeGrid uses to test the variety of numbers we check.
I know GIMPS uses the Lucas-Lehmer test for Mersenne numbers.
I've discovered many large prime numbers, but I've yet to fully understand why they're prime. That is, I don't personally know that they're prime; I just have faith in the word of mathematicians! | |
|
|
|
|
Hi Chris,
The principle tests that are used at Primegrid are (along with some references you might find useful for further reading):
- Lucas-Lehmer-Riesel test (http://en.wikipedia.org/wiki/Lucas–Lehmer–Riesel_test, and Riesel's paper). A deterministic primality test for Riesel numbers (k*2^n-1, k < 2^n). Used on 321 (-1), TRP, WOO, SGS subprojects
- Proth test (http://en.wikipedia.org/wiki/Proth's_theorem). A deterministic primality test for Proth numbers (k*2^n+1, k < 2^n). Used on 321 (+1), PPS(E), MEGA, SOB, PSP, ESP, CUL subprojects
- N-1 and N+1 tests (https://primes.utm.edu/prove/prove3.html). A deterministic primality test for numbers where N+/-1 can be factorised. Used on SR5 subproject.
- Fermat test (http://en.wikipedia.org/wiki/Fermat_primality_test). A probabilistic primality test which can be efficiently implemented for some forms of number including Generalised Fermat Numbers. Used on the GFN and GFN-WR sub projects. Probable primes (PRPs) found with this method must be verified with a deterministic test (e.g. N-1).
There are also some good sieving algorithms which are used to remove the vast number of candidates before we even start running primality tests on them, but I'm not very well versed in that area, others might be able to give more details…
Cheers
- Iain
____________
Twitter: IainBethune
Proud member of team "Aggie The Pew". Go Aggie!
3073428256125*2^1290000-1 is Prime!
| |
|
|
|
|
Thank you.
So are the GFNs tested with a simple Fermat test?
Just: a^(GFN-1) = 1 (mod GFN) ?
Or is a more sophisticated probable prime test used?
Why are GFNs (in particular) capable of being tested using GPU parallelization? Can't any number be tested in this way? | |
|
|
|
|
That's correct.
Genefer (which does the Fermat test), has both CUDA and OpenCL versions written, which are quite efficient. All the other tests are done by LLR, which makes use of the gwnum library for the expensive numerical parts (squaring, modular reduction …). There was a CUDA port of LLR floating around a few years ago where the gwnum parts were replaced by CUDA but it was not particularly efficient (only a little faster than CPUs, and used quite a lot of CPU to keep the GPU busy), and it had some bugs too.
There is no reason in principle why LLR can't be implemented on GPUs but no-one (including myself) has had the time to do it :(
____________
Twitter: IainBethune
Proud member of team "Aggie The Pew". Go Aggie!
3073428256125*2^1290000-1 is Prime! | |
|
Message boards :
Number crunching :
Primality algorithms |
