Lucas-Lehmer-Riesel-testen ( LLR ) er en primalitetstest for tal af formen c (en delmængde af sådanne tal kaldes Sabit-tal ). Udviklet af Hans Riesel og baseret på Luc-Lehmer-testen , er det den hurtigste deterministiske algoritme for tal af denne art [1] .
Algoritmen minder meget om Luc-Lehmer-testen, men starter med en værdi, der afhænger af . Til algoritmen bruges Lucas-sekvensen , som er givet ved formlen:
.er prime, hvis og kun hvis den deler sig .
En alternativ metode til at finde startværdien blev givet i 1994 [2] . Metoden er meget enklere end den, Riesel bruger til tilfældet, hvor 3 deler . I den alternative metode skal du først finde den værdi , der opfylder følgende Jacobi-symbollighed :
og .I praksis er det kun nogle få værdier, der skal kontrolleres (5, 8, 9 eller 11 dækker 85%).
For at få startværdien fra kan du bruge Lucas-sekvensen [2] [3] . For 3 ∤ k (k er ikke deleligt med 3), kan værdien bruges, og der er ikke behov for et foreløbigt opslag. Startværdien er så lig med Lucas-sekvensen modulo . Denne proces tager meget kort tid sammenlignet med hovedtesten.
Luc-Lehmer-Riesel-testen er et særligt tilfælde af kontrol af enkelheden i rækkefølgen af en gruppe. Testen viser, at et bestemt tal er primtal på grund af det faktum, at en bestemt gruppe har en rækkefølge, der ville være lig med dette primtal, for hvilket der identificeres et element i gruppen, som har præcis den ønskede rækkefølge.
Tests som Luke's tests bruger den multiplikative gruppe af den kvadratiske modulo-udvidelse af heltal for et tal . Hvis er prime, rækkefølgen af den multiplikative gruppe er , og den har en undergruppe af orden , med henblik på testen søges genereringssættet for denne undergruppe.
Du kan finde et ikke-iterativt udtryk for . Efter Lucas-Lehmer-testmodellen indstiller og opnår vi ved induktion .
Overvej det 2 i -te element i sekvensen . Hvis a opfylder en andengradsligning, er det en Lucas-sekvens og adlyder udtrykket . Vi leder faktisk efter det -te element i en anden sekvens, men da decimering (valg af hvert k -te element) af Lucas-sekvensen også giver en Lucas-sekvens, kan vi vælge faktoren k ved at vælge et udgangspunkt.
LLR er et program, der udfører en LLR-test. Programmet er udviklet af Jean Penné. Vincent Penné ændrede programmet, så du kan tjekke et tals primehed over internettet. Programmet kan bruges både til individuelle søgninger, men er også inkluderet i nogle distribuerede computerprojekter , herunder Riesel Sieve og PrimeGrid .