Dlaczego nie rozłożyć po prostu obu liczb na czynniki?

Bo rozkład jest trudny, a Euklides nie. Rozbicie 123456789 na czynniki pierwsze to realna praca; wzięcie trzech reszt nie. Bezpieczeństwo RSA opiera się dokładnie na tej asymetrii — mnożenie i NWD są tanie, rozkład na czynniki nie.

Co oznacza NWD równe 1?

Liczby są względnie pierwsze — nie mają wspólnego dzielnika większego od 1. Nie oznacza to, że którakolwiek jest pierwsza: 8 i 9 są względnie pierwsze i żadna z nich pierwsza nie jest. Oznacza za to, że ułamek 8/9 jest już nieskracalny.

Kalkulator NWD

Wprowadz liczby

NWD

Przewodnik: największy wspólny dzielnik (NWD)

Czym jest NWD?

Najwiekszy wspolny dzielnik (NWD) to najwieksza liczba calkowita, dzielaca bez reszty dwie lub wiecej innych liczb calkowitych. Na przyklad NWD(48, 18) = 6, poniewaz 6 jest najwieksza liczba, ktora dzieli zarowno 48 jak i 18 bez reszty. NWD jest fundamentalnym pojciem w teorii liczb i kryptografii.

Algorytm Euklidesa

Najstarszym i najbardziej efektywnym sposobem obliczania NWD jest algorytm Euklidesa. Polega on na powtarzajacym sie dzieleniu: NWD(a, b) = NWD(b, a mod b), az b bedzie rowne 0. Dla przykladu: NWD(48, 18) → NWD(18, 12) → NWD(12, 6) → NWD(6, 0) = 6. Ten algorytm jest niezwykle szybki i dziala nawet dla bardzo duzych liczb.

Wlasnosci NWD

NWD(a, b) * NWW(a, b) = a * b (iloczyn NWD i NWW rowna sie iloczynu liczb). Jesli NWD(a, b) = 1, to liczby a i b sa wzglednie pierwsze. NWD jest zawsze mniejszy lub rowny mniejszej z liczb. NWD(0, a) = |a| dla kazdej niezerowej liczby a.

Praktyczne zastosowania

NWD jest uzywany do skracania ulamkow - dzielimy licznik i mianownik przez NWD, by otrzymac ulamek nieskracalny. W kryptografii RSA NWD sluzy do generowania kluczy szyfrujacych. W informatyce, NWD okresla najwiekszy wspolny podzial zasobow pamieci lub procesora. W muzyce, NWD moze okreslic wspolne interwaly dzwiekowe dla rytmow.

Euklides znajduje dzielnik dwóch dziewięciocyfrowych liczb w trzech krokach

Znalezienie tego, co dwie liczby mają wspólnego, wygląda na zadanie wymagające rozkładu na czynniki, a rozkład jest powolny. Algorytm Euklidesa całkowicie go omija: NWD(123456789, 987654321) = 9, osiągnięte w trzech dzieleniach. Dzielenie próbne mniejszej liczby mogłoby wymagać 11 111 sprawdzeń. Algorytm ma ponad dwa tysiące lat i wciąż jest tym, którego używa każdy komputer.

Jak to działa

Znajduje największy wspólny dzielnik dwóch lub więcej liczb algorytmem Euklidesa.
Skraca ułamki do postaci nieskracalnej, co jest tą samą operacją w innym przebraniu.
Podaje liczbę kroków, bo to właśnie szybkość jest tu całą rzeczą.

NWD(a, b) = NWD(b, a mod b),  powtarzane aż b = 0

pozostałe a jest odpowiedzią

postać nieskracalna:  a/b podzielone przez NWD(a, b) w obu częściach
względnie pierwsze oznacza NWD = 1 — zero wspólnych czynników

Przykład z liczbami

Euklides na coraz paskudniejszych danych.

NWD(1071, 462) = 21 w 3 krokach
NWD(123456789, 987654321) = 9 w 3 krokach
NWD(2⁴⁰, 3²⁰) = 1 w 15 krokach
NWD(832040, 514229) = 1 w 28 krokach
ta ostatnia para to kolejne liczby Fibonacciego — najgorszy przypadek, jaki istnieje

Dwie dziewięciocyfrowe liczby rozwiązują się w trzech dzieleniach. Nawet celowo najgorsze dane, czyli para kolejnych liczb Fibonacciego, zajmują 28 kroków. Liczba kroków rośnie z liczbą cyfr, a nie z wielkością liczb, i dlatego algorytm skaluje się do wartości o setkach cyfr.

Jak czytać wynik

Kolejne liczby Fibonacciego to udowodniony najgorszy przypadek i są najgorsze właśnie dlatego, że każde dzielenie usuwa możliwie najmniej. NWD(987, 610) zajmuje 14 kroków, a NWD(75025, 46368) 23 — licznik kroków pełznie w górę, podczas gdy same liczby eksplodują.
Skracanie ułamka to NWD w przebraniu. 84/126 ma wspólny dzielnik 42 i spada do 2/3 w jednym kroku; NWD to dokładnie granica, do której da się uprościć dowolny ułamek, a dzielenie przez cokolwiek mniejszego zostawia robotę niedokończoną.
Największy wspólny dzielnik i najmniejsza wspólna wielokrotność to dwie połowy jednego narzędzia, związane wzorem NWD(a,b) × NWW(a,b) = a × b. Mając jedno, dostajesz drugie kosztem mnożenia i dzielenia.
Algorytm Euklidesa stoi u podstaw współczesnej kryptografii przez swoją postać rozszerzoną, która daje też współczynniki potrzebne do odwrotności modularnych. Generowanie kluczy RSA zależy od niego, co jest długim życiem pośmiertnym procedury spisanej około 300 roku p.n.e.

Częste pytania

Dlaczego nie rozłożyć po prostu obu liczb na czynniki?: Bo rozkład jest trudny, a Euklides nie. Rozbicie 123456789 na czynniki pierwsze to realna praca; wzięcie trzech reszt nie. Bezpieczeństwo RSA opiera się dokładnie na tej asymetrii — mnożenie i NWD są tanie, rozkład na czynniki nie.
Co oznacza NWD równe 1?: Liczby są względnie pierwsze — nie mają wspólnego dzielnika większego od 1. Nie oznacza to, że którakolwiek jest pierwsza: 8 i 9 są względnie pierwsze i żadna z nich pierwsza nie jest. Oznacza za to, że ułamek 8/9 jest już nieskracalny.