Vylepsene hladanie prvocisiel_2_diel

Úvod

Tento diel je pokračovaním článku Vylepšené hľadanie prvočísiel. Toto vylepšené hľadanie prvočísiel je postavené na geometrickom aspekte malej Fermatovej vety. Predchádzajúce diely boli medziproduktom (zisťovaním) toho, aby sa dal definovať ucelený algoritmus, ktorý samozrejme poskytne nový pohľad na problematiku prvočísiel.

Geometrický aspekt Fermatovej vety poskytol nový pohľad, poskytol zjednodušenie samotnej formuly Fermatovej vety, teda v zmysle výpočtovej náročnosti (pre veľké prvočísla). Čísla môžu ísť do nekonečna a žiaden počítač nie je schopný preveriť ľubovoľné prvočísla. Tento fakt sa využil v RSA šifrovaní. Toto šifrovanie chráni prístup a hesla.


Delenie intervalu 2ˆint(p/2)

V predchádzajúcom článku bolo naznačené, že by sme mohli deliť interval x, resp. interval y, a tak znižovať mocninu malej Fermatovej vety. Tento diel poskytne úplnú a pravdivú metódu, ako redukovať mocninu vo výraze 2ˆint(p/2)= 2ˆ((p-1)/2).

Vieme, že predelením x- intervalu 2ˆ(int(p/2)+1)/2, dostaneme 2ˆint(p/2), teda sme znížili mocninu o jeden rad a všetky prvočísla končia +-1 od tohto „stredu“. (viď. predošlé diely).

Zadefinujme usporiadanú dvojicu celých čísiel [m,n], ktoré budú reprezentovať vzdialenosti sledu prvočísiel (začiatky a konce), od stredu predelenia intervalu -x, alebo intervalu – y.

Screenshot - 6_ 7jpg

Pokračovaním, tohto delenia dostaneme:


Redukovaná Fermatová veta:

Reduced_Fermat_theorempng

Vzťahy sa dajú taktiež urobiť aj pre y- smer, zvyšok y(1) a zvyšok y(2). Tieto vzťahy sú rovnocenné ako pre x – smer.

Náčrt algoritmu - príklady

My nemusíme počítať obrovské mocniny, redukovaná Fermatová veta nám dovolí vytvoriť takýto algoritmus:
Reduced_Fermat_theorem_example1png

Reduced_Fermat_theorem_example2png
Z príkladov vidieť, že pre prvočísla nebolo potrebné hľadať výsledky m(i), n(i) algoritmom, pretože to bude vždy rovné. Ak je skúmané číslo -zložené číslo, redukovaná rovnica nájde falošný m(i), n(i). Doposiaľ som nenašiel jednoduchšiu, výpočtovo nenáročnú metódu, ako odhaliť falošné hodnoty m(i), n(i) pre zložené čísla (bez použitia algoritmu, či výpočtom rovnice s vysokým exponentom- článok vylepšené hľadanie prvočísiel 1. diel).
Algoritmus sa dá samozrejme optimalizovať, pretože pri zložených číslach sa prejaví perióda a následne budeme vedieť, že ide o zložené číslo, skôr ako vypočítame cieľovú hodnotu m(i), n(i).
Existujú aj iné významné úrovne a súvisí to s periódou m(i), n(i). Periódy všetkých prvočísiel sa dajú veľmi efektívne hľadať ,bez použitia uvedené algoritmu na m(i),n(i), viac v diely o algoritme na prvočísla.

Pre zaujímavosť:
Ak do predchádzajúceho algoritmu pre m(i), n(i) začleníme aj výpočet hodnôt k(i), l(i) odhalíme, či je naše skúmané číslo - "p" zložené číslo. Hodnoty k(i), l(i) nebudú obsahovať deliteľov skúmaného čísla "p".

Screenshot - 10_ 7png


Záver

Metóda je plne funkčná, poskytuje správne výsledky. Hodnoty m(i), n(i) pre ľubovolne prvočíslo, cez redukovanú, malú Fermatovú vetu sa dajú zistiť bez použitia hľadania algoritmom. Pre zložené čísla je však nutné použiť algoritmus pre overenie. Ak sa výsledky nezhodujú ide o zložené číslo.
Problém prvočísiel sa zdá ďalej nejde redukovať. Už aj z analýzy malej Fermatovej vety (vrátane tu opísaného algoritmu) vyplýva, že zrejme neexistuje žiadna čarovná formula, ktorá nájde prvočíslo bez hľadania. To samozrejme nie je prekvapivé.