- **Math**
(*https://www.mersenneforum.org/forumdisplay.php?f=8*)

- - **PRP => LL-tests?**
(*https://www.mersenneforum.org/showthread.php?t=4096*)

PRP => LL-tests?hi,
a short, maybe silly question: i know how the LucasLehmer test works for Mersennes (S(n+1)=S(n)^2-2 mod 2^n-1, S(1)=4 etc. ). But how it works for a general numbers like a*b^n-1? Or the algorithm used in PRP3.exe isn't related to LL-tests? If it isn't, may i kindly ask for a short explanation or a link to such? J. HOlmes |

[QUOTE=Holmes]
... But how it works for a general numbers like a*b^n-1? Or the algorithm used in PRP3.exe isn't related to LL-tests? If it isn't, may i kindly ask for a short explanation or a link to such? [/QUOTE] Sure. First of all - take look at this page (but whole site is worth of reading): [url]http://primes.utm.edu/prove/index.html[/url]. The theorem used in testing number as Probable Prime is Fermat Little Theorem. [B]Fermat's Little Theorem: If p is a prime and if a is any integer, then a^p = a (mod p). In particular, if p does not divide a, then a^(p-1) = 1 (mod p). [/B] In most cases we choose a=2, as multiplying by 2 is very simple in binary system, used by computers. This test gives only certainty of number being composite in 99% cases (when 2^(p-1) != 2 mod p), and pretty good PROBABILITY of number being prime, if 2^(p-1) = 1 mod p. One of algorithm for PROVING primarility of n follows: Let n > 1. If for every prime factor q of n-1 there is an integer a such that * a(n-1) = 1 (mod n), and * a(n-1)/q is not 1 (mod n); then n is prime. That should be enough for now, come back here when you read mentioned webpage :) Regards, Washuu |

All times are UTC. The time now is 09:45. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.