Úvod
Update: 30.06.2021
Tento demonštračný program slúži na ukážku toho, ako sa dnes rýchlo dajú hľadať prvočísla. Zároveň demonštruje všetky uvedené informácie na tomto blogu (v súvislosti s prvočíslami). Program si môžete voľne stiahnuť a používať.
LINK: setup_prime_numbers_GUI_2024.rar : komprimované WinRar
Stiahnite
si inštalačný súbor, rozbaľte v programe WinRar, nainštalujte do PC, nainštaluje sa Vám ikona v ponuke štart, súbor je
bezpečný, povoľte nainštalovať súbor cez antivírovú ochranu.
Algoritmus na extrémne, veľké prvočísla
Obr.3 Ukážka kódu programu v Pythone, zdroj: vlastný obrázok.
V novšom článku: Algoritmus na extremne prvocisla nájdete kompletný algoritmus, program v pythone na preverenie extrémne veľkých čísiel.
Tento program odstraňuje nedostatky (hlavne vo veľkosti preverovaného čísla) demonštračného programu vytvoreného vo visual basic.
Metódy - Eratostenovo
sito
Táto metóda patrí medzi klasické algoritmy na hľadanie prvočísiel, v programe je možné si zobraziť postupne prvočísla po zadané číslo „n“ – (kolónka test number). Viac informácii o tejto metóde nájdete napr. na Wikipédii.
Klasický algoritmus
V demonštračnom programe je čiastočne optimalizovaný, kde tento algoritmus delí zadané číslo- „n“ postupne do hodnoty sqrt(n). Pričom nedelí číslo párnymi číslami, ani číslami končiacimi päťkou. Dal by sa optimalizovať v súvislosti s rozšírenou Riemanovou hypotézou do hodnoty menšej ako je sqrt(n). Vzťah sa dá nájsť (logaritmický vzťah).
Redukovaná malá, Fermatová veta
Tento algoritmus je vytvorený a navrhnutý autorom
stránky. Jeho princíp je zmesou využitia redukovanej, Fermatovej vety (viď. príspevky
na blogu), využitia toho ako optimálne hľadať periódu prvočísiel.
Fermatová veta potrebuje počítať vysoké mocniny, pri bežnom programovaní premenná pretečie u hodnoty 2^1000. V demonštračnom programe to je urobené tak, že využíva vzťahy modulárnej aritmetiky, kde medzi sebou násobí zvyšky miesto výpočtu obrovských mocnín. No pri veľkých číslach pretečie násobenie, či umocňovanie. Program je určený ako ukážka správnosti a efektívnosti tejto metódy.
Efektívny spôsob rátania malej Fermatovej vety je schematicky znázornený na obr.1.
Obr.1 Grafický priebeh zvyškov , zdroj: vlastný obrázok.
Priebeh zvyškov 2^x mod p si môžete pozrieť pre male prvočísla v súbore: prvočísla_pokusy.xlsx.
Dá sa nájsť efektívna metóda ako zbytočne nerátať veľké mocniny (zaberajú hodne číslic, potrebujú konverziu, bežne premenné sú ohraničené veľkosťou, napr. 16 číslic) tak, že miesto umocňovania 2^x využijeme to, že platí:
príklad:
2 ^500 mod p =a, 2 ^1000 mod p=(a *a)/mod p=b, 2 ^2000 mod p=(b*b)/mod p=c
Algoritmus pre aplikáciu Fermatovej vety, pre extrémne veľké čísla, program v Pythone:
Obr. 2 Využitie Fermatovej vety a efektívneho rátania pomocou zvyškov: autor Robopol.
Mersennové prvočísla
Program vypíše prvých 51 Mersennových prvočísiel. Zároveň obsahuje výpočet pre vyššie prvočísla. Pri tomto spôsobe je využitá veľmi krátka perióda T=exponent mocniny, platí pre základ a=2 malej, Fermatovej vety. Teda je možné extrémne rýchlo preveriť kandidátov na ďalšie Mersennové prvočísla. Pre základ a=2 však existuje pomerne veľa pseudoprvočísiel, teda pre optimalizáciu toho, či dané číslo je naozaj prvočíslo by sme museli urobiť výpočty aj pre iné základy a=3,4,5... No prvotný nestrel ďalších prvočísiel je extrémne rýchly a ukazuje to, že pokiaľ je exponent Mersennoveho čísla prvočíslo, potom je dobrá pravdepodobnosť, že to môže byť ďalšie Mersennové prvočíslo.
Záhadné číslo 24
V diskusii na internete som narazil na hypotézu, že:pre p=prvočíslo, p>3 platí:
(p ^ 2 - 1) Mod 24=0
Hypotéza bola preverená pre všetky čísla od >3 po 999 999 999. Pre určenie, či sa jedná o prvočíslo táto hypotéza nepostačuje, pretože podmienku spĺňa zhruba 1/10 čísiel. No je to dobrý, úvodný filter, pre určenie zložených čísiel. V tejto hypotéze (pri platnosti) n ---> infinity, táto hypotéza naznačuje filter štruktúry rozloženia prvočísiel.
Dôkaz:
Každé prvočíslo patrí do množiny nepárnych čísiel vyjadrených vzťahom (6k+-1), pre k=1,2,3....n.
Dosaďme za p:
(6k+-1)^2 -1 Mod 24=0
(36k ^2 +-12k+1) -1 Mod 24=0
36k ^2 +-12k Mod 24=0 //vyjmeme 12k
12k (3k+-1) Mod 24 =0
člen (3k+-1) v rovnici je pre k=1,3,5...(každé nepárne k) vždy deliteľný 2, ostane nám
12k *(2*i) mod 24=0 , pričom i =1,2,3...n, upravíme rovnicu
24k*i mod 24=0
Dostali sme rovnosť pretože akýkoľvek násobok 24 mod 24 je nula.
pre člen (3k+-1) v rovnici pre k=2,4,6,8 (každé párne k) nám dá vždy nepárne číslo "j". Člen 12k nám však dá vždy násobok čísla 24, pretože k je vždy deliteľné 2, teda platí:
(24*(k-1) *j) mod 24 =0, pričom "j" je prirodzené číslo a uvedená rovnica spĺňa vždy rovnosť, pretože akýkoľvek násobok (celým číslom) 24 Mod 24 dá vždy nulu.