Farm teszt

A számelméleti Fermat - primalitáspróba  egy n természetes szám primalitástesztje, amely a Fermat-féle kis tételen alapul .

Tartalom

Ha n prím ,  akkor kielégíti az összehasonlítást bármely olyan a számára , amely nem osztható n -nel .

Az összehasonlítás szükséges, de nem elégséges jele annak, hogy egy szám prím. Vagyis ha van legalább egy a , amelyre , akkor az n szám  összetett; egyébként semmit sem lehet mondani, bár nő annak az esélye, hogy a szám prím. Ha összehasonlítunk egy n összetett számot , akkor az n számot pszeudoprímnek mondjuk az a bázisban . Amikor egy szám elsődlegességét Fermat-próbával teszteljük, több a számot választunk . Minél nagyobb a száma , amelyre , annál nagyobb az esély arra, hogy az n szám prím. Léteznek azonban olyan összetett számok , amelyeknél az összes n -re vonatkozó prímszámot összehasonlítjuk  – ezek Carmichael-számok . A Carmichael-számok végtelenek , a legkisebb Carmichael-szám 561. A Fermat-teszt azonban meglehetősen hatékony az összetett számok kimutatására.

Sebesség

Gyors hatványozási modulo algoritmusok használatakor a Fermat-teszt futási ideje egy a esetén a becslések szerint O (log 2 n  × log log n  × log log log n ), ahol n  a tesztelt szám. Általában több ellenőrzést végeznek különböző a .

Irodalom

• Vasilenko O. N. Számelméleti algoritmusok a kriptográfiában, MTsNMO, 2003
• Trost E. - Primzahlen / Prímszámok - M .: GIFML, 1959, 135 oldal
• Thomas Cormen , Charles Letherston , Ronald Rivest , Clifford Stein . 31.8. szakasz: Primalitásteszt // Bevezetés az algoritmusokba . - Második kiadás. — MIT Press; McGraw-Hill, 2001, 889-890. — ISBN 0-262-03293-7 . (Orosz)

Linkek

• Ez a szám prím? // Berkeley Math Circle 2002-2003
• Fermat teszt // Aszimmetrikus titkosítási rendszerekben használt algoritmusok. cryptowiki.net