Przejdź do treści

Liczby pierwsze, dzielniki

Szukanie liczb pierwszych i rozkład liczby na czynniki pierwsze zajmują w informatyce wyjątkowo ważne miejsce. Jak dowiemy się w trakcie lekcji, byłoby lepiej dla światowego bezpieczeństwa, aby te problemy okazały się ... trudne. I jak dotąd, rzeczywiście nie potrafimy szybko znajdować czynników pierwszych dla bardzo dużych liczb.

Małe liczby potrafimy jednak rozkładać dość skutecznie. Zacznijmy od problemu szukania dzielników zadanej liczby:

Dzielniki i pierwszość

Bardzo łatwo napisać program znajdujący (i, na przykład, wypisujący na wyjście) wszystkie dzielniki zadanej liczby n:

for(int i = 1; i <= n; i++)
    if (n % i == 0)
        cout << i;

Program ten ma w oczywisty sposób złożoność \(O(n)\). Istnieje łatwy sposób przyśpieszenia tego algorytmu – popatrzmy, jakie dzielniki ma, na przykład, liczba 36:

36 = 1 * 36
36 = 2 * 18
36 = 3 * 12
36 = 4 * 9
36 = 6 * 6

Dzielniki można pogrupować w pary: jeden czynnik z pary jest zawsze mniejszy lub równy 6, drugi zawsze większy lub równy 6. W ogólnym wypadku jeden czynnik będzie mniejszy lub równy \(\sqrt{n}\), drugi większy lub równy \(\sqrt{n}\). Będziemy więc szukać tylko mniejszych dzielników, większe wyliczając na ich podstawie:

for(int i = 1; i * i <= n; i++)
    if (n % i == 0)
    {
        cout << i;
        cout << n / i;
    }

Teraz mamy w algorytmie tylko jedną pętlę, wykonującą \(\sqrt{n}\) iteracji – złożoność algorytmu jest więc \(O(\sqrt{n})\).

Zauważmy, że przy okazji rozwiązaliśmy inny problem: potrafimy w złożoności \(O(\sqrt{n})\). sprawdzić, czy zadana liczba n jest liczbą pierwszą. Wystarczy w tym celu przekonać się, że nie ma żadnego dzielnika "małego" (mniejszego lub równego \(\sqrt{n}\)):

bool czy_pierwsza(int n)
{
    for(int i = 2; i * i <= n; i++)
        if (n % i == 0)                // jeśli n ma mały dzielnik większy od 1
            return false;              // to nie jest pierwsza

     return true;                      // jeśli nie ma małych dzielników, to nie ma żadnych
}

Sito Eratostenesa

Powyższy algorytm ma niezłą skuteczność, jeśli musimy sprawdzić pierwszość jednej, zadanej liczby. Gdybyśmy jednak musieli znaleźć wszystkie liczby pierwsze mniejsze od pewnego \(N\), lepiej użyć znacznie szybszego (a przy tym znanego już starożytnym) sposobu, zwanego sitem Eratostenesa.

Najpierw piszemy w rzędzie wszystkie liczby \(2, 3, ..., N\), po czym bierzemy najmniejszą liczbę – w tej chwili jest to 2 – i wykreślamy wszystkie jej wielokrotności (które oczywiście nie mogą być liczbami pierwszymi). Teraz bierzemy najmniejszą liczbę, której (3), wykreślamy wszystkie jej wielokrotności, i powtarzamy operację, dopóki to możliwe. Niewykreślone liczby, które rozpatrywaliśmy po drodze (2, 3, 5, ...) to liczby pierwsze, co łatwo udowodnić: o każdej z nich wiemy, że nie mogła być wielokrotnością żadnej mniejszej liczby, skoro nie została wcześniej wykreślona.

bool tablica[N+1];           // tablica[j] == false, jeśli liczba jest wykreślona, true jeśli nie jest

for(int i = 2; i <= N; i++)
    tablica[i] = true;

for(int i = 2; i <= N; i++)  // bierzemy kolejną liczbę i
    if (tablica[i])          // jeśli nie jest wykreślona
        for(int j = 2 * i; j <= N; j = j + i)   // iterujemy się po wszystkich wielokrotnościach i
            tablica[j] = false;

