Jak komputery mogą obliczyć matematykę wykładniczą bez błędów przepełnienia?

Studiując niektóre metody szyfrowania / deszyfrowania RSA, znalazłem ten artykuł: Przykład algorytmu RSA

Wymaga to dekrpytacji tej wiadomości

Całkowity wynik jest tak duży, jak na maszynę 64-bitową / 32-bitową, nie sądzę, aby mogła utrzymać tak dużą wartość w jednym rejestrze. Jak komputer robi to bez przepełnienia?

To pytanie było pytaniem superużytkownika tygodnia .
Przeczytać wpis w blogu więcej szczegółów lub przyczynić się do bloga siebie

Ponieważ operacja na module całkowitym jest homomorfizmem pierścieniowym ( Wikipedia ) od ℤ -> ℤ / nℤ,

(X * Y) mod N = (X mod N) * (Y mod N) mod N

Możesz to zweryfikować samodzielnie za pomocą prostej algebry. (Zauważ, że finał modpo prawej stronie pojawia się ze względu na definicję mnożenia w pierścieniu modułowym.)

Komputery używają tej sztuczki do obliczania wykładniczych w pierścieniach modułowych bez konieczności obliczania dużej liczby cyfr.

               / 1 I = 0,
               |
(X ^ I) mod N = <(X * (X ^ (I-1) mod N)) mod NI nieparzysty,
               |
               \ (X ^ (I / 2) mod N) ^ 2 mod NI parzysty i I / = 0.

W formie algorytmicznej

-- compute X^I mod N
function expmod(X, I, N)
    if I is zero
        return 1
    elif I is odd
        return (expmod(X, I-1, N) * X) mod N
    else
        Y <- expmod(X, I/2, N)
        return (Y*Y) mod N
    end if
end function

Możesz użyć tego do obliczeń (855^2753) mod 3233tylko z rejestrami 16-bitowymi, jeśli chcesz.

Jednak wartości X i N w RSA są znacznie większe, zbyt duże, aby zmieścić się w rejestrze. Moduł ma zazwyczaj 1024-4096 bitów! Możesz więc poprosić komputer o pomnożenie „na długą” drogę, w ten sam sposób, w jaki wykonujemy pomnożenie ręcznie. Tylko zamiast używać cyfr 0-9, komputer użyje słowa „0-2” ¹⁶ -1 lub coś podobnego. (Używanie tylko 16 bitów oznacza, że ​​możemy pomnożyć dwie 16-bitowe liczby i uzyskać pełny wynik 32-bitowy bez uciekania się do języka asemblera. W języku asemblera zazwyczaj bardzo łatwo jest uzyskać pełny wynik 64-bitowy lub w przypadku komputera 64-bitowego , pełny wynik 128-bitowy).

-- Multiply two bigints by each other
function mul(uint16 X[N], uint16 Y[N]):
    Z <- new array uint16[N*2]
    for I in 1..N
        -- C is the "carry"
        C <- 0
        -- Add Y[1..N] * X[I] to Z
        for J in 1..N
            T <- X[I] * Y[J] + C + Z[I + J - 1]
            Z[I + J - 1] <- T & 0xffff
            C <- T >> 16
        end
        -- Keep adding the "carry"
        for J in (I+N)..(N*2)
            T <- C + Z[J]
            Z[J] <- T & 0xffff
            C <- T >> 16
        end
    end
    return Z
end
-- footnote: I wrote this off the top of my head
-- so, who knows what kind of errors it might have

To pomnoży X przez Y w czasie w przybliżeniu równym liczbie słów w X pomnożonej przez liczbę słów w Y. Nazywa się to czasem O (N ² ). Jeśli spojrzysz na powyższy algorytm i go rozdzielisz, będzie to to samo „długie mnożenie”, którego uczą w szkole. Nie masz zapamiętanych tabel czasów do 10 cyfr, ale nadal możesz pomnożyć 1 926 348 x 8 192 004, jeśli usiądziesz i wypracujesz.

Długie mnożenie:

    1,234
  x 5,678
---------
    9,872
   86,38
  740,4
6,170
---------
7,006,652

W rzeczywistości istnieje kilka szybszych algorytmów do mnożenia ( Wikipedia ), takich jak szybka metoda Fouriera Strassena, a także niektóre prostsze metody, które dodają i odejmują, ale mniej mnożą, a więc ogólnie szybciej. Biblioteki numeryczne, takie jak GMP, są w stanie wybierać różne algorytmy na podstawie tego, jak duże są liczby: transformata Fouriera jest najszybsza tylko dla największych liczb, mniejsze liczby używają prostszych algorytmów.

