Netleksikon - Et online leksikon Netleksikon er ikke blevet opdateret siden 2005. Nogle artikler kan derfor indeholde informationer der ikke er aktuelle.
Forside | Om Netleksikon

Lucas-Lehmer

En Lucas-Lehmer-test kan vise om et mersennetal også er et primtal. Testen er opkaldt efter François Edouard Anatole Lucas og Derrick Henry Lehmer. En nødvendig (men ikke tilstrækkelig) betingelse for at et mersennetal kan være et primtal er at eksponenten er et primtal.

Table of contents
1 Algoritmen

Algoritmen

Definitioner

  • p er et primtal.
  • M(p) er et mersennetal med p som eksponent.
  • s er det resultat, der viser om M(p) er et primtal.

Forløbet

  1. s = 4
  2. Gentag p-2 gange:
    • s = (s2-2) mod M(p)
  3. Hvis s er 0 er M(p) et primtal

Implementering

Hvis algoritmen bruges direkte i et computerprogram, er den ikke særlig effektiv, selvom den er langt hurtigere end en generel primtalstest. Det er dog muligt, at lave en del optimeringer. I det binære talsystem skrives 2p med et ettal efterfulgt af p nuller. Det betyder, at tallet kan findes ved at forskyde 1 p bits og derefter trække en fra.

Når s skal beregnes modulo p, kan man også udnytte, at tallet består af ene ettaller i totalssystemet. 

Den store tidsrøver i denne algoritme er beregningen af S2. 








Denne artikel er kun påbegyndt.
 Du kan hjælpe Wikipedia ved at [ tilføje mere].






 


Denne artikel er fra Wikipedia. Læs artiklen hos Wikipedia. 
 









Boligstedet.dk

Boligsite med dagligt opdaterede boligannoncer med lejeboliger i hele landet.

Lejebolig i Aarhus

Lejebolig i København

Lejebolig i Odense

Lejebolig i Aalborg






Rejseforsikringer
Husk at kontrollere din rejseforsikring inden du tager ud at rejse. Læs mere på:
Rejseforsikring




Bilforsikringer
Sammenlign bilforsikringer og find information om forsikringer til din bil på:
Bilforsikring

  

Varmepumpepuljen
Varmepumpepulje åbner i 2023. Få tilskud til varmepumpe.
Varmepumpepuljen
















Denne artikel er fra Wikipedia. Denne hjemmeside tager ikke resourcer fra Wikipedias hardware. Netleksikon.dk  støtter Wikipedia projektet finansielt. Indholdet er udgivet under GNU Free Documentation License. Kontakt Netleksikon, hvis ophavsretten er krænket.