Re: how to check if 2^n-1 is prime for some n ?
From: Dale Henderson (nilram_at_hotpop.com)
Date: 06/10/04
- Next message: DanKage: "Re: algebra~.."
- Previous message: Eckard Blumschein: "Re: .999... ?= 1"
- In reply to: Basel Naamna: "how to check if 2^n-1 is prime for some n ?"
- Next in thread: Oscar Lanzi III: "Re: how to check if 2^n-1 is prime for some n ?"
- Reply: Oscar Lanzi III: "Re: how to check if 2^n-1 is prime for some n ?"
- Messages sorted by: [ date ] [ thread ]
Date: 10 Jun 2004 12:21:52 -0500
>>>>> "Basel" == Basel Naamna <baseln@yahoo.com> writes:
Basel> is there an algorithm to check of the 2^n-1 is prime?
Yes.
Numbers of the form 2^n-1 are called Mersenne numbers and primes
of the this form are known as Mersenne primes. To date 41 Mersenne
primes have been found. The most recent was found in May!
Probably the most common approach is to use the Lucas-Lehmer test.
Let L_1=4.
Define L_n=l_(n-1)^2-2.
2^n-1 is prime if and only if 2^n-1 divides L_(n-1) (equivalently
L_(n-1) = 0 (mod 2^n-1))
In practice calculation of L_k is done mod (2^n-1) since the L_k
grows *very* fast (L_6 has 18 digits!).
Since the Lucas-Lehmer test can be computationally taxing it is best
to perform some more basic checks first.
First check the primality of n. 2^n-1 can only be prime if n is
prime. (otherwise 2^n-1 is divisible by 2^k-1 where k divides n) Of
course this implies that n must be odd (or 2 but one would assume we
want n>2).
Another test that can be performed is to check for the primality of
2n+1. If n and 2n+1 are both prime then 2^n-1 is not prime.
For more information see
http://www.utm.edu/research/primes/mersenne/index.html
-- Dale Henderson "Imaginary universes are so much more beautiful than this stupidly- constructed 'real' one..." -- G. H. Hardy
- Next message: DanKage: "Re: algebra~.."
- Previous message: Eckard Blumschein: "Re: .999... ?= 1"
- In reply to: Basel Naamna: "how to check if 2^n-1 is prime for some n ?"
- Next in thread: Oscar Lanzi III: "Re: how to check if 2^n-1 is prime for some n ?"
- Reply: Oscar Lanzi III: "Re: how to check if 2^n-1 is prime for some n ?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
