ARTP - 08 - Testovanie prvočíselnosti. Monte Carlo algoritmy.

Zhrnutie prednášky

Prednáška sa zaoberá testovaním prvočíselnosti veľkých čísel, ktoré je dôležité najmä v kryptografii. Naivný algoritmus skúšajúci delitele do odmocniny z n je pseudopolynomiálny, pretože je exponenciálny vzhľadom na počet bitov vstupu, a pre 1024-bitové čísla je nepoužiteľný. Na lepší prístup sa využíva malá Fermatova veta a pojem Fermatov svedok, pričom test s náhodným základom môže zlyhať. Problémom sú Carmichaelove čísla (napr. 561, 1105, 1729), ktoré sú zložené, ale nemajú žiadneho Fermatovho svedka. Preto sa zavádza pojem silného svedka, ktorý vychádza z rozkladu n−1 = 2^t · u a sledovania postupnosti mocnín modulo n.

• - Prvočísla sú kľúčové v kryptografii; úlohy sú testovať prvočíselnosť a generovať veľké prvočísla.
• - Naivný test delením do √n je pseudopolynomiálny, lebo je exponenciálny vzhľadom na počet bitov vstupu log n.
• - Malá Fermatova veta: pre prvočíslo p platí a^(p−1) ≡ 1 (mod p); a, pre ktoré to neplatí, je Fermatov svedok zloženosti.
• - Test len so základom 2 je dobrá heuristika, ale môže chybne vyhlásiť zložené číslo (napr. 561) za prvočíslo.
• - Náhodný výber a funguje pravdepodobnostne, no nie je zaručený dostatok Fermatových svedkov.
• - Carmichaelove čísla (561, 1105, 1729) sú zložené, no nemajú žiadneho Fermatovho svedka, preto je Fermatov test nedostatočný.
• - Riešením je silný svedok: rozklad n−1 = 2^t · u a sledovanie postupnosti a^u, a^(2u), …, a^(2^t·u) modulo n.

Zhrnutie pripravené s pomocou AI z prepisu videa.