Quote:
Originally Posted by Holmes
...
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?

Sure. First of all  take look at this page (but whole site is worth of reading):
http://primes.utm.edu/prove/index.html.
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