Fermat pseudoprime - Fermat pseudoprime

v teorie čísel, Fermat pseudoprimes tvoří nejdůležitější třídu pseudoprimes které pocházejí z Fermatova malá věta.

Definice

Fermatova malá věta uvádí, že pokud str je hlavní a A je coprime na str, pak A^str−1 - 1 je dělitelný podle str. Pro celé číslo A > 1, pokud je složené celé číslo X rozděluje A^X−1 - 1 tedy X se nazývá a Fermat pseudoprime na základnu A.^{[1]:Def. 3.32}Jinými slovy, složené celé číslo je Fermatův pseudoprime na bázi A pokud úspěšně projde Fermatův test primality pro základnu A.^[2] Falešné tvrzení, že všechna čísla, která projdou Fermatovým testem primality pro základnu 2, jsou prvočísla, se nazývá Čínská hypotéza.

Nejmenší pseudoprime základny-2 Fermat je 341. Není to prvočíslo, protože se rovná 11,31, ale splňuje Fermatovu malou větu: 2³⁴⁰ ≡ 1 (mod 341), a tedy předáFermatův test primality pro základnu 2.

Někdy se nazývají pseudoprimesi na bázi 2 Sarrusova čísla, po P. F. Sarrus kdo zjistil, že 341 má tuto vlastnost, Čísla pouletů, po P. Poulet kdo vytvořil tabulku takových čísel, nebo Fermati (sekvence A001567 v OEIS ).

Fermat pseudoprime se často nazývá a pseudoprime, s modifikátorem Fermat být chápán.

Celé číslo X to je Fermatův pseudoprime pro všechny hodnoty A které jsou coprime X se nazývá a Carmichael číslo.^{[2][1]:Def. 3.34}

Vlastnosti

Rozdělení

Na danou základnu existuje nekonečně mnoho pseudoprimitů A > 1. V roce 1904 Cipolla ukázal, jak vyrobit nekonečné množství báze pseudoprimes A > 1: Let str být prime, který se nerozdělí A(A² - 1). Nechat A = (A^str - 1)/(A - 1) a nechte B = (A^str + 1)/(A + 1). Pak n = AB je složený a je základem pseudoprime A.^[3] Například pokud A = 2 a str = 5, tedy A = 31, B = 11 a n = 341 je pseudoprime k základně 2.

Ve skutečnosti je jich nekonečně mnoho silné pseudoprimesi na jakoukoli základnu větší než 1 (viz teorém 1 z^[4]) a nekonečně mnoho čísel Carmichael,^[5] ale jsou poměrně vzácné. Existují tři pseudoprimesy, které mají základnu 2 pod 1000, 245 pod milionem a 21853 méně než 25,10⁹. Pod tímto limitem je 4842 silných pseudoprimesů základny 2 a 2163 Carmichaelových čísel (viz tabulka 1 z ^[4]).

Počínaje 17,257 je produktem po sobě jdoucích Fermatových čísel pseudoprime základny-2, a tak jsou všechny Fermat kompozit a Mersennovy kompozity.

Faktorizace

Faktorizace 60 čísel Poulet až 60787, včetně 13 čísel Carmichael (tučně), jsou v následující tabulce.

(sekvence A001567 v OEIS )

Číslo pouletu, jehož všechny dělitele d rozdělit 2^d - 2 se nazývá a číslo super-poulet. Existuje nekonečně mnoho čísel pouletů, které nejsou super-pouletovými čísly.^[6]

Nejmenší Fermat pseudoprimes

Nejmenší pseudoprime pro každou základnu A ≤ 200 je uvedeno v následující tabulce; barvy označují počet hlavních faktorů. Na rozdíl od definice na začátku článku, pseudoprimes níže A jsou v tabulce vyloučeny. (Za tímto účelem povolit pseudoprimes níže Aviz OEIS: A090086)

(sekvence A007535 v OEIS )

Seznam pseudoprimů Fermat v pevné základně n

Další informace (základna 31 až 100) viz OEIS: A020159 na OEIS: A020228a pro všechny základny do 150 viz tabulka Fermat pseudoprimes (text v němčině), tato stránka nedefinuje n je pseudoprime základny shodné s 1 nebo -1 (mod n)

Které základy b udělat n Fermatský pseudoprime?

Pokud je složený ${ displaystyle n}$ je tedy vyrovnaný ${ displaystyle n}$ je Fermatův pseudoprime k triviální základně ${ displaystyle b equiv 1 { pmod {n}}}$Pokud je složený ${ displaystyle n}$ je tedy zvláštní ${ displaystyle n}$ je Fermatův pseudoprime k triviálním základnám ${ displaystyle b equiv pm 1 { pmod {n}}}$.

Pro jakýkoli kompozit ${ displaystyle n}$, číslo různých bází ${ displaystyle b}$ modulo ${ displaystyle n}$, pro který ${ displaystyle n}$ je pseudoprime základna Fermat ${ displaystyle b}$, je^{[7]:Thm. 1, s. 1392}

${ displaystyle prod _ {i = 1} ^ {k} gcd (p_ {i} -1, n-1)}$

kde ${ displaystyle p_ {1}, tečky, p_ {k}}$ jsou odlišné hlavní faktory ${ displaystyle n}$. To zahrnuje triviální základy.

Například pro ${ displaystyle n = 341 = 11 cdot 31}$, tento produkt je ${ displaystyle gcd (10 340) cdot gcd (30 340) = 100}$. Pro ${ displaystyle n = 341}$, nejmenší taková netriviální základna je ${ displaystyle b = 2}$.

