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 p 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}}







Místo pro váš banner

Zde je vyhrazené místo pro bannery našich partnerů a zákazníků.