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 serves to show how quickly prime numbers can be searched today. At the same time, it demonstrates all the information mentioned on this blog (related to 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 classic prime number search + special algorithm for extremely large numbers.
Algorithm for Extremely Large Prime Numbers
In newer article: Algorithm for extreme prime numbers you will find a complete algorithm, a Python program for checking extremely large numbers.
This program eliminates the shortcomings (especially in the size of the number to be checked) of the demonstration program created in Visual Basic.
Methods - Sieve of Eratosthenes
This method belongs among the classic algorithms for finding prime numbers. In the program, it is possible to display prime numbers progressively up to the given number "n" - (test number column). More information about this method can be found, for example, on Wikipedia.
Classic Algorithm
In the demonstration program it is partially optimized, where this algorithm divides the given number "n" progressively up to the value sqrt(n). It does not divide the number by even numbers or numbers ending with five. It could be optimized in connection with the extended Riemann hypothesis to a value less than sqrt(n). The relation can be found (logarithmic relation).
Reduced Little Fermat's Theorem
This algorithm is created and designed by the author of the page. Its principle is a mixture of using the reduced Fermat's theorem (see blog posts), using how to optimally search for the period of prime numbers.
Fermat's theorem needs to calculate high powers, in normal programming the variable overflows at value 2^1000. In the demonstration program, this is done by using modular arithmetic relations, where it multiplies remainders among themselves instead of calculating huge powers. But with large numbers, multiplication or exponentiation overflows. The program is intended as a demonstration of the correctness and efficiency of this method.
An efficient way of calculating little Fermat's theorem is schematically shown in Fig.1.
Fig.1 Graphical course of remainders, source: own image.
The course of remainders 2^x mod p you can view for small prime numbers in the file: prvočísla_pokusy.xlsx.
An efficient method can be found how not to unnecessarily calculate large powers (they take many digits, need conversion, common variables are limited by size, e.g., 16 digits) so that instead of exponentiation 2^x we use that it holds:
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 application of Fermat's theorem, for extremely large numbers, Python program:
Fig. 2 Use of Fermat's theorem and efficient calculation using remainders: author Robopol.
Mersenne Prime Numbers
The program lists the first 51 Mersenne prime numbers. It also contains calculation for higher prime numbers. In this method, a very short period T=exponent of power is used, which holds for base a=2 of little Fermat's theorem. Therefore, it is possible to extremely quickly check candidates for other Mersenne prime numbers. For base a=2, however, there are quite a lot of pseudoprimes, so for optimization of whether the given number is really prime we would have to do calculations for other bases a=3,4,5... But the initial search for other prime numbers is extremely fast and shows that if the exponent of a Mersenne number is prime, then there is a good probability that it could 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 holds:
(p^2 - 1) Mod 24=0
The hypothesis was verified for all numbers from >3 to 999,999,999. For determining whether it is a prime number, this hypothesis is not sufficient, because the condition is satisfied by about 1/10 of numbers. But it is a good, initial filter for determining composite numbers. In this hypothesis (if valid) n ----> infinity, this hypothesis suggests a filter of prime number distribution structure.
Proof:
Every prime number belongs to the set of odd numbers expressed by the relation (6k+-1), for k=1,2,3....n.
Let's 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
the term (3k+-1) in the equation for k=1,3,5...(every odd k) is always divisible by 2, we have left
12k *(2*i) mod 24=0, where i =1,2,3...n, we modify the equation
24k*i mod 24=0
We got equality because any multiple of 24 mod 24 is zero.
for the term (3k+-1) in the equation for k=2,4,6,8 (every even k) always gives us an odd number "j". The term 12k, however, always gives us a multiple of number 24, because k is always divisible by 2, so it holds:
(24*(k-1) *j) mod 24 =0, where "j" is a natural number and the given equation always satisfies equality, because any multiple (by a whole number) of 24 Mod 24 always gives zero.