Interesujące jest pytanie o złożoność tego algorytmu. Przede wszystkim, raz sprawdzamy każdą liczbę, w zewnętrznej pętli, pod kątem tego, czy została wykreślona, czy też musimy ją rozpatrywać. To daje \(N\) operacji. Oprócz nich pozostały właściwie tylko operacje wykreślania, policzmy je więc osobno:

Podczas rozpatrywania liczby 2 wykonamy \(\frac N2\) operacji – tyle jest wielokrotności do wykreślenia. Podczas rozpatrywania liczby 3 wykonamy operacji \(\frac N3\), potem \(\frac N5\), \(\frac N7\), i tak dalej. Całkowita liczba wykreśleń wynosi \(\frac N2 + \frac N3 + \frac N5 + \frac N7 + ... = N \cdot (\frac 12 + \frac 13 + \frac 15 + \frac 17 + ...)\), gdzie w nawiasie sumowane są wszystkie odwrotności liczb pierwszych, nie większych od \(N\). Dokładne oszacowanie sumy wykraczałoby daleko poza ramy tego wykładu, wystarczy nam zatem wiedzieć, że suma jest równa jest \(\log \log N\) (logarytmowi z logarytmu z \(N\)), pomnożonemu przez pewną stałą.

Całkowita złożoność algorytmu wynosi zatem \(O(N \log \log N)\). Należy zauważyć, że \(\log \log N\) jest dla wszystkich praktycznych danych bardzo małą liczbą (na przykład dla \(N = 10^{82}\), szacowanej liczby cząstek we Wszechświecie, \(\log \log N\) nie przekroczy 9). Algorytm ten jest więc w praktyce nieodróżnialny od algorytmów liniowych.

Zadanie: rozkład na czynniki

Jednym z zadań dołączonych do dzisiejszej lekcji jest rozkład danej liczby \(N\) na czynniki pierwsze. Co więcej, należy tego rozkładu dokonać w czasie \(O(\sqrt{N})\), inaczej (prawdopodobnie) program przekroczy limity czasowe. Zalecamy w tym zadaniu pamiętac o dwóch rzeczach:

  • Okazuje się, że wystarczy znaleźć czynniki pierwsze mniejsze od \(\sqrt{N}\) i podzielić \(N\) przez nie – na przykład rozkładając \(N = 110\), znajdujemy dzielniki pierwsze 2 i 5, a po podzieleniu przez nie pozostaje 11. W ogólnym wypadku albo zostanie 1 (czyli \(N\) nie ma już więcej dzielników), albo jakaś inna liczba. Jaka musi być ta pozostała liczba?
  • Można oczywiście szukać liczb pierwszych (na przykład sitem Eratostenesa), aby dzielić \(N\) kolejno przez nie, ale nie jest to konieczne. Po prostu spróbujmy podzielić \(N\) przez 2 tyle razy, ile się uda, a potem analogicznie przez 3. Teraz mamy pewność, że nie uda się podzielić przez 4 – liczba w tym momencie na pewno nie jest parzysta – ani przez 6. Przez jakie liczby uda się nam w ten sposób podzielić N, a przez jakie na pewno nie?

Znaczenie praktyczne, czyli algorytm RSA

Jeden z najpopularniejszych, najczęściej stosowanych algorytmów szyfrowania, zwany (od nazwisk twórców) algorytmem RSA, opiera się bardzo istotnie na problemie rozkładu na czynniki. W algorytmie tym wybiera się bardzo duże (na przykład mające po kilka setek cyfr) liczby pierwsze \(p\) oraz \(q\) i oblicza się ich iloczyn \(pq\), który można podać do publicznej wiadomości. Algorytm RSA pozwala zaszyfrować wiadomość, znając wyłącznie iloczyn \(pq\) – tak więc wysłać zakodowaną wiadomość może każdy. Aby jednak ją odszyfrować, trzeba znać liczby \(p\) i \(q\), czyli rozłożyć \(pq\) na czynniki.

Zauważmy, że nasze algorytmy są tu bezużyteczne – liczba o 100 cyfrach miałaby wielkość około \(10^{100}\), więc algorytm sprawdzania dzielników potrzebowałby aż \(10^{50}\) operacji – na każdym komputerze trwałoby to o wiele dłużej, niż wynosi wiek Wszechświata. Jeśli ktoś zatem nie znajdzie pewnego dnia istotnie szybszych algorytmów rozkładu na czynniki, można przyjąć, że szyfrowanie tą metoda jest bezpieczne. Ze względu na to, jak szeroko ten algorytm jest stosowany, dobrze byłoby, gdyby rzeczywiście problem rozkładu na czynniki okazał się niemożliwy do szybkiego pokonania. Jak dotąd, nie mamy jednak takiej pewności.