Prosta odpowiedź brzmi: nie mogą, nie sami. Rzeczywiście, jeśli przyjmiesz koncepcję maszyny x-bitowej, wówczas istnieje ograniczona liczba liczb, które mogą być reprezentowane przez ograniczoną liczbę bitów, podobnie jak istnieje ograniczona liczba liczb, które mogą być reprezentowane przez 2 cyfry w system dziesiętny.

To powiedziawszy, komputerowa reprezentacja bardzo dużych liczb jest dużym elementem w dziedzinie kryptografii. Istnieje wiele sposobów przedstawiania bardzo dużych liczb w komputerze, z których każda jest tak zróżnicowana jak następna.

Każda z tych metod ma inne zalety i wady i chociaż nie wymienię tutaj wszystkich metod, przedstawię tylko jedną z nich.

Załóżmy, że liczba całkowita może przechowywać tylko wartości od 0 do 99. Jak można reprezentować liczbę 100? Na początku może się to wydawać niemożliwe, ale dzieje się tak, ponieważ rozważamy tylko jedną zmienną. Gdybym miał liczbą całkowitą o nazwie unitsi jeden o nazwie hundreds, mogę łatwo reprezentować 100: hundreds = 1; units = 0;. Mógłbym łatwo reprezentować większą liczbę, jak 9223: hundreds = 92; units = 23.

Chociaż jest to prosta metoda, można argumentować, że jest bardzo nieefektywna. Podobnie jak większość algorytmów, które przekraczają granice tego, co potrafi komputer, zwykle jest to przeciąganie liny między mocą (reprezentują duże liczby) a wydajnością (szybkie pobieranie / przechowywanie). Jak powiedziałem wcześniej, istnieje wiele sposobów przedstawiania dużej liczby w komputerach; po prostu znajdź metodę i eksperymentuj z nią!

Mam nadzieję, że to odpowiedziało na twoje pytanie!

Dalsza lektura:Ten artykuł i ten mogą się przydać po więcej informacji.

Sposób, w jaki można to zrobić (istnieją znacznie szybsze sposoby polegające na powtarzaniu kwadratu itp.), Polega na pomnożeniu, a po każdym pomnożeniu moduł. Dopóki moduł podniesiony do kwadratu jest mniejszy niż 2 ^ 32 (lub 2 ^ 64), nigdy nie będzie to miało przepełnienia.

Tak samo możesz.

Zgaduję, że nie wiesz od razu, czym jest 342 * 189. Ale znasz następujące fakty:

9 * 2 = 18
9 * 4 = 36
9 * 3 = 27
8 * 2 = 16
8 * 4 = 32
8 * 3 = 24
1 * 2 = 2
1 * 4 = 4
1 * 3 = 3

18 + 360 + 2700 + 160 + 3200 + 24000 + 200 + 4000 + 30000 = 64638

Znając te proste fakty i opanowawszy technikę manipulowania nimi, możesz wykonywać arytmetykę, której inaczej byś nie mógł.

Z tego samego powodu komputer, który nie jest w stanie poradzić sobie z więcej niż 64 bitami matematyki na raz, może z łatwością podzielić większe problemy na mniejsze części, wykonać te mniejsze części i złożyć je z powrotem, tworząc odpowiedź na większe, poprzednio problem nieodwracalny.

Jeśli chodzi o dodawanie i odejmowanie, wiele procesorów ma „bit przenoszenia”, który jest ustawiany, jeśli operacja arytmetyczna się przepełniła. Jeśli więc wynik będzie wymagał przechowywania 8 bajtów, a procesor ma 32 bity (co odpowiada 4 bajtom 8-bitowym), może wykonać dwie operacje dodawania, najpierw na „niskim słowie”, a następnie na „wysokim słowie” z bitem przenoszącym dbającym o przelew. Konieczne, aby najpierw wyczyścić bit przenoszenia. Jest to jeden z powodów, dla których wyższe bitowe procesory zwiększają wydajność, ponieważ nie trzeba tego robić zbyt wiele.

Oczywiście wynika to z mojego ograniczonego doświadczenia w asemblerze z 8-bitowymi procesorami. Nie wiem, jak bit przeniesienia działa z nowoczesnymi procesorami z instrukcjami mnożenia i dzielenia. Procesory RISC inne niż Intel mogą również zachowywać się inaczej.

Nie wiem zbyt wiele o matematyce zmiennoprzecinkowej, ale w zasadzie bajty reprezentują stałą liczbę miejsc, ale nie konkretne miejsca. Dlatego nazywa się to „zmiennoprzecinkowym” punktem. Na przykład liczba 34459234 zajmowałaby mniej więcej tyle samo miejsca w pamięci co 3,4459234 lub 3,4459234E + 20 (to jest 3,4459234 x 10 ^ 20).