Proth Prime Search (LLR)

François Proth (1852 - 1879) byl francouzský samouk, matematik a farmář, který žil v Vaux-devant-Damloup u Verdunu ve Francie .

V oblasti výzkumu prvočísel vyslovil celkem čtyři věty. Nejslavnější z nich vychází z tzv. Prothova čísla. Uvádí, že „p“ - Prothovo číslo se vypočítá k 2 ⁿ  + 1 (kde „k“ je liché celé číslo, menší než „2 n {\displaystyle 2^{n}}2 ⁿ“, tedy k  <2 ⁿ).

Například: 3 * 2² + 1 = 13

Posloupnost Prothových čísel začíná 3, 5, 9, 13, 17, 25, 33, 41, 49, 57, 65, 81, 97, 113, 129, 145, 161, 177, 193, 209, …

Pokud při dosazení „p“ do vzorečku vyjde celé číslo „a“, jedná se o prvočíslo (tzv. Prothova věta). Tato prvočísla dostala pojmenování Prothova prvočísla.

Jak vzoreček číst? Trojité rovnítko se jmenuje kongruence. Zápis x ≡ y (mod p) značí, že x a y mají stejný zbytek po dělení číslem p, tedy že x − y je dělitelné číslem p.
Výraz x ≡ y (mod p) platí například pro čísla 5 ≡ 11 (mod 3), protože dělíme-li 5 číslem 3, je výsledek 1 a zbytek po dělení je 2. A dělíme-li 11 číslem 3, je výsledek 3 a zbytek po dělení je opět 2. Přepsáním do toho druhého tvaru dostaneme výraz: „5 – 11 je dělitelné číslem 3“, což platí, 5 – 11 = (-6).
Ve výše uvedeném vzorečku je a^(p-1)/2 tím číslem x a (-1) je tím číslem y.

Například:
- Prothovo číslo p = 3 získáme 1(2¹) + 1. Při dosazení do vzorečku 2^(3-1)/2 + 1 nám vyjde 3. Trojka je dělitelná trojkou, takže 3 je prvočíslo.
- pro p = 5 = 1(2²) + 1, máme 3^(5-1)/2 + 1 = 10 je dělitelné pětkou, takže 5 je prvočíslo
- pro p = 13 = 3(2²) + 1,máme 5^(13-1)/2 + 1 = 15626 je dělitelné třináctkou, takže 13 je prvočíslo
První Prothovo číslo, které není Prothovým prvočíslem je p = 9. Tedy platí, že a^(9-1)/2 + 1 není dělitelné 9. Jinými slovy neexistuje žádné a, pro které by a^(9-1)/2 + 1 (tedy a⁴ + 1), bylo dělitelné devíti.

Posloupnost Prothových prvočísel začíná: 3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153,…

Projekt se v úvodní fázi snažil doplnit všechna chybějící Prothova prvočísla až do n=200.000. Následně docházelo k postupnému navyšování této laťky na nynějších (rok 2020) n=800.000. Aktuálně je projekt rozdělen na tři fází:

• Proth Prime Search (LLR) - "n < 800.000" - tedy prohledávání a doplnění řady všech Proth prvočísel do "n < 800.000"
• Proth Prime Search Extended (LLR) - "n = 800.000 - 1.000.000"
• Proth Mega Prime Search (LLR) - "n > 1.000.000"

Hledání Prothových prvočísel v oblasti Prothových čísel je zároveň důležité při hledání největších známých prvočísel na světě. Jelikož je daná jasná oblast výzkumu (generovaná Prothova čísla) a jednoznačné zadání toho, jak u těchto čísel ověřit, zda se jedná, nebo nejedná o prvočísla, tedy Prothova prvočísla.
 

Mezi speciální případy Prothových čísel patří Cullenova čísla a Fermatova čísla.

https://otik.zcu.cz/bitstream/11025/19814/1/DP_Hefler_PrvocislaAFaktorizace.pdf
https://cs.wikipedia.org/wiki/Prothovo_%C4%8D%C3%ADslo
https://en.wikipedia.org/wiki/Proth%27s_theorem