mersenneforum.org > Math PRP => LL-tests?
 Register FAQ Search Today's Posts Mark Forums Read

 2005-05-12, 15:50 #1 Holmes   5078 Posts 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
2005-05-13, 17:18   #2
Washuu

Mar 2005
Poland

5×7 Posts

Quote:
 Originally Posted by 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?
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^(p-1) = 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^(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

 Similar Threads Thread Thread Starter Forum Replies Last Post alpertron Software 35 2018-02-27 16:01 joblack Hardware 12 2009-08-26 20:40 dave_0273 Marin's Mersenne-aries 1 2006-03-23 00:03 GP2 Completed Missions 5 2003-09-30 22:10 outlnder Lounge 8 2002-10-21 00:12

All times are UTC. The time now is 02:49.

Wed Feb 1 02:49:17 UTC 2023 up 167 days, 17 mins, 0 users, load averages: 1.11, 1.32, 1.23