Ciekawostką jest fakt, że podobny problem – sprawdzania, czy liczba jest pierwsza – daje się rozwiązać znacznie prościej. Od dawna znane były algorytmy probabilistyczne (takie, które dawały dobry wynik z bardzo dużą szansą, tym większą, im dłużej działały), a w 2002 roku trzech naukowców z Indii podało pierwszy deterministyczny (czyli "klasyczny") algorytm, który szybko sprawdza pierwszość.

Dodatek: arytmetyka modulo liczba pierwsza

W zadaniu o szybkim potęgowaniu na lekcji 2 należało obliczyć wynik pewnego działania ale wystarczyło podać jego cztery ostatnie cyfry, czyli resztę z dzielenia przez 10000. W rozwiązaniu korzystaliśmy z faktu, że reszta z dzielenia zachowuje się "dobrze" przy mnożeniu i dodawaniu (a także odejmowaniu, ale tej własności nie używaliśmy): jeśli na przykład chcemy pomnożyć przez siebie wiele liczb i znaleźć resztę z dzielenia iloczynu przez jakieś \(M\), możemy zamiast tego domnażać wynik po kolei przez każdą liczbę oddzielnie, i po każdej operacji brać resztę z dzielenia. Innymi słowy, możemy wyobrażać sobie, że cały czas działamy na liczbach między 0 a \(M-1\), a wynikami dodawania, mnożenia, a także odejmowania, również są takie liczby. Mówimy wtedy o działaniach modulo \(M\), a ogólniej o arytmetyce modulo \(M\).

Problem pojawia się dopiero, gdy chcemy dokonać dzielenia. Z definicji dzielenie jest odwrotnością mnożenia – każde dzielenie możemy zapisać jako mnożenie przez liczbę odwrotną: \(a \div b = a \cdot \frac{1}{b} = ab^{-1}\). Oczywiście przez liczbę odwrotną do \(b\) rozumiemy taką liczbę \(b^{-1}\), że \(b \cdot b^{-1} = 1\). Będziemy trzymać się tej definicji także w arytmetyce modulo \(M\): \(b \cdot b^{-1} \equiv 1 \pmod{M}\). Działając w arytmetyce modulo \(M\) wykonanie dzielenia przez dowolną liczbę \(x\) będzie zatem równoważne wykonaniu mnożenia przez \(x^{-1}\). Znalezienie odwrotności jest czasami niemożliwe, na przykład w modulo 9:

  • \(1 \cdot 1 \equiv 1 \pmod{9}\)
  • \(2 \cdot 5 \equiv 1 \pmod{9}\)
  • 3 nie ma odwrotności
  • \(4 \cdot 7 \equiv 1 \pmod{9}\)
  • \(5 \cdot 2 \equiv 1 \pmod{9}\)
  • 6 nie ma odwrotności
  • \(7 \cdot 4 \equiv 1 \pmod{9}\)
  • \(8 \cdot 8 \equiv 1 \pmod{9}\)

Okazuje się, że jeśli \(M\) jest liczbą pierwszą, to dla każdej wartości z przedziału \(1\ldots M-1\) istnieje jej odwrotność w arytmetyce modulo \(M\). Odwrotności można szukać na różne sposoby. My zademonstrujemy w tym celu pewną sztuczkę matematyczną: wiadomo (z tzw. małego twierdzenia Fermata), że \(b^{M-1}\) daje resztę 1 z dzielenia przez \(M\). A zatem można przyjąć po prostu \(b' = b^{M-2}\) i obliczyć tę ostatnią potęgę za pomocą znanego z poprzednich lekcji szybkiego potęgowania.

Warto wspomnieć jeszcze, że istnieje algorytm, oparty na algorytmie Euklidesa, który pozwala szukać odwrotności również wtedy, jeśli \(M\) nie jest liczbą pierwszą – wystarczy, aby odwracana reszta \(b\) nie miała wspólnego dzielnika z \(M\). Zwany jest rozszerzonym algorytmem Euklidesa.

Zadania

Rozkład na czynniki

Suma liczb pierwszych