A Lucas-Lehmer-Riesel teszt ( LLR ) a c alakú számok elsődlegességi tesztje (az ilyen számok egy részhalmazát Sabit számoknak nevezzük ). Hans Riesel által kifejlesztett és a Luc-Lehmer teszt alapján ez a leggyorsabb determinisztikus algoritmus az ilyen típusú számokra [1] .
Az algoritmus nagyon hasonlít a Luc-Lehmer teszthez, de olyan értékkel kezdődik, amely attól függ . Az algoritmushoz a Lucas sorozatot használjuk , amelyet a következő képlettel adunk meg:
.prím akkor és csak akkor, ha osztja .
1994-ben megadtak egy alternatív módszert a kiindulási érték meghatározására [2] . A módszer sokkal egyszerűbb, mint amit Riesel használ arra az esetre, amikor 3 oszt . Az alternatív módszerben először keresse meg azt az értéket , amely kielégíti a következő Jacobi szimbólumegyenlőséget :
és .A gyakorlatban csak néhány értéket kell ellenőrizni (5, 8, 9 vagy 11 lefedi a 85%-ot).
A kezdeti érték lekéréséhez használhatja a Lucas sorozatot [ 2] [3] . 3 ∤ k esetén (k nem osztható 3-mal) az érték használható, és nincs szükség előzetes keresésre. A kezdeti érték ekkor egyenlő a Lucas-szekvencia modulo értékével . Ez a folyamat nagyon kevés időt vesz igénybe a fő teszthez képest.
A Luc-Lehmer-Riesel teszt egy speciális eset a csoport sorrendjének egyszerűségének ellenőrzésére. A teszt azt mutatja, hogy egy bizonyos szám prím, mivel egy bizonyos csoportnak van egy olyan sorrendje, amely megegyezik ezzel a prímszámmal, amelyhez a csoport egy elemét azonosítjuk, amelynek pontosan a kívánt sorrendje van.
A Luke-féle tesztekhez hasonló tesztek az egész számok másodfokú modulo kiterjesztésének szorzócsoportját használják egy számhoz . Ha prím, akkor a szorzócsoport sorrendje , és van egy rendű alcsoportja, a teszt céljaira ennek az alcsoportnak a generáló halmazát kell keresni.
Találhat egy nem iteratív kifejezést a kifejezésre . A Lucas-Lehmer tesztmodellt követve indukcióval állítjuk be és kapjuk meg .
Tekintsük a sorozat 2 i -edik elemét . Ha a teljesít egy másodfokú egyenletet, akkor ez egy Lucas-sorozat, és engedelmeskedik a kifejezésnek . Valójában egy másik sorozat -edik elemét keressük, de mivel a Lucas-sorozat tizedelése (minden k -edik elem kiválasztása) egy Lucas-sorozatot is eredményez, a k faktort egy kiindulási pont kiválasztásával választhatjuk ki.
Az LLR egy olyan program, amely LLR tesztet hajt végre. A programot Jean Penné fejlesztette ki. Vincent Penné úgy módosította a programot, hogy ellenőrizni tudja egy szám elsődlegességét az interneten keresztül. A program egyéni keresésekhez is használható, de néhány elosztott számítástechnikai projektben is szerepel, mint például a Riesel Sieve és a PrimeGrid .