next up previous contents
Næste: 5.2.2 Dobbelttjek Op: 5.2 Programmet mprime Foregående: 5.2 Programmet mprime

5.2.1 Lucas-Lehmer testen

Hvis man ikke finder nogen divisorer, må man lave en Lucas-Lehmer test. Sætning 4.1 siger at tallet $ M_p$ er et primtal hvis det går op i $ S_{p-1}$.

Vi skal altså finde ud af om $ S_{p-1} \equiv 0 \pmod{2^p-1}$. Men hvis vi bare begynder at regne $ S_{p-1}$ ud, får vi hurtigt nogle meget store tal ( $ S_5 = 1537110438$), hvilket vi ikke er interesseret i, da disse er langsomme at arbejde med.5.1

Derfor regner vi modulus $ 2^p-1$, sådan at vi efter hvert trin reducerer $ S_n$ modulus $ 2^p-1$. Det kan vi gøre, fordi hvis

$\displaystyle S_n$ $\displaystyle \equiv k \pmod{2^p-1} \Leftrightarrow$ (5.1)

så har vi ifølge sætning 2.5 at


$\displaystyle S_n^2$ $\displaystyle \equiv k^2 \pmod{2^p-1} \Leftrightarrow$ (5.2)

og vi kan så trække 2 fra på begge sider


$\displaystyle S_{n+1} = S_n^2-2$ $\displaystyle \equiv k^2-2 \pmod{2^p-1}$ (5.3)

Vi kan altså lige så godt regne videre med et tal som er kongruent med det ``rigtige'' og alt for store tal $ S_n$. Resten, $ k$ i eksemplet, holder sig så hele tiden under $ 2^p-1$, hvilket sikre at tallene ikke løber løbsk og bliver alt for store.

Hvis vi efter sidste trin får resten 0, ved vi at $ 2^p-1$ er et primtal. Vi demonstrere det ved at vise at $ 2^{17}-1$ virkeligt er et primtal. Processen skal så igennem $ p-1=16$ trin. Ved hvert trin bruger man resten fra sidste trin, kvadrerer den og trækker 2 fra, og finder en ny rest:

$\displaystyle S_1$ $\displaystyle = 4$        
$\displaystyle S_2$ $\displaystyle = 4^2-2$   $\displaystyle \:\equiv\:$ $\displaystyle 14$ $\displaystyle \pmod{2^{17}-1}$    
$\displaystyle S_3$ $\displaystyle = 14^2-2$   $\displaystyle \:\equiv\:$ $\displaystyle 194$ $\displaystyle \pmod{2^{17}-1}$    
$\displaystyle S_4$ $\displaystyle = 194^2-2$   $\displaystyle \:\equiv\:$ $\displaystyle 37634$ $\displaystyle \pmod{2^{17}-1}$    
$\displaystyle S_5$ $\displaystyle \equiv 37634^2-2$   $\displaystyle \:\equiv\:$ $\displaystyle 95799$ $\displaystyle \pmod{2^{17}-1}$    
      $\displaystyle \:\cdots\:$        
$\displaystyle S_{13}$ $\displaystyle \equiv 69559^2-2$   $\displaystyle \:\equiv\:$ $\displaystyle 99585$ $\displaystyle \pmod{2^{17}-1}$    
$\displaystyle S_{14}$ $\displaystyle \equiv 99585^2-2$   $\displaystyle \:\equiv\:$ $\displaystyle 78221$ $\displaystyle \pmod{2^{17}-1}$    
$\displaystyle S_{15}$ $\displaystyle \equiv 78221^2-2$   $\displaystyle \:\equiv\:$ $\displaystyle 130559$ $\displaystyle \pmod{2^{17}-1}$    
$\displaystyle S_{16}$ $\displaystyle \equiv 130559^2-2$   $\displaystyle \:\equiv\:$ 0 $\displaystyle \pmod{2^{17}-1}$    

Efter det 4. trin ændrede jeg lignedstegnet ($ =$) til et $ \equiv$ da $ S_5$ ikke er lig 37634, men blot er kongruent med det, modulus $ 2^{17}-1$. Resten 0 efter det 16. trin, sådan som den skulle, da $ 2^{17}-1$ er et primtal.


Fodnoter

... med.5.1
Da det er store tal, ganger mprime dem ikke sammen på normal vis, men bruger i stedet en hurtigere metode kaldet irrational base discrete weighted transform, som involverer en Fast Fourier Transform (FFT), en kvadrering og en invers FFT, se [16].
next up previous contents
Copyright © 2001, Martin Geisler.