Næste: E. Elektroniske kilder Op: D. Hurtig division Foregående: D.1 Algoritmen

D.2 Eksempel

Hvis man f.eks. gerne vil finde en faktor til $M_{29}$ (som ikke er et primtal), skal den have formen $q=2\cdot 29k+1$, og der skal også gælde at $q \equiv \pm 1 \pmod{8}$. Det giver os alt i alt at der skal gælder følgende om divisoren $q$:

$$q = 58k + 1 \equiv \pm 1 \pmod{8}$$ (D.1)

Vi prøver os frem og finder at $p=58\cdot 3 + 1 = 175$ og $q = 58\cdot 4 + 1 = 233$ er mulige divisorer, da der gælder at $175 \equiv 7 \pmod{8}$ og $233 \equiv 1 \pmod{8}$. Vi starter med $p=175$.

Første trin i algoritmen er at skrive eksponenten som et binært tal: $29_{10} = 11101_2$. De små mærker forneden angiver talsystemet. Vi starter med 1 som vi kvadrerer. Vi ser så på den mest betydende bit i eksponenten som er 1, hvilket betyder at vi skal gange med 2 og finder resten ved division med 175. Resten bliver så 2.

Vi gentager proceduren, og får denne gang at $2^2 \cdot 2 \equiv 4 \pmod{175}$. Vi ganger med 2, da den næste bit også er 1. Fortsætter vi, kan vi udfylde et skema som det i tabel D.1.

Tabel D.1: Trinene i division af $2^{29}-1$ med 175.

Kvadrering	Bit	Gange med 2	Rest
$1^2 = 1$	1	$1\cdot 2 = 2$	2
$2^2 = 4$	1	$4\cdot 2 = 8$	8
$8^2 = 64$	1	$64\cdot 2 = 128$	128
$128^2 = 16384$	0	Nej	109
$109^2 = 11881$	1	$11881\cdot 2 = 23762$	137

Tabel D.1 fortæller os at den sidste rest blev 137. Det betyder at $2^{29} \equiv 137 \pmod{175}$. Trækker vi en fra på begge sider, får vi at $2^{29}-1 \equiv 136 \pmod{175}$. 175 er altså ikke en faktor i $M_{29}$. Prøver vi så i stedet med den mulige divisor 233, får vi de udregninger som findes i tabel D.2.

Tabel D.2: Trinene i division af $2^{29}-1$ med 233.

Kvadrering	Bit	Gange med 2	Rest
$1^2 = 1$	1	$1\cdot 2 = 2$	2
$2^2 = 4$	1	$4\cdot 2 = 8$	8
$8^2 = 64$	1	$64\cdot 2 = 128$	128
$128^2 = 16384$	0	Nej	74
$74^2 = 5476$	1	$5476\cdot 2 = 10952$	1

Så fortæller tabel D.2 os at $2^{29} \equiv 1 \pmod{233} \Leftrightarrow 2^{29}-1 \equiv 0 \pmod{233}$. Vi kan altså nu konstatere at 233 er en faktor i $M_{29}$, som så ikke kan være et primtal.

• Næste: E. Elektroniske kilder
• Op: D. Hurtig division
• Foregående: D.1 Algoritmen