Lehmannův test prvočíselnosti

Lehmannův test je test prvočíselnosti - určuje, zda-li je zadané číslo prvočíslem nebo nikoliv.

Princip

Z malé Fermatovy věty víme, že pro každé prvočíslo platí

${a^{p-1} \\equiv 1 \\bmod p}$

Proto také určitě platí

${a^{p-1} -1 \\equiv 0 \\bmod p}$

Použijeme-li vzorec $A^2 - B^2 = (A - B) \\cdot (A + B)$ , tak dostáváme

$a^{p-1} -1 = (a^{(p-1)/2} - 1) \\cdot (a^{(p-1)/2} + 1)$

Z dělitelnosti čísel víme, že musí platit

${p \\mid (x \\cdot y)} \\: \\Rightarrow \\: {(p \\mid x)} \\vee {(p \\mid y)}$

Aby tedy platila rovnice ${a^{p-1} -1 \\equiv 0 \\bmod p}$ , tak musí platit jedna z následujích podmínek

${a^{(p-1)/2} - 1 \\equiv 0 \\bmod p} \\:\\:\\: \\Rightarrow \\:\\:\\: {a^{(p-1)/2} \\equiv 1 \\bmod p} \\:\\:\\: \\Rightarrow \\:\\:\\: a^{(p-1)/2} = 1 \\; v \\; Z_{p}$
${a^{(p-1)/2} + 1 \\equiv 0 \\bmod p} \\:\\:\\: \\Rightarrow \\:\\:\\: {a^{(p-1)/2} \\equiv -1 \\bmod p} \\:\\:\\: \\Rightarrow \\:\\:\\: a^{(p-1)/2} = -1 = p - 1 \\; v \\; Z_{p}$

Pokud tedy

$a^{(p-1)/2} = 1 \\; v \\; Z_{p} \\quad nebo \\quad a^{(p-1)/2} = -1 = p - 1 \\; v \\; Z_{p}$

Pak je číslo p možná prvočíslo. V každém jiném případě prvočíslem určitě není (odporuje malé Fermatově větě). Dá se ukázat, že při každém průchodu tohoto algoritmu dojde k vyloučení padesáti procent složených čísel.

Pravděpodobnost, že číslo je prvočíslem po k průchodech algoritmu, je

$p = 1 - {1 \\over 2^{k}}$

Princip

Doporučujeme