In de wiskunde is modulaire rekenkunde een rekensysteem voor gehele getallen, met behulp waarvan ze "omdraaien" wanneer ze een bepaalde waarde bereiken - de module (of het meervoud ervan). De moderne benadering van dit soort wetenschap werd ontwikkeld door Carl Friedrich Gauss in zijn Disquisitiones Arithmeticae, gepubliceerd in 1801. Computerwetenschappers zijn dol op het gebruik van deze methode, omdat het erg interessant is en bepaalde nieuwe mogelijkheden opent in bewerkingen met getallen.
Essentie
Omdat het aantal uren opnieuw begint nadat het 12 heeft bereikt, is het rekenkundig modulo 12. Volgens de onderstaande definitie komt 12 niet alleen overeen met 12, maar ook met 0, dus men kan de tijd ook noemen " 12.00 uur". "0:00". 12 is immers hetzelfde als 0 modulo 12.
Modulaire rekenkunde kan wiskundig worden verwerkt door een congruente relatie met gehele getallen te introduceren die compatibel is met bewerkingen op gehele getallengetallen: optellen, aftrekken en vermenigvuldigen. Voor een positief geheel getal n zijn twee getallen a en b congruent modulo n als hun verschil a - b een veelvoud van n is (dat wil zeggen, als er een geheel getal k bestaat zodat a - b=kn).
Afhoudingen
In de theoretische wiskunde is modulaire rekenkunde een van de fundamenten van de get altheorie, die van invloed is op bijna alle aspecten van de studie, en wordt ook veel gebruikt in de theorie van groepen, ringen, knopen en abstracte algebra. Op het gebied van toegepaste wiskunde wordt het gebruikt in computeralgebra, cryptografie, informatica, scheikunde, beeldende kunst en muziek.
Oefen
Een zeer praktische toepassing is de berekening van controlesommen in serienummer-ID's. Sommige gangbare boekstandaarden gebruiken bijvoorbeeld rekenkunde modulo 11 (indien vrijgegeven vóór 1 januari 2007) of modulo 10 (indien vrijgegeven vóór of na 1 januari 2007). Zo ook bijvoorbeeld in International Bank Account Numbers (IBAN's). Dit maakt gebruik van modulo 97 rekenkunde om gebruikersinvoerfouten in bankrekeningnummers te detecteren.
In de chemie is het laatste cijfer van het CAS-registratienummer (het unieke identificatienummer voor elke chemische verbinding) het controlecijfer. Het wordt berekend door het laatste cijfer van de eerste twee delen van het CAS-registratienummer te vermenigvuldigen met 1, het vorige cijfer 2 keer, het vorige cijfer 3 keer, enz., alles bij elkaar op te tellen en de som te berekenen modulo 10.
Wat is cryptografie? Het feit is dathet heeft een zeer sterke band met het onderwerp dat wordt besproken. In cryptografie liggen de wetten van modulaire rekenkunde direct ten grondslag aan openbare-sleutelsystemen zoals RSA en Diffie-Hellman. Hier biedt het de eindige velden die ten grondslag liggen aan elliptische krommen. Gebruikt in verschillende algoritmen voor symmetrische sleutels, waaronder Advanced Encryption Standard (AES), International Data Encryption Algorithm en RC4.
Toepassing
Deze methode wordt gebruikt in gebieden waar je cijfers moet lezen. Het is ontwikkeld door wiskundigen en iedereen gebruikt het, vooral computerwetenschappers. Dit is goed gedocumenteerd in boeken als Modular Arithmetic for Dummies. Een aantal experts raadt echter aan om dergelijke literatuur niet serieus te nemen.
In de informatica wordt modulaire rekenkunde vaak gebruikt in bitsgewijze en andere bewerkingen met circulaire datastructuren met vaste breedte. Analisten maken er graag gebruik van. De modulo-bewerking is geïmplementeerd in veel programmeertalen en rekenmachines. In dit geval is het een voorbeeld van een dergelijke toepassing. Modulo-vergelijking, delen met een rest en andere trucs worden ook gebruikt bij het programmeren.
In de muziek wordt rekenkundige modulo 12 gebruikt bij het overwegen van een systeem van gelijkzwevende stemming van twaalf tonen, waarin het octaaf en de enharmonische equivalent zijn. Met andere woorden, de sleutels in de verhouding 1-2 of 2-1 zijn equivalent. In muziek en andere geesteswetenschappen speelt rekenen een vrij belangrijke rol, maar in schoolboekencomputerwetenschappers schrijven er meestal niet over.
Methode om negens te verminderen
De 9s-conversiemethode biedt een snelle controle van handmatige decimale rekenkundige berekeningen. Het is gebaseerd op modulaire rekenkunde modulo 9 en in het bijzonder op de beslissende eigenschap 10 10 1.
er zijn andere voorbeelden. Rekenkundige modulo 7 wordt gebruikt in algoritmen die de dag van de week voor een bepaalde datum bepalen. In het bijzonder maken de congruentie van Zeller en het Doomsday-algoritme veel gebruik van rekenkundige modulo 7.
Andere toepassingen
Er is al gezegd over modulaire rekenkunde in cryptografie. Op dit gebied is ze gewoon onvervangbaar. Meer in het algemeen vindt modulaire rekenkunde ook toepassingen in disciplines zoals recht, economie (zoals speltheorie) en andere gebieden van de sociale wetenschappen. Met andere woorden, waar de proportionele verdeling en verdeling van middelen een grote rol speelt.
Omdat modulaire rekenkunde zo'n breed scala aan toepassingen heeft, is het belangrijk om te weten hoe moeilijk het is om een systeem van vergelijkingen op te lossen. Een lineair systeem van congruenties kan worden opgelost in polynomiale tijd in de vorm van Gauss-eliminatie. Dit wordt in meer detail beschreven door de lineaire congruentiestelling. Er bestaan ook algoritmen zoals Montgomery-reductie om eenvoudige rekenkundige bewerkingen efficiënt uit te voeren. Bijvoorbeeld vermenigvuldiging en machtsverheffing modulo n, voor grote getallen. Dit is erg belangrijk om te weten om te begrijpen wat:cryptografie. Het werkt tenslotte gewoon met vergelijkbare bewerkingen.
Congruentie
Sommige bewerkingen, zoals het vinden van de discrete logaritme of de kwadratische congruentie, lijken net zo complex als factorisatie van gehele getallen en vormen dus het startpunt voor cryptografische algoritmen en encryptie. Deze problemen kunnen NP-intermediair zijn.
Voorbeelden
Hier volgen drie redelijk snelle C-functies - twee voor het uitvoeren van modulaire vermenigvuldiging en één voor het verhogen naar modulaire getallen voor niet-ondertekende gehele getallen tot 63 bits, zonder tijdelijke overloop.
Kort na de ontdekking van gehele getallen (1, 2, 3, 4, 5…) wordt het duidelijk dat ze in twee groepen zijn verdeeld:
- Even: deelbaar door 2 (0, 2, 4, 6..).
- Oneven: niet deelbaar door 2 (1, 3, 5, 7…).
Waarom is dit onderscheid belangrijk? Dit is het begin van abstractie. We zien de eigenschappen van het getal (bijvoorbeeld even of oneven) en niet alleen het getal zelf ("37").
Hierdoor kunnen we de wiskunde op een dieper niveau onderzoeken en relaties tussen nummertypen vinden in plaats van specifieke.
Eigenschappen van een getal
Een "drie" zijn is gewoon een andere eigenschap van een getal. Misschien niet zo direct bruikbaar als even/oneven, maar het is er wel. We kunnen regels maken zoals "dertien x drie ader=dertien" enzovoort. Maar het is gek. We kunnen niet altijd nieuwe woorden maken.
De modulo-bewerking (afgekort mod of "%" in veel programmeertalen) is de rest wanneerdivisie. Bijvoorbeeld "5 mod 3=2", wat betekent dat 2 de rest is als je 5 deelt door 3.
Bij het converteren van alledaagse termen naar wiskunde, is een "even getal" waar het "0 mod 2" is, wat betekent dat de rest 0 is wanneer gedeeld door 2. Een oneven getal is "1 mod 2" (heeft een rest van 1).
Even en oneven nummers
Wat is even x even x oneven x oneven? Nou, het is 0 x 0 x 1 x 1=0. Eigenlijk kun je zien of een even getal ergens wordt vermenigvuldigd, waar het hele resultaat nul zal zijn.
De truc met modulaire wiskunde is dat we het al hebben gebruikt om tijd op te slaan - ook wel "klokrekenkunde" genoemd.
Bijvoorbeeld: 7:00 uur (am/pm - maakt niet uit). Waar staat de uurwijzer over 7 uur?
Modulaties
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 is de rest wanneer 14 wordt gedeeld door 12. Vergelijking 14 mod 12=2 mod 12 betekent 14 uur en 2 uur kijk hetzelfde op een 12-uurs klok. Ze zijn congruent, aangegeven door een drievoudig gelijkteken: 14 ≡ 2 mod 12.
Nog een voorbeeld: het is 8:00 uur. Waar zal de grote hand zijn over 25 uur?
In plaats van 25 bij 8 op te tellen, kun je begrijpen dat 25 uur gewoon "1 dag + 1 uur" is. Het antwoord is simpel. De klok eindigt dus 1 uur vooruit - om 9:00 uur.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Je hebt intuïtief 25 omgezet in 1 en dit toegevoegd tot 8.
Door de klok als analogie te gebruiken, kunnen we erachter komen of dede regels van modulaire rekenkunde, en ze werken.
Optellen/Aftrekken
Laten we zeggen dat twee tijden er hetzelfde uitzien op onze klok ("2:00" en "14:00"). Wat gebeurt er als we bij beide dezelfde x uren optellen? Nou, ze veranderen voor hetzelfde bedrag op de klok! 2:00 + 5 uur ≡ 14:00 + 5 uur - beide tonen 7:00.
Waarom? We kunnen eenvoudig 5 toevoegen aan de 2 resten die beide hebben en ze gaan op dezelfde manier verder. Voor alle congruente getallen (2 en 14) hebben optellen en aftrekken hetzelfde resultaat.
Het is moeilijker om te weten of de vermenigvuldiging hetzelfde blijft. Als 14 ≡ 2 (mod 12), kunnen we beide getallen vermenigvuldigen en hetzelfde resultaat krijgen? Laten we eens kijken wat er gebeurt als we vermenigvuldigen met 3.
Nou, 2:003 × 6:00. Maar wat is 14:003?
Onthoud, 14=12 + 2. Dus we kunnen
zeggen
143=(12 + 2)3=(123) + (23)
Het eerste deel (123) kan worden genegeerd! De overloop van 12 uur die 14 draagt, herha alt zich gewoon meerdere keren. Maar wie maakt het uit? We negeren de overloop toch.
Vermenigvuldigen
Bij vermenigvuldiging is alleen de rest van belang, dat wil zeggen dezelfde 2 uur voor 14:00 en 2:00. Intuïtief zie ik dat vermenigvuldiging de relatie niet verandert met modulaire wiskunde (je kunt beide zijden van een modulaire relatie vermenigvuldigen en hetzelfde resultaat krijgen).
We doen het intuïtief, maar het is leuk om het een naam te geven. Je hebt een vlucht die om 15.00 uur aankomt. Hij14 uur vertraagd. Hoe laat zal het landen?
14 ≡ 2 mod 12. Dus beschouw het als 2 uur, dus het vliegtuig zal om 5 uur 's ochtends landen. De oplossing is simpel: 3 + 2=5 uur. Dit is iets ingewikkelder dan de eenvoudige modulo-bewerking, maar het principe is hetzelfde.
