thumb|Przykład rozkładu liczby na czynniki pierwsze: Faktoryzacja liczb całkowitych – rozkład liczby całkowitej większej od 1 na iloczyn czynników całkowitych większych od 1. W pełnym rozkładzie wszystkie czynniki są liczbami pierwszymi. Liczba większa od 1 jest albo pierwsza, albo złożona, czyli da się przedstawić jako iloczyn mniejszych czynników, na przykład Taki rozkład jest jednoznaczny z dokładnością do kolejności czynników na mocy podstawowego twierdzenia arytmetyki.

Faktoryzacja liczb całkowitych jest szczególnym przypadkiem szerszego rozkładu na czynniki, ograniczonym do liczb całkowitych i ich dzielników. W elementarnej arytmetyce rozkład na czynniki pierwsze pomaga opisywać dzielniki liczby. Służy też do obliczania największego wspólnego dzielnika, najmniejszej wspólnej wielokrotności i do upraszczania działań na ułamkach. W informatyce i kryptografii ważne jest natomiast pytanie, jak szybko taki rozkład można znaleźć dla bardzo dużych liczb.

Najprostsza metoda rozkładu polega na sprawdzaniu podzielności przez kolejne liczby pierwsze nie większe niż pierwiastek z rozkładanej liczby. Dla dużych liczb używa się metod specjalnego albo ogólnego przeznaczenia. Skuteczność metod specjalnych zależy od własności szukanego czynnika albo szczególnej postaci liczby. Metody ogólne zależą przede wszystkim od rozmiaru wejścia. Najlepszym znanym algorytmem klasycznym dla dużych, ogólnych wejść jest ogólne sito ciał liczbowych.

Nie jest znany klasyczny algorytm, który rozkładałby dowolną liczbę całkowitą w czasie wielomianowym względem długości jej zapisu binarnego. Nie udowodniono też, że taki algorytm nie istnieje. Trudność faktoryzacji dużych liczb złożonych jest jedną z podstaw bezpieczeństwa kryptosystemu RSA i pokrewnych zastosowań kryptografii klucza publicznego. Szczególne znaczenie mają liczby półpierwsze, czyli iloczyny dwóch dużych liczb pierwszych. Skalowalny, odporny na błędy komputer kwantowy mógłby rozwiązywać ten problem w czasie wielomianowym przy użyciu algorytmu Shora. Taka przewaga nie jest jednak dostępna dla znanych komputerów klasycznych.

Definicja i jednoznaczność rozkładu Jeśli podczas rozkładu otrzymany czynnik jest jeszcze złożony, można rozkładać go dalej, aż wszystkie czynniki będą pierwsze. Dla liczby można na przykład zapisać .

Jednoznaczność rozkładu nie oznacza, że łatwo go znaleźć. Test pierwszości pozwala rozstrzygnąć, czy dana liczba jest pierwsza. Gdy liczba jest złożona, sam wynik testu nie wskazuje jednak jej dzielników. Dlatego algorytm faktoryzacji zwykle łączy wykrywanie nietrywialnych czynników z kolejnym testowaniem, czy znaleziony czynnik jest pierwszy.

Przykłady i zastosowania elementarne Rozkład na czynniki pierwsze daje wygodny zapis informacji o dzielnikach liczby. Niech gdzie są różnymi liczbami pierwszymi. Liczba dodatnich dzielników wynosi wtedy Z takiego zapisu można też odczytać NWD i NWW dwóch liczb. Dla każdego czynnika pierwszego w NWD bierze się mniejszy z wykładników, a w NWW większy z wykładników.

+ Przykładowe użycia rozkładu na czynniki pierwsze Liczba lub para liczb Rozkład Przykładowa informacja ma dodatnich dzielników. Mniejsze wykładniki wspólnych czynników dają Największe wykładniki czynników dają

Trudność obliczeniowa i kryptografia Najtrudniejszymi przypadkami dla znanych metod klasycznych są zwykle duże, losowo dobrane liczby półpierwsze. Ich czynniki pierwsze mają zbliżoną długość bitową, lecz nie leżą zbyt blisko siebie. Właśnie takie liczby pojawiają się w zastosowaniach kryptograficznych. W RSA moduł publiczny jest iloczynem dwóch dużych liczb pierwszych. Bez znajomości tych czynników odwrócenie operacji używanej w systemie jest obliczeniowo trudne, co stanowi podstawę praktycznego bezpieczeństwa RSA.

W 2019 roku zespół badaczy, w którym uczestniczył m.in. Paul Zimmermann, rozłożył 240-cyfrową liczbę RSA-240 o długości 795 bitów. Obliczenia wymagały około 900 lat pracy pojedynczego rdzenia procesora, czyli około 900 rdzeniolat. Autorzy oszacowali, że moduł RSA o długości 1024 bitów wymagałby około 500 razy większego nakładu. W lutym 2020 roku rozłożono RSA-250, 250-cyfrową liczbę półpierwszą. Obliczenia wykonane z użyciem CADO-NFS wymagały około 2700 rdzeniolat pracy. Paul Zimmermann prowadzi zestawienie rekordów faktoryzacji, które wskazuje RSA-250 jako największy opublikowany rozkład liczby RSA wykonany algorytmem ogólnego przeznaczenia.

Problem faktoryzacji jest przykładem zadania, w którym łatwo zweryfikować podane rozwiązanie przez pomnożenie czynników. Znalezienie takiego rozwiązania dla odpowiednio dobranych dużych liczb pozostaje jednak trudne dla znanych metod klasycznych. Dlatego faktoryzacja pojawia się zarówno w teorii złożoności, jak i w analizie założeń trudności obliczeniowej stosowanych w kryptografii.

