Advanced algorithms for factorization of natural numbers

Problem faktoryzacji liczb naturalnych polega na znalezieniurozkładu liczby naturalnej na czynniki pierwsze. Aktualnie dostępne metody faktoryzacji nie są w stanie znależć rozkładu dużej liczby w rozsądnym czasie.Z tego powodu problem ten znajduje swoje zastosowanie w kryptografii, gdzie jest podstawą zapewnienia bezpieczeństwa wielu szyfrów, w tym najpopularniejszego z nich RSA.Celem niniejszej pracy było zaimplementowanie zaawansowanych algorytmów faktoryzacji oraz próba zmierzenia się od strony technicznej z aktualnymi rekordamirozkładu dużych liczb naturalnych. Kolejnym celem tej pracy jest jasne i przystępne opisanie algorytmów oraz ich implementacji.W pracy zaimplementowano algorytmy p-1 Pollarda, metodę Lenstry na krzywych eliptycznych jak również Sito Kwadratowe. Wszystkie algorytmy w niniejszej pracy przedstawione są od strony teoretycznej wraz z analizą ich poprawności.W części technicznej pracy omówiono możliwości tych implementacji wraz z wynikami jakie udało się dzięki nim osiągnąć. Największa liczba jaką rozłożyłem posiada 70 cyfr.Wszystkie przedstawione przeze mnie implementacje są dedykowane pod środowiska rozproszone, dzięki czemu na większych chmurach obliczeniowych można uzyskać jeszcze lepsze rezultaty. Materiały i implementacje mogą zostać użyte w celach dydaktycznych jak w i celu bicia dalszych rekordów faktoryzacji liczb naturalnych.

Natural number factorization is the decomposition of a composite numberinto a product of primes. When the numbers are very large, there is no efficient method of finding a solution in a reasonable timeframe. The factorization is widely used in cryptography where it guarantees safety of many algorithms, including RSA.The main goal of this thesis is to implement various factorization algorithms to show their efficiency and to try if it is possible to break current records. The next goal of this thesis is to describe algorithms in clear and meaningful way.In this paper you will find an implementation of p-1 Pollard, Elliptic Curve Method, Quadratic Sieve algorithms. All of these implementations are described from theoretical and technical point of view. In technical part of this thesis I also describe results of the tests and analysis of efficiency for all described algorithms. My best result is factorization of a number with 70 digits.All the code presented in this paper is dedicated for distributed computing. Result of this work can be used for education purposes.