V matematice je modulární aritmetika výpočtový systém pro celá čísla, s jehož pomocí se "obrátí", když dosáhnou určité hodnoty - modulu (nebo jejich množného čísla). Moderní přístup k tomuto druhu vědy vyvinul Carl Friedrich Gauss ve svém Disquisitiones Arithmeticae publikovaném v roce 1801. Počítačoví odborníci tuto metodu velmi rádi používají, protože je velmi zajímavá a otevírá určité nové možnosti v operacích s čísly.
Essence
Protože počet hodin začíná znovu poté, co dosáhne 12, jedná se o aritmetický modulo 12. Podle níže uvedené definice odpovídá 12 nejen 12, ale také 0, takže čas lze pojmenovat také jako „ 12:00". "0:00". Koneckonců, 12 je totéž jako 0 modulo 12.
Modulární aritmetiku lze zpracovat matematicky zavedením kongruentního vztahu k celým číslům, který je kompatibilní s operacemi s celými číslyčísla: sčítání, odčítání a násobení. Pro kladné celé číslo n se říká, že dvě čísla a a b jsou shodná modulo n, pokud jejich rozdíl a - b je násobkem n (to znamená, pokud existuje celé číslo k takové, že a - b=kn).
Srážky
V teoretické matematice je modulární aritmetika jedním ze základů teorie čísel, která ovlivňuje téměř všechny aspekty jejího studia, a je také široce používána v teorii grup, prstenců, uzlů a abstraktní algebry. V oblasti aplikované matematiky se používá v počítačové algebře, kryptografii, informatice, chemii, výtvarném umění a hudbě.
Cvičení
Velmi praktickou aplikací je výpočet kontrolních součtů v identifikátorech sériového čísla. Například některé běžné knižní standardy používají aritmetické modulo 11 (pokud byly vydány před 1. lednem 2007) nebo modulo 10 (pokud byly vydány před nebo po 1. lednu 2007). Podobně například v mezinárodních číslech bankovních účtů (IBAN). Toto používá aritmetiku modulo 97 k detekci chyb uživatelského vstupu v číslech bankovních účtů.
V chemii je kontrolní číslicí poslední číslice registračního čísla CAS (jedinečné identifikační číslo pro každou chemickou sloučeninu). Vypočítá se tak, že se poslední číslice z prvních dvou částí registračního čísla CAS vynásobí 1, předchozí číslice 2krát, předchozí číslice 3krát atd., sečte se vše a vypočítá se součet modulo 10.
Co je kryptografie? Faktem je, žemá velmi silnou souvislost s diskutovaným tématem. V kryptografii jsou zákony modulární aritmetiky přímo základem systémů s veřejným klíčem, jako je RSA a Diffie-Hellman. Zde poskytuje konečná pole, která jsou základem eliptických křivek. Používá se v různých algoritmech symetrických klíčů, včetně Advanced Encryption Standard (AES), International Data Encryption Algorithm a RC4.
Aplikace
Tato metoda se používá v oblastech, kde potřebujete číst čísla. Vyvinuli ho matematici a používají ho všichni, zejména informatici. To je dobře zdokumentováno v knihách jako Modular Arithmetic for Dummies. Řada odborníků však doporučuje nebrat takovou literaturu vážně.
V informatice se modulární aritmetika často používá v bitových a jiných operacích zahrnujících kruhové datové struktury s pevnou šířkou. Analytici to rádi používají. Operace modulo je implementována v mnoha programovacích jazycích a kalkulačkách. V tomto případě je to jeden příklad takové aplikace. Při programování se také používá modulo porovnání, dělení se zbytkem a další triky.
V hudbě se aritmetický modulo 12 používá při zvažování systému stejného temperamentu dvanácti tónů, ve kterém jsou oktáva a enharmonie ekvivalentní. Jinými slovy, klíče v poměru 1-2 nebo 2-1 jsou ekvivalentní. V hudbě a dalších humanitních oborech hraje aritmetika poměrně významnou roli, ale v učebnicíchinformatici o tom obvykle nepíší.
Metoda redukce devítek
Metoda převodu 9s nabízí rychlou kontrolu ručních desítkových aritmetických výpočtů. Je založen na modulární aritmetice modulo 9 a zejména na rozhodující vlastnosti 10 10 1.
existují další příklady. Aritmetický modulo 7 se používá v algoritmech, které určují den v týdnu pro konkrétní datum. Zejména Zellerova kongruence a algoritmus Doomsday hojně využívají aritmetický modulo 7.
Další aplikace
O modulární aritmetice v kryptografii již bylo řečeno. V této oblasti je prostě nenahraditelná. Obecněji platí, že modulární aritmetika také nachází uplatnění v oborech, jako je právo, ekonomie (jako je teorie her) a dalších oblastech společenských věd. Jinými slovy, kde proporcionální rozdělení a rozdělení zdrojů hraje hlavní roli.
Protože modulární aritmetika má tak širokou škálu použití, je důležité vědět, jak obtížné je vyřešit systém porovnávání. Lineární systém kongruencí lze řešit v polynomiálním čase formou Gaussovy eliminace. Podrobněji to popisuje věta o lineární kongruenci. Existují také algoritmy, jako je Montgomeryho redukce, které umožňují efektivní provádění jednoduchých aritmetických operací. Například násobení a umocňování modulo n pro velká čísla. To je velmi důležité vědět, abyste pochopili cokryptografie. Přeci jen to funguje s podobnými operacemi.
Kongruence
Některé operace, jako je nalezení diskrétního logaritmu nebo kvadratické kongruence, se zdají být stejně složité jako faktorizace celého čísla, a proto jsou výchozím bodem pro kryptografické algoritmy a šifrování. Tyto problémy mohou být středně pokročilé.
Příklady
Následují tři poměrně rychlé funkce C – dvě pro provádění modulárního násobení a jedna pro zvýšení na modulární čísla pro celá čísla bez znaménka až do 63 bitů, bez přechodného přetečení.
Krátce po objevení celých čísel (1, 2, 3, 4, 5…) je zřejmé, že se dělí na dvě skupiny:
- Sudy: dělitelné 2 (0, 2, 4, 6..).
- Liché: nedělitelné 2 (1, 3, 5, 7…).
Proč je toto rozlišení důležité? To je začátek abstrakce. Všímáme si vlastností čísla (např. sudé nebo liché), nikoli pouze samotného čísla ("37").
To nám umožňuje prozkoumat matematiku na hlubší úrovni a najít vztahy mezi typy čísel spíše než mezi konkrétními.
Vlastnosti čísla
Být „trojkou“je jen další vlastností čísla. Možná to není hned tak užitečné jako sudé/liché, ale je to tam. Můžeme vytvořit pravidla jako "třináct x tři žíla=třináct" a podobně. Ale je to šílené. Nemůžeme neustále vytvářet nová slova.
Operace modulo (v mnoha programovacích jazycích zkráceně mod nebo "%") je zbytek, kdyždivize. Například „5 mod 3=2“, což znamená, že 2 je zbytek, když vydělíte 5 3.
Při převodu běžných termínů na matematiku je „sudé číslo“tam, kde je „0 mod 2“, což znamená, že zbytek je 0, když je děleno 2. Liché číslo je „1 mod 2“(má zbytek z 1).
Sudá a lichá čísla
Co je sudé x sudé x liché x liché? No, je to 0 x 0 x 1 x 1=0. Ve skutečnosti můžete vidět, zda se někde vynásobí sudé číslo, kde celý výsledek bude nula.
Trik s modulární matematikou je v tom, že jsme ji již použili k ukládání času – někdy nazývané „hodinová aritmetika“.
Například: 7:00 (am/pm – nezáleží). Kde bude hodinová ručička za 7 hodin?
Modulace
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 je zbytek, když je 14 děleno 12. Rovnice 14 mod 12=2 mod 12 znamená 14 hodin a 2 hodiny. to samé na 12hodinovém taktu. Jsou shodné a jsou označeny trojitým rovnítkem: 14 ≡ 2 mod 12.
Další příklad: je 8:00. Kde bude velká kombinace za 25 hodin?
Místo přidávání 25 k 8 můžete pochopit, že 25 hodin je jen „1 den + 1 hodina“. Odpověď je jednoduchá. Hodiny tedy skončí o 1 hodinu dopředu – v 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Intuitivně jste převedli 25 na 1 a přidali toto do 8.
Použitím hodin jako analogie můžeme zjistit, zdapravidla modulární aritmetiky a fungují.
Sčítání/odčítání
Řekněme, že na našich hodinách vypadají dva časy stejně ("2:00" a "14:00"). Když k oběma přidáme stejných x hodin, co se stane? No, na hodinách se mění za stejnou částku! 2:00 + 5 hodin ≡ 14:00 + 5 hodin – obě zobrazí 7:00.
Proč? Můžeme jednoduše přidat 5 ke 2 zbytkům, které oba mají, a postupují stejným způsobem. Pro všechna kongruentní čísla (2 a 14) má sčítání a odčítání stejný výsledek.
Je těžší zjistit, zda násobení zůstane stejné. Jestliže 14 ≡ 2 (mod 12), můžeme vynásobit obě čísla a získat stejný výsledek? Podívejme se, co se stane, když vynásobíme 3.
No, 2:003 × 6:00. Ale kolik je 14:003?
Pamatujte si, 14=12 + 2. Můžeme tedy říci
143=(12 + 2)3=(123) + (23)
První část (123) lze ignorovat! Přetečení 12 hodin, které nese 14, se prostě několikrát opakuje. Ale koho to zajímá? Přetečení stejně ignorujeme.
Násobení
Při násobení záleží pouze na zbytku, tedy stejné 2 hodiny pro 14:00 a 2:00. Intuitivně takto vidím, že násobení nemění vztah s modulární matematikou (můžete vynásobit obě strany modulárního vztahu a získat stejný výsledek).
Děláme to intuitivně, ale je hezké to pojmenovat. Máte přílet v 15:00. Onse zpožděním 14 hodin. V kolik přistane?
14 ≡ 2 mod 12. Představte si to jako 2 hodiny, takže letadlo přistane v 5 hodin ráno. Řešení je jednoduché: 3 + 2=5 hodin ráno. Je to trochu složitější než jednoduchá operace modulo, ale princip je stejný.