Złożoność problemu W teorii złożoności wygodnie formułuje się faktoryzację jako problem decyzyjny. Dane są wtedy liczby naturalne i Pytanie brzmi, czy istnieje dzielnik taki, że i dzieli Odpowiedź „tak” można potwierdzić, podając odpowiedni czynnik. Odpowiedź „nie” można potwierdzić przez podanie rozkładu na czynniki pierwsze większe od i sprawdzenie ich pierwszości, na przykład przez test AKS.

Tak sformułowany problem należy do klas NP i co-NP, a także do bardziej restrykcyjnych klas związanych z jednoznacznymi certyfikatami. Nie wiadomo, czy należy do klasy P. Nie jest też znany jako problem NP-zupełny ani co-NP-zupełny. Dlatego często przedstawia się go jako kandydata na problem NP-pośredni. Dzięki algorytmowi Shora problem należy natomiast do kwantowej klasy BQP.

Brak znanego algorytmu wielomianowego nie jest dowodem jego nieistnienia. W literaturze podkreśla się raczej, że aktualna wiedza oddziela skuteczne testowanie pierwszości od znajdowania czynników. Pierwszość można rozstrzygać w czasie wielomianowym. Najlepsze znane algorytmy faktoryzacji ogólnego przeznaczenia mają natomiast czas podwykładniczy, ale nie wielomianowy.

Algorytmy faktoryzacji Algorytmy faktoryzacji można dzielić na metody specjalnego przeznaczenia i metody ogólnego przeznaczenia. Pierwsze wykorzystują szczególną postać rozkładanej liczby albo własności jednego z jej czynników. Drugie są projektowane tak, aby ich czas działania zależał przede wszystkim od rozmiaru samej liczby.

Metody specjalnego przeznaczenia sprawdza podzielność przez kolejne możliwe czynniki do pierwiastka z rozkładanej liczby. Jest wystarczające dla małych liczb i jako etap usuwania małych dzielników, ale staje się niepraktyczne, gdy liczba nie ma małych dzielników pierwszych.

Do metod specjalnego przeznaczenia należą również metoda Fermata, algorytm rho Pollarda, , , , oraz metody oparte na przedstawieniu liczby jako różnicy kwadratów.

Metody ogólnego przeznaczenia Metody ogólnego przeznaczenia mają czas działania zależny głównie od rozmiaru liczby, a nie od szczególnej postaci jej czynników. Najważniejsze przykłady to , , sito kwadratowe, metoda sita liczbowego, ogólne sito ciał liczbowych oraz . Wiele takich metod szuka kongruencji kwadratowych. Taka kongruencja może prowadzić do nietrywialnego dzielnika przez obliczenie największego wspólnego dzielnika.

Dla dużych liczb ogólne sito ciał liczbowych ma najlepszą znaną asymptotyczną złożoność spośród opublikowanych algorytmów klasycznych. Dla liczby jego czas działania zapisuje się zwykle w postaci podwykładniczej zależnej od i :

Metody probabilistyczne i ścisłe oszacowania Wiele algorytmów faktoryzacji ma charakter heurystyczny albo probabilistyczny. Ich typowy czas działania opisuje się przy założeniach o rozkładzie liczb gładkich lub o powodzeniu losowych wyborów. Dla sita kwadratowego oczekiwany czas działania bywa wyrażany w notacji względem rozkładanej liczby Dla metody krzywych eliptycznych ważniejszy jest rozmiar najmniejszego nietrywialnego czynnika pierwszego. Dlatego jej zachowania nie opisuje się po prostu tym samym parametrem co metod ogólnego przeznaczenia.

Osobną linią badań była metoda relacji w grupie klas, rozwijana przez Clausa P. Schnorra, Martina Seysena i Arjena K. Lenstrę. W pierwotnych analizach jej działanie wiązano z założeniami takimi jak uogólniona hipoteza Riemanna, a algorytm używa relacji w grupach klas dodatnio określonych binarnych form kwadratowych o odpowiednim wyróżniku.

Hendrik W. Lenstra i Carl Pomerance uzyskali później ścisłe oszacowanie oczekiwanego czasu dla wariantu tej metody bez odwoływania się do uogólnionej hipotezy Riemanna. Wynik ten pokazał, że można uzyskać rygorystyczny czas oczekiwany rzędu zastępując założenie hipotezy odpowiednim doborem mnożników.

Komputery kwantowe Algorytm Shora, opisany w 1994 roku i opublikowany w pełnej wersji w 1997 roku, rozwiązuje faktoryzację w czasie wielomianowym na komputerze kwantowym. Dla wejścia o długości bitów często podaje się czas rzędu i pamięć rzędu To zasadnicza różnica wobec najlepszych znanych metod klasycznych.

Pierwsze demonstracje algorytmu Shora rozkładały bardzo małe liczby i miały charakter eksperymentalny. W 2001 roku zrealizowano wersję algorytmu przy użyciu technik jądrowego rezonansu magnetycznego na układzie siedmiu kubitów. Była to ważna demonstracja zasady, ale nie stanowiła praktycznego zagrożenia dla dużych kluczy RSA.

Zobacz też rozkład na czynniki test pierwszości RSA (kryptografia) algorytm Shora

Przypisy

Kategoria:Teoria podzielności Kategoria:Teoria liczb Kategoria:Algorytmy faktoryzacji