Každý zvláštní kompozit ${ displaystyle n}$ je Fermatův pseudoprime na nejméně dvě netriviální báze modulo ${ displaystyle n}$ ledaže ${ displaystyle n}$ je síla 3.^{[7]:Cor. 1, s. 1393}

Pro kompozitní n <200, následující je tabulka všech bází b < n který n je Fermat pseudoprime. Pokud složené číslo n není v tabulce (nebo n je v pořadí A209211 ), pak n je pseudoprime pouze pro triviální základnu 1 modulo n.

Pro více informací (n = 201 až 5 000), viz,^[8] tato stránka nedefinuje n je pseudoprime základny shodné s 1 nebo -1 (mod n). Když str je vrchol, str² je Fermatův pseudoprime k základně b kdyby a jen kdyby str je Wieferich prime na základnu b. Například 1093² = 1194649 je Fermatův pseudoprime na bázi 2 a 11² = 121 je Fermatův pseudoprime k základně 3.

Počet hodnot b pro n jsou (pro n prime, počet hodnot b musí být n - 1, protože všichni b uspokojit Fermatova malá věta )

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, ... (sekvence A063994 v OEIS )

Nejméně základna b > 1 který n je pseudoprime na bázi b (nebo prvočíslo) jsou

2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, ... (sekvence A105222 v OEIS )

Počet hodnot b pro n musí se rozdělit ${ displaystyle varphi}$ (n), nebo A000010 (n) = 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, ... (The kvocient může být jakékoli přirozené číslo a podíl = 1 kdyby a jen kdyby n je primární nebo a Carmichael číslo (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997 ), kvocient = 2 právě tehdy n je v pořadí: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... A191311 )

Nejmenší počet s n hodnoty b jsou (nebo 0, pokud takové číslo neexistuje)

1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, 0, 286, 17, 1854, 19, 3820, 891, 2752, 23, 1128, 595, 2046, 0, 532, 29, 1770, 31, 9952, 425, 1288, 0, 2486, 37, 8474, 0, 742, 41, 3486, 43, 7612, 5589, 2356, 47, 13584, 325, 9850, 0, ... (sekvence A064234 v OEIS ) (kdyby a jen kdyby n je dokonce a ne totient z číslo bez čtverce, pak nth termín této sekvence je 0)

Slabé pseudoprime

Složené číslo n které to uspokojují ${ displaystyle b ^ {n} equiv b { pmod {n}}}$ je nazýván slabý pseudoprime na základnu b. Tuto podmínku splňuje pseudoprime, jehož základem je (podle obvyklé definice). Naopak slabý pseudoprime, který je coprime se základnou, je pseudoprime v obvyklém smyslu, jinak tomu tak může nebo nemusí být.^[9] Nejméně slabý pseudoprime k základně b = 1, 2, ... jsou:

4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ... (sekvence A000790 v OEIS )

Všechny výrazy jsou menší nebo rovny nejmenšímu číslu Carmichael, 561. Kromě pouze 561 semiprimes může nastat ve výše uvedené sekvenci, ale ne všechny poloprime méně než 561, poloprime pq (str ≤ q) ve výše uvedených sekvencích se vyskytuje méně než 561 kdyby a jen kdyby str - 1 rozdělí q - 1. (viz OEIS: A108574) Kromě toho nejmenší pseudoprime, který má být založen n (také není nutné překračovat n) (OEIS: A090086) je také obvykle semiprime, první protipříklad je A090086 (648) = 385 = 5 × 7 × 11.

Pokud požadujeme n > b, jsou (pro b = 1, 2, ...)

4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, ... (sekvence A239293 v OEIS )

Počty Carmichaelů jsou slabé pseudoprimesi pro všechny báze.

Nejmenší, dokonce slabý pseudoprime v základně 2, je 161038 (viz OEIS: A006935).

Euler – Jacobi pseudoprimes

Dalším přístupem je použití propracovanějších pojmů pseudoprimality, např. silné pseudoprimesi nebo Euler – Jacobi pseudoprimes, pro které neexistují žádné analogy Carmichael čísla. Tohle vede k pravděpodobnostní algoritmy tak jako Test primality Solovay – Strassen, Baityho-PSW test primality a Miller – Rabinův test primality, které vyrábějí tzv průmyslové prvočísla. Průmyslová prvočísla jsou celá čísla, u nichž primitivita nebyla „certifikována“ (tj. Přísně prokázána), ale prošla testem, jako je Miller-Rabinův test, který má nenulovou, ale libovolně nízkou pravděpodobnost selhání.

Aplikace

Vzácnost takových pseudoprimes má důležité praktické důsledky. Například, kryptografie veřejného klíče algoritmy jako např RSA vyžadují schopnost rychle najít velká prvočísla. Obvyklým algoritmem pro generování prvočísel je generování náhodných lichých čísel a test je pro primalitu. Nicméně, deterministický testy primality jsou pomalé. Pokud je uživatel ochoten tolerovat libovolně malou šanci, že nalezené číslo není prvočíslo, ale pseudoprime, je možné použít mnohem rychlejší a jednodušší Fermatův test primality.

Reference

externí odkazy

• W. F. Galway a Jan Feitsma, Tabulky pseudoprimes k základně 2 a související data (úplný seznam všech pseudoprimesů k základu 2 níže 2⁶⁴, včetně faktorizace, silných pseudoprimes a Carmichael čísel)
• Výzkum pro pseudoprime