W matematyce arytmetyka modularna to system obliczania liczb całkowitych, za pomocą którego „odwracają się”, gdy osiągną określoną wartość - moduł (lub ich liczbę mnogą). Nowoczesne podejście do tego rodzaju nauki rozwinął Carl Friedrich Gauss w opublikowanych w 1801 roku Disquisitiones Arithmeticae. Informatycy bardzo lubią tę metodę, ponieważ jest bardzo ciekawa i otwiera pewne nowe możliwości w operacjach na liczbach.
Esencja
Ponieważ liczba godzin zaczyna się ponownie po osiągnięciu 12, jest to arytmetyczne modulo 12. Zgodnie z poniższą definicją, 12 odpowiada nie tylko 12, ale także 0, więc można również nazwać czas o nazwie 12:00”. „0:00”. W końcu 12 to to samo co 0 modulo 12.
Arytmetyka modułowa może być przetwarzana matematycznie przez wprowadzenie przystającej relacji do liczb całkowitych, która jest zgodna z operacjami na liczbach całkowitychliczby: dodawanie, odejmowanie i mnożenie. Dla dodatniej liczby całkowitej n, dwie liczby a i b są przystające modulo n, jeśli ich różnica a - b jest wielokrotnością n (to znaczy, jeśli istnieje liczba całkowita k taka, że a - b=kn).
Odliczenia
W matematyce teoretycznej arytmetyka modularna jest jedną z podstaw teorii liczb, wpływającą na prawie wszystkie aspekty jej badań, a także jest szeroko stosowana w teorii grup, pierścieni, węzłów i algebrze abstrakcyjnej. W dziedzinie matematyki stosowanej jest używany w algebrze komputerowej, kryptografii, informatyce, chemii, sztukach wizualnych i muzyce.
Praktyka
Bardzo praktycznym zastosowaniem jest obliczanie sum kontrolnych w identyfikatorach numerów seryjnych. Na przykład, niektóre popularne standardy książkowe używają arytmetyki modulo 11 (jeśli została wydana przed 1 stycznia 2007) lub modulo 10 (jeśli została wydana przed lub po 1 stycznia 2007). Podobnie na przykład w przypadku międzynarodowych numerów kont bankowych (IBAN). Wykorzystuje arytmetykę modulo 97 do wykrywania błędów wprowadzanych przez użytkownika w numerach kont bankowych.
W chemii ostatnia cyfra numeru rejestracyjnego CAS (unikalny numer identyfikacyjny dla każdego związku chemicznego) jest cyfrą kontrolną. Oblicza się ją, biorąc ostatnią cyfrę dwóch pierwszych części numeru rejestracyjnego CAS pomnożoną przez 1, poprzednią cyfrę 2 razy, poprzednią cyfrę 3 razy itd., zsumować to i obliczyć sumę modulo 10.
Co to jest kryptografia? Fakt jest takima to bardzo silny związek z omawianym tematem. W kryptografii prawa arytmetyki modularnej bezpośrednio leżą u podstaw systemów klucza publicznego, takich jak RSA i Diffie-Hellman. Tutaj dostarcza skończonych pól, które leżą u podstaw krzywych eliptycznych. Używany w różnych algorytmach klucza symetrycznego, w tym Advanced Encryption Standard (AES), International Data Encryption Algorithm i RC4.
Aplikacja
Ta metoda jest używana w obszarach, w których musisz czytać liczby. Został opracowany przez matematyków i wszyscy go używają, zwłaszcza informatycy. Jest to dobrze udokumentowane w książkach takich jak Modular Arithmetic for Dummies. Jednak wielu ekspertów zaleca, aby nie traktować takiej literatury poważnie.
W informatyce arytmetyka modularna jest często używana w operacjach bitowych i innych operacjach związanych z kołowymi strukturami danych o stałej szerokości. Analitycy uwielbiają go używać. Operacja modulo jest zaimplementowana w wielu językach programowania i kalkulatorach. W tym przypadku jest to jeden z przykładów takiej aplikacji. Porównanie modulo, dzielenie z resztą i inne sztuczki są również używane w programowaniu.
W muzyce arytmetyka modulo 12 jest używana przy rozważaniu systemu o jednakowym temperamencie dwunastu tonów, w którym oktawa i enharmonia są równoważne. Innymi słowy, klucze w stosunku 1-2 lub 2-1 są równoważne. W muzyce i innych naukach humanistycznych arytmetyka odgrywa dość znaczącą rolę, ale w podręcznikachinformatycy zwykle o tym nie piszą.
Metoda redukcji dziewiątek
Metoda konwersji 9s umożliwia szybkie sprawdzenie ręcznych obliczeń arytmetycznych dziesiętnych. Opiera się na arytmetyce modularnej modulo 9, a w szczególności na właściwości decyzyjnej 10 10 1.
są inne przykłady. Arytmetyka modulo 7 jest wykorzystywana w algorytmach wyznaczających dzień tygodnia dla określonej daty. W szczególności kongruencja Zellera i algorytm Doomsday intensywnie wykorzystują arytmetykę modulo 7.
Inne aplikacje
Już powiedziano o arytmetyce modularnej w kryptografii. W tej dziedzinie jest po prostu niezastąpiona. Mówiąc bardziej ogólnie, arytmetyka modularna znajduje również zastosowanie w takich dyscyplinach, jak prawo, ekonomia (np. teoria gier) i innych dziedzinach nauk społecznych. Innymi słowy, gdzie proporcjonalny podział i dystrybucja zasobów odgrywa główną rolę.
Ponieważ arytmetyka modularna ma tak szeroki zakres zastosowań, ważne jest, aby wiedzieć, jak trudno jest rozwiązać system porównań. Liniowy układ kongruencji można rozwiązać w czasie wielomianowym w postaci eliminacji Gaussa. Opisuje to bardziej szczegółowo twierdzenie o liniowej kongruencji. Istnieją również algorytmy, takie jak redukcja Montgomery'ego, które umożliwiają wydajne wykonywanie prostych operacji arytmetycznych. Na przykład mnożenie i potęgowanie modulo n dla dużych liczb. Jest to bardzo ważne, aby wiedzieć, aby zrozumieć, cokryptografia. W końcu działa po prostu z podobnymi operacjami.
Kongruencja
Niektóre operacje, takie jak znajdowanie logarytmu dyskretnego lub kongruencji kwadratowej, wydają się być tak złożone, jak faktoryzacja liczb całkowitych, a zatem są punktem wyjścia dla algorytmów kryptograficznych i szyfrowania. Te problemy mogą być NP-pośrednie.
Przykłady
Poniżej znajdują się trzy dość szybkie funkcje C - dwie do wykonywania mnożenia modularnego i jedna do podnoszenia do liczb modularnych dla liczb całkowitych bez znaku do 63 bitów, bez przejściowego przepełnienia.
Krótko po odkryciu liczb całkowitych (1, 2, 3, 4, 5…) okazuje się, że są one podzielone na dwie grupy:
- Nawet: podzielne przez 2 (0, 2, 4, 6..).
- Nieparzyste: niepodzielne przez 2 (1, 3, 5, 7…).
Dlaczego to rozróżnienie jest ważne? To początek abstrakcji. Zauważamy właściwości liczby (np. parzystą lub nieparzystą), a nie tylko samą liczbę ("37").
Pozwala nam to zbadać matematykę na głębszym poziomie i znaleźć relacje między typami liczb, a nie konkretnymi.
Właściwości numeru
Bycie „trójką” to po prostu kolejna właściwość liczby. Może nie tak od razu przydatne jak parzyste/nieparzyste, ale jest. Możemy tworzyć reguły, takie jak „trzynaście x trzy żyły=trzynaście” i tak dalej. Ale to szaleństwo. Nie możemy cały czas tworzyć nowych słów.
Operacja modulo (w skrócie mod lub "%" w wielu językach programowania) to reszta, gdydział. Na przykład „5 mod 3=2”, co oznacza, że 2 to reszta z dzielenia 5 przez 3.
Podczas konwersji codziennych terminów na matematykę, „liczba parzysta” to „0 mod 2”, co oznacza, że reszta to 0 po podzieleniu przez 2. Nieparzysta liczba to „1 mod 2” (ma resztę z 1).
Liczby parzyste i nieparzyste
Co to jest parzyste x parzyste x nieparzyste x nieparzyste? Cóż, to jest 0 x 0 x 1 x 1=0. Właściwie możesz zobaczyć, czy liczba parzysta jest pomnożona w dowolnym miejscu, gdzie cały wynik będzie równy zero.
Sztuczka z matematyką modułową polega na tym, że używaliśmy jej już do przechowywania czasu - czasami nazywa się to "arytmetyka zegarowa".
Na przykład: 7:00 (am/pm - nie ma znaczenia). Gdzie będzie wskazówka godzinowa za 7 godzin?
Modulacje
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 to reszta z dzielenia 14 przez 12. Równanie 14 mod 12=2 mod 12 oznacza 14 godzin i 2 godziny patrz to samo na 12-godzinnym zegarze. Są przystające, oznaczone potrójnym znakiem równości: 14 ≡ 2 mod 12.
Inny przykład: jest 8:00. Gdzie będzie wielka ręka za 25 godzin?
Zamiast dodawać 25 do 8, możesz zrozumieć, że 25 godzin to po prostu „1 dzień + 1 godzina”. Odpowiedź jest prosta. Tak więc zegar skończy się 1 godzinę wcześniej - o 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Intuicyjnie przekonwertowałeś 25 na 1 i dodałeś to do 8.
Używając analogii zegara, możemy dowiedzieć się, czyzasady arytmetyki modularnej i działają.
Dodawanie/odejmowanie
Powiedzmy, że dwa razy wyglądają tak samo na naszym zegarze ("2:00" i "14:00"). Jeśli do obu dodamy te same x godzin, co się stanie? Cóż, zmieniają się na tę samą kwotę na zegarze! 2:00 + 5 godzin ≡ 14:00 + 5 godzin - oba pokażą 7:00.
Dlaczego? Możemy po prostu dodać 5 do 2 reszt, które obaj mają i postępują w ten sam sposób. Dla wszystkich liczb przystających (2 i 14) dodawanie i odejmowanie dają ten sam wynik.
Trudniej jest stwierdzić, czy mnożenie pozostaje takie samo. Jeśli 14 ≡ 2 (mod 12), czy możemy pomnożyć obie liczby i otrzymać ten sam wynik? Zobaczmy, co się stanie, gdy pomnożymy przez 3.
Cóż, 2:003 × 6:00. Ale co to jest 14:003?
Pamiętaj, 14=12 + 2. Możemy więc powiedzieć
143=(12 + 2)3=(123) + (23)
Pierwszą część (123) można zignorować! Przepełnienie 12 godzin, które niesie 14, po prostu powtarza się kilka razy. Ale kogo to obchodzi? I tak ignorujemy przepełnienie.
Mnożenie
Podczas mnożenia liczy się tylko reszta, czyli te same 2 godziny o 14:00 i 2:00. Intuicyjnie, tak widzę mnożenie nie zmieniające relacji z matematyką modularną (możesz pomnożyć obie strony relacji modularnej i uzyskać ten sam wynik).
Robimy to intuicyjnie, ale fajnie jest nadać temu nazwę. Masz samolot przylatujący o 15:00. Onopóźnione o 14 godzin. O której godzinie wyląduje?
14 ≡ 2 mod 12. Pomyśl o tym jako o godzinie drugiej, więc samolot wyląduje o godzinie piątej rano. Rozwiązanie jest proste: 3 + 2=5 rano. Jest to trochę bardziej skomplikowane niż prosta operacja modulo, ale zasada jest taka sama.
