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

Pomohl Vám tento článek?

Pomohl Vám tento článek lépe porozumět dané problematice, složit zkoušku nebo dokončit Váš program? Přispějte tedy na provoz těchto stránek a umožněte tak dalším čtenářům získat nové znalosti.

PDF

– Pavel Mička

Zakladatel a administrátor stránek Algoritmy.net

Tweet

Hodnocení (0): 0

Přečtěte si také

Fermatův test

Rabin-Millerův test

Diskuse

Článek zatím nemá žádné komentáře.