Lucas-Lehmer test

Lucas-Lehmer- testen er en verifisering av primaliteten til Mersenne - primtallene . Oppsummert, etter primtall, kalt det -th Mersenne-tallet, er det primtall hvis og bare hvis det deler , hvor er det n-te leddet i rekkefølgen definert rekursivt som: $s$ ${\ displaystyle M_ {p} = 2 ^ {p} -1}$ $s$ ${\ displaystyle L_ {p-1}}$ ${\ displaystyle L_ {n}}$

{\ displaystyle L_ {n + 1} = L_ {n} ^ {2} -2}

starter fra

{\ displaystyle L_ {1} = 4}

Testen ble opprinnelig utviklet av matematikeren Édouard Lucas i 1870 og forenklet av Derrick Norman Lehmer i 1930 . Testen er så rask og enkel å programmere at i 1978 beviste to elever på videregående skole at Mersenne-tallet var primtall, og slo den tidligere rekorden for det største primtallet kjent på den tiden. ${\ displaystyle 2 ^ {21701} -1}$

Det er også mulig en optimalisering i beregningstiden, for å kunne håndtere større tall, siden den vokser veldig raskt, ettersom den øker , for raskt å bli vanskelig. Den forrige sekvensen kan erstattes av den spesifikke for nummeret som skal verifiseres , oppnådd som følger: $L_ {n}$ $n$ $M_n$

{\ displaystyle L_ {n + 1} \ equiv (L_ {n} ^ {2} -2) \, \ operatørnavn {mod} \, M_ {p}}

der mod er modulo , dvs. resten av divisjonen med . Imidlertid har denne sekvensen den ulempen at den bare er nyttig for Mersenne-tall mindre enn eller lik . $M_p$ $M_p$

Uttalelse

La p være et primtall. Det tilsvarende Mersenne-tallet er primtall hvis og bare hvis: ${\ displaystyle M_ {p} = 2 ^ {p} -1}$

{\ displaystyle L_ {p-1} \ equiv 0 \, \ operatørnavn {mod} \, M_ {p}}

Merknad

Det er ikke begrensende å betrakte Mersenne-tall som primtall i stedet for naturlig tall. Faktisk viser det at hvis det er sammensatt, så er det det også. $M_p$ $s$ $M_n$ $n$ $n$ $M_n$

Demonstrasjon

For tilstrekkelighet: er og . Det er da lett å vise ved induksjon at ${\ displaystyle u = 2 + {\ sqrt {3}}}$ ${\ displaystyle v = 2 - {\ sqrt {3}}}$

{\ displaystyle L_ {n} = u ^ {2 ^ {n-1}} + v ^ {2 ^ {n-1}}}

Siden den deler , eksisterer det et heltall slik at $M_p$ ${\ displaystyle L_ {p-1}}$ $R.$

{\ displaystyle L_ {p-1} = R \, M_ {p}}

eller

{\ displaystyle u ^ {2 ^ {p-2}} + v ^ {2 ^ {p-2}} = R \, M_ {p}}

Multiplisere med , får jeg ${\ displaystyle u ^ {2 ^ {p-2}}}$

{\ displaystyle 1) \, \, \, \, \, u ^ {2 ^ {p-1}} = R \, M_ {p} u ^ {2 ^ {p-2}} - 1}

Kvadring

{\ displaystyle 2) \, \, \, \, \, u ^ {2 ^ {p}} = \ venstre (R \, M_ {p} u ^ {2 ^ {p-2}} - 1 \ høyre ) ^ {2}}

Vi går absurd frem. Anta at den er sammensatt og ta divisor d mindre enn kvadratroten . La G være tallgruppen i formen som også er inverterbare: G har høyst elementer. Hvis vi omskriver 1- og 2 - formen d , får vi hhv . Så u er et element av G i periode . Siden perioden til et element maksimalt kan være lik antall elementer i gruppen, har vi følgende ulikhet $M_p$ ${\ visningsstil \ venstre (a + b {\ sqrt {3}} \ høyre) \, \ operatørnavn {mod} \, d}$ ${\ displaystyle d ^ {2} -1}$ ${\ displaystyle u ^ {2 ^ {p-1}} \ equiv -1 \, \ operatørnavn {mod} \, d}$ ${\ displaystyle u ^ {2 ^ {p}} \ equiv 1 \, \ operatørnavn {mod} \, d}$ ${\ displaystyle 2 ^ {p}}$

{\ displaystyle 2 ^ {p} \ leq d ^ {2} -1 <M_ {p} = 2 ^ {p} -1}

Siden vi har en motsetning, har den ingen divisorer, og er derfor primtall. $M_p$

Relaterte elementer

Eksterne lenker

( EN ) Demonstrasjon av Lucas-Lehmer-testen ( PDF ), 140.122.140.53 . Hentet 8. august 2005 (arkivert fra originalen 16. juni 2006) .