20050512, 15:50  #1 
2^{3}×1,033 Posts 
PRP => LLtests?
hi,
a short, maybe silly question: i know how the LucasLehmer test works for Mersennes (S(n+1)=S(n)^22 mod 2^n1, S(1)=4 etc. ). But how it works for a general numbers like a*b^n1? Or the algorithm used in PRP3.exe isn't related to LLtests? If it isn't, may i kindly ask for a short explanation or a link to such? J. HOlmes 
20050513, 17:18  #2  
Mar 2005
Poland
5·7 Posts 
Quote:
The theorem used in testing number as Probable Prime is Fermat Little Theorem. 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^(p1) = 1 (mod p). 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^(p1) != 2 mod p), and pretty good PROBABILITY of number being prime, if 2^(p1) = 1 mod p. One of algorithm for PROVING primarility of n follows: Let n > 1. If for every prime factor q of n1 there is an integer a such that * a(n1) = 1 (mod n), and * a(n1)/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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Run P1 before PRP tests  alpertron  Software  35  20180227 16:01 
p4  1.8 ghz  LL tests?  joblack  Hardware  12  20090826 20:40 
More P1 tests  dave_0273  Marin's Mersennearies  1  20060323 00:03 
Yet another set of 20 P1 tests  GP2  Completed Missions  5  20030930 22:10 
Bad LL Tests  outlnder  Lounge  8  20021021 00:12 