Program na prvočísla
Prime Numbers Program
Ú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ť.
Verzie:
download súboru - Github:
prime_test_GUI.py (novšia verzia s GUI)
html verzia : prime-numbers-test.html
Popis: Algoritmus obsahuje klasické
vyhľadávanie prvočísiel + špeciálny algoritmus na extrémne veľké čísla.
Algoritmus na extrémne, veľké prvočísla
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.
Introduction
Update: 30.06.2021
This demonstration program shows how quickly prime numbers can be searched today. At the same time, it demonstrates the information published on this blog in connection with prime numbers. You can freely download and use the program.
Versions:
download file - Github:
prime_test_GUI.py (newer version with GUI)
html version: prime-numbers-test.html
Description: The algorithm contains
a classic prime-number search plus a special algorithm for extremely large numbers.
Algorithm for Extremely Large Prime Numbers
In the newer article: Algorithm for extreme prime numbers you can find the complete algorithm,
a Python program for checking extremely large numbers.
This program removes the limitations
of the demonstration program created in Visual Basic, especially the size of the checked number.
Methods - Sieve of Eratosthenes
This method is one of the classic algorithms for finding prime numbers. In the program, prime numbers can be displayed progressively up to the entered number "n" in the test number field. More information about this method can be found, for example, on Wikipedia.
Classic Algorithm
In the demonstration program, this algorithm is partially optimized. It divides the entered number "n" progressively up to sqrt(n), while skipping even numbers and numbers ending in five. It could be optimized in connection with the extended Riemann hypothesis to a value lower than sqrt(n). The relation can be found as a logarithmic relation.
Reduced Little Fermat Theorem
This algorithm was created and designed by the author of the page. Its principle combines the reduced form of Fermat's theorem (see related blog posts) with an optimal search for prime-number periods.
Fermat's theorem requires calculating high powers. In ordinary programming, a variable can overflow already around 2^1000. In the demonstration program this is handled through modular arithmetic relations, where remainders are multiplied instead of calculating huge powers. With large numbers, however, multiplication or exponentiation can still overflow. The program is intended as a demonstration of the correctness and efficiency of this method.
An efficient way of calculating the little Fermat theorem is shown schematically in Fig. 1.
Fig. 1 Graphical course of remainders, source: author's own image.
The course of remainders 2^x mod p can be viewed for small prime numbers in the file: prvocisla_pokusy.xlsx.
An efficient method can avoid unnecessarily calculating large powers, which take many digits, require conversion, and exceed the size limits of common variables. Instead of direct exponentiation of 2^x, we use the following relation:
example:
2 ^500 mod p =a, 2 ^1000 mod p=(a*a)/mod p=b, 2 ^2000 mod p=(b*b)/mod p=c
Algorithm for applying Fermat's theorem to extremely large numbers, implemented in Python:
Fig. 2 Use of Fermat's theorem and efficient calculation through remainders: author Robopol.
Mersenne Prime Numbers
The program lists the first 51 Mersenne prime numbers. It also contains calculations for higher prime numbers. This method uses a very short period T equal to the exponent of the power, valid for base a=2 in the little Fermat theorem. Therefore, candidates for further Mersenne prime numbers can be checked extremely quickly. For base a=2, however, there are many pseudoprimes, so to verify whether a given number is truly prime, calculations for other bases such as a=3,4,5... would also be required. Still, the initial search for additional prime candidates is extremely fast and shows that if the exponent of a Mersenne number is prime, there is a good probability that it may be another Mersenne prime number.
The Mysterious Number 24
In an internet discussion I came across the hypothesis that:
for p=prime number, p>3 it
holds:
(p^2 - 1) Mod 24=0
The hypothesis was checked for all numbers from >3 to 999,999,999. For deciding whether a number is prime, this hypothesis is not sufficient, because the condition is satisfied by about one tenth of numbers. However, it is a good initial filter for identifying composite numbers. If the hypothesis holds as n approaches infinity, it suggests a structural filter in the distribution of prime numbers.
Proof:
Every prime number belongs to the set of odd numbers expressed by the relation (6k+-1), for k=1,2,3....n.
Substitute for p:
(6k+-1)^2 -1 Mod 24=0
(36k^2+-12k+1) -1 Mod 24=0
36k^2+-12k Mod 24=0 //extract 12k
12k (3k+-1) Mod 24 =0
For k=1,3,5... (every odd k), the term (3k+-1) in the equation is always divisible by 2, so we get:
12k *(2*i) mod 24=0, where i =1,2,3...n, and after modifying the equation:
24k*i mod 24=0
We obtain equality because any multiple of 24 modulo 24 is zero.
For k=2,4,6,8 (every even k), the term (3k+-1) always gives an odd number "j". The term 12k, however, always gives a multiple of 24, because k is always divisible by 2, so:
(24*(k-1) *j) mod 24 =0, where "j" is a natural number, and the equation is always satisfied because any integer multiple of 24 Mod 24 gives zero.