Pollard methods for factorization

U teoriji brojeva, cjelobrojna faktorizacija je rastav složenog cijelog broja u produkt manjih cijelih brojeva. Ako su ti brojevi dodatno ograničeni na proste faktore, onda ovaj proces nazivamo rastav broja na proste faktore. Faktorizacija cijelih brojeva već je od davnina predmet proučavanja brojnih matematičara. Pronalazak prostog faktora nekog složenog broja smatra se teškim problemom i često se primjenjuje u kriptografiji. John M. Pollard je osmislio dvije bitne metode za faktorizaciju velikih prirodnih brojeva: \(\rho \) (rho) metodu i \( p \) − 1 metodu. Pollardova \(\rho \) metoda je efikasna za velike brojeve koji imaju barem jedan mali prosti faktor. Ideja metode je prvo konstruirati niz cijelih brojeva \( (x_i) \)modulo \( p \), gdje je \( p \) prosti faktor koji tražimo. Zatim treba pronaći period tog niza te naposljetku odrediti prosti faktor \( p \). Ovakav algoritam za faktorizaciju je neefikasan ako je period niza velik. Matematičari poput Floyda i Brenta su, koristeći svoje algoritme za pronalaženje ciklusa u nizu, dodatno poboljšali Pollardovu \(\rho \) metodu. Floydova varijanta se temelji na paralelnom računanju nizova \( (x_i) \) i \((x_{2i})\) te računanju gcd \(\gcd{(x_{2k}-x_k, n)} \). Kod Brentove varijante računamo niz \( (x_i) \)te gcd \({(x_i-x_{2^k-1}, n)} \) za \(k\in\mathbb{N}\) i \(3 \cdot 2^{k-1} \leq i \leq 2^{k+1}-1\). U obje varijante smo gotovi ako smo dobili da je gcd > 1, no može se dogoditi da nam algoritmi ne daju prosti faktor kao izlaz. Metode se dodatno mogu ubrzati periodičnim računanjem najvećeg zajedničkog djelitelja. Analognu metodi za faktorizaciju, Pollard je izumio i \(\rho \) metodu za izračun diskretnih logaritama. Problem diskretnog logaritma za cikličku grupu G se bavi pronalaskom broja k takvog da vrijedi \(h=g^k\) za neki element \(h\in G\), gdje je g neki generator grupe. Ovaj problem se također smatra teškim te se primjenjuje u kriptografiji. Objasnili smo Pollardovu \(\rho \) metodu za problem diskretnog logaritma za grupu \(\mathbb{Z}_p^*\), gdje je \( p \) neparan prosti broj. Pollardova \( p \) − 1 metoda se temelji na Malom Fermatovom teoremu. Uspješna je za velike brojeve za koje vrijedi da se faktorizacija broja \( p \) − 1 sastoji samo od malih prostih faktora, gdje je \( p \) prosti faktor broja kojeg želimo faktorizirati. Ideja je pronaći neki višekratnik m od \( p \)−1 te pomoću Euklidovog algoritma izračunati faktor \( p \). Dakle, ako dobijemo da je \(\gcd{(a^m-1, n)}\) netrivijalan, pronašli smo faktor od \( n \). I ova metoda nam može ne dati prosti faktor kao izlaz. Ako za izlaz dobijemo da je najveći zajednički djelitelj jednak 1, možemo primijeniti drugu fazu algoritma, tzv. varijaciju velikog prostog broja.In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further limited to prime numbers, the process is called prime factorization. Integer factorization has been a subject of study by many mathematicians for a long time. Finding a prime factor of a composite number is considered a difficult problem and is often used in cryptography. John M. Pollard has invented two essential methods for factorizing large positive integers: \(\rho \) (rho) method and \( p \) − 1 method. Pollard’s \(\rho \) mehod is effective for large numbers that have at least one small prime factor. The idea is to first construct a sequence of integers \( (x_i) \) modulo \( p \), where \( p \) is the prime factor we are trying to find. Then we need to find the period of this sequence and finally determine the prime factor \( p \).This factorization algorithm is inefficient if the period of the sequence is large. Mathematicians like Floyd and Brent further improved Pollard’s ρ method by using their cycle finding algorithms. Floyd’s variant is based on the parallel calculation of the sequences \( (x_i) \) and \((x_{2i})\) and the calculation of \(\gcd{(x_{2k}-x_k, n)} \). For the Brent variant, we compute the sequence \( (x_i) \) and gcd \({(x_i-x_{2^k-1}, n)} \) for \(k\in\mathbb{N}\) i \(3 \cdot 2^{k-1} \leq i \leq 2^{k+1}-1\). In both variants we are done if we get that gcd > 1, but it may happen that the algorithms do not give us a prime factor as the output. Methods can be further accelerated by periodically calculating the greatest common divisor. Analogous to the factorization method, Pollard invented the \(\rho \) method for calculating discrete logarithms. The discrete logarithm problem for a cyclic group G concerns finding the number k such that \(h=g^k\) is valid for some element \(h\in G\), where g is a generator of the group. This problem is also considered difficult and is applied in cryptography. We have explained Pollard’s \(\rho \) method for the discrete logarithm problem for the group \(\mathbb{Z}_p^*\), where \( p \) is an odd prime number. Pollard’s \( p \) − 1 method is based on Little Fermat’s theorem. It is successful for large numbers for which it is true that the factorization of the number \( p \) −1 consists only of small prime factors, where \( p \) is the prime factor of the number we want to factorize. The idea is to find a multiple m of \( p \) − 1 and use the Euclidean algorithm to calculate the factor \( p \). So if we get that gcd \(\gcd{(a^m-1, n)}\) is non-trivial, we have found a factor of n. This method may also not give us a prime factor as a output. If for the output we get that the greatest common divisor is equal to 1, we can apply the second phase of the algorithm, the so-called large prime variation