Lucas-Lehmer-teszt

• IPA:

Lucas-Lehmer-teszt

1. (matematika, algoritmusok, számelmélet)

Legyen ${\displaystyle p>2}$ tetszőleges prímszám, ${\displaystyle M_{p}:=2^{p}-1}$ és legyen ${\displaystyle (a_{n})\subset \mathbb {N} }$ a következő sorozat: ${\displaystyle a_{1}:=4}$ és ${\displaystyle a_{n+1}:=a_{n}^{2}-2{\text{ maradéka }}M_{p}{\text{-vel osztva}}}$ Ekkor Lucas és Lehmer tétele szerint az ${\displaystyle M_{p}:=2^{p}-1}$ (ún. Mersenne-szám) pontosan akkor prím (Mersenne-prím) ha ${\displaystyle a_{p-1}}$ osztható ${\displaystyle M_{p}}$ -vel.

A Lucas-Lehmer-teszt egy olyan heurisztikus módszer, amelyet kifejezetten a Mersenne-prímek tesztelésére használnak. Egy ( M_p = 2^p - 1 ) alakú szám akkor és csak akkor prím, ha ( p ) maga prím, és a Lucas-Lehmer-szekvencia alapján a szám osztója egy meghatározott ( S_{p-2} ) értéknek.

1. Indítás: Definiáljuk a Lucas-Lehmer-szekvenciát ( S_0 = 4 )-el.
2. Rekurzió: A következő tagokat ( S_{n+1} = S_n^2 - 2 M_p ) képlettel számítjuk.
3. Feltétel: Ha ( S_{p-2} M_p ), akkor ( M_p ) prím, különben összetett.

Az alábbi program megvalósítja a Lucas-Lehmer-tesztet:

def is_mersenne_prime(p):
    if p < 2:
        return False
    if p == 2:
        return True  # M2 = 2^2 - 1 = 3, ami prím
    
    M_p = 2**p - 1  # Mersenne-szám kiszámítása
    S = 4  # Kezdőérték a Lucas-Lehmer szekvenciában
    
    for _ in range(p - 2):  # Iteráljunk p-2 alkalommal
        S = (S * S - 2) % M_p
    
    return S == 0  # Ha S végül 0, akkor M_p prím

# Példa használat:
p = 5  # Ellenőrizzük, hogy M5 = 2^5 - 1 prím-e
if is_mersenne_prime(p):
    print(f"M{p} = {2**p - 1} prím.")
else:
    print(f"M{p} = {2**p - 1} nem prím.")

1. ( p = 5 ):
   

( M_5 = 2^5 - 1 = 31 )
Kimenet: M5 = 31 prím.

1. ( p = 11 ):
   

( M_{11} = 2^{11} - 1 = 2047 )
Kimenet: M11 = 2047 nem prím.

• A teszt kifejezetten Mersenne-számokra optimalizált, mivel a Lucas-Lehmer-szekvencia gyorsan eldönti, hogy ( 2^p - 1 ) osztható-e maradék nélkül.
• A számítások hatékonyak, mert a szekvencia minden lépésében csak moduláris műveleteket használunk.

• angol: Lucas-Lehmer test (en)
• német: Lucas-Lehmer-Test (de)

• Édouard Lucas
• Derrick Henry Lehmer

• Lucas-Lehmer-teszt - Értelmező szótár (MEK)
• Lucas-Lehmer-teszt - Etimológiai szótár (UMIL)
• Lucas-Lehmer-teszt - Szótár.net (hu-hu)
• Lucas-Lehmer-teszt - DeepL (hu-de)
• Lucas-Lehmer-teszt - Яндекс (hu-ru)
• Lucas-Lehmer-teszt - Google (hu-en)
• Lucas-Lehmer-teszt - Helyesírási szótár (MTA)
• Lucas-Lehmer-teszt - Wikidata
• Lucas-Lehmer-teszt - Wikipédia (magyar)