Inom matematiken är modulär aritmetik ett beräkningssystem för heltal, med vars hjälp de "vänder" när de når ett visst värde - modulen (eller pluralen av dem). Den moderna inställningen till denna typ av vetenskap utvecklades av Carl Friedrich Gauss i hans Disquisitiones Arithmeticae publicerad 1801. Datavetare är mycket förtjusta i att använda denna metod, eftersom den är mycket intressant och öppnar upp för vissa nya möjligheter i operationer med siffror.
Essence
Eftersom antalet timmar börjar igen efter att det når 12 är det aritmetisk modulo 12. Enligt definitionen nedan motsvarar 12 inte bara 12, utan också 0, så man kan också namnge tiden som kallas " 12:00". "0:00". När allt kommer omkring är 12 detsamma som 0 modulo 12.
Modulär aritmetik kan bearbetas matematiskt genom att introducera en kongruent relation till heltal som är kompatibel med operationer på helt altal: addition, subtraktion och multiplikation. För ett positivt heltal n sägs två tal a och b vara kongruenta modulo n om deras skillnad a - b är en multipel av n (det vill säga om det finns ett heltal k så att a - b=kn).
Avdrag
Inom teoretisk matematik är modulär aritmetik en av grunderna för t alteorin, som påverkar nästan alla aspekter av dess studier, och används också flitigt i teorin om grupper, ringar, knutar och abstrakt algebra. Inom området tillämpad matematik används det inom datoralgebra, kryptografi, datavetenskap, kemi, bildkonst och musik.
Öva
En mycket praktisk tillämpning är beräkningen av kontrollsummor i serienummeridentifierare. Till exempel använder vissa vanliga bokstandarder aritmetisk modulo 11 (om den släpptes före 1 januari 2007) eller modulo 10 (om den släpptes före eller efter 1 januari 2007). På liknande sätt, till exempel i internationella bankkontonummer (IBAN). Detta använder modulo 97 aritmetik för att upptäcka användarinmatningsfel i bankkontonummer.
Inom kemi är den sista siffran i CAS-registreringsnumret (det unika identifieringsnumret för varje kemisk förening) kontrollsiffran. Den beräknas genom att ta den sista siffran i de två första delarna av CAS-registreringsnumret multiplicerad med 1, den föregående siffran 2 gånger, den föregående siffran 3 gånger, etc., lägga ihop allt och beräkna summan modulo 10.
Vad är kryptografi? Faktum är attden har ett mycket starkt samband med ämnet som diskuteras. Inom kryptografi ligger lagarna för modulär aritmetik direkt till grund för system med offentliga nyckel som RSA och Diffie-Hellman. Här ger den de finita fälten som ligger bakom elliptiska kurvor. Används i olika symmetriska nyckelalgoritmer, inklusive Advanced Encryption Standard (AES), International Data Encryption Algorithm och RC4.
Application
Denna metod används i områden där du behöver läsa siffror. Det utvecklades av matematiker, och alla använder det, särskilt datavetare. Detta är väl dokumenterat i böcker som Modular Arithmetic for Dummies. Ett antal experter rekommenderar dock att man inte tar sådan litteratur på allvar.
Inom datavetenskap används modulär aritmetik ofta i bitvisa och andra operationer som involverar cirkulära datastrukturer med fast bredd. Analytiker älskar att använda det. Modulo-operationen är implementerad i många programmeringsspråk och miniräknare. I det här fallet är det ett exempel på en sådan applikation. Modulo-jämförelse, division med en rest och andra knep används också i programmering.
I musik används aritmetisk modulo 12 när man överväger ett system med lika temperament av tolv toner, där oktav och enharmonik är ekvivalenta. Med andra ord är nycklarna i förhållandet 1-2 eller 2-1 likvärdiga. Inom musik och annan humaniora spelar aritmetiken en ganska betydande roll, men i läroböckerdatavetare brukar inte skriva om det.
Metod för att minska nior
Niotalets omvandlingsmetoden erbjuder en snabb kontroll av manuella decimalaritmetiska beräkningar. Den är baserad på modulär aritmetik modulo 9 och i synnerhet på den avgörande egenskapen 10 10 1.
det finns andra exempel. Aritmetisk modulo 7 används i algoritmer som bestämmer veckodagen för ett visst datum. Speciellt Zellers kongruens och Doomsday-algoritmen använder mycket aritmetisk modulo 7.
Andra applikationer
Det har redan sagts om modulär aritmetik i kryptografi. På det här området är hon helt enkelt oersättlig. Mer generellt finner modulära aritmetik även tillämpningar inom discipliner som juridik, ekonomi (som spelteori) och andra områden inom samhällsvetenskapen. Med andra ord, där den proportionella uppdelningen och fördelningen av resurser spelar stor roll.
Eftersom modulär aritmetik har så många olika användningsområden är det viktigt att veta hur svårt det är att lösa ett system av jämförelser. Ett linjärt system av kongruenser kan lösas i polynomtid i form av Gauss eliminering. Detta beskrivs mer i detalj av linjär kongruenssatsen. Algoritmer som Montgomery-reduktion finns också för att tillåta enkla aritmetiska operationer att utföras effektivt. Till exempel multiplikation och exponentieringsmodulo n, för stora tal. Detta är mycket viktigt att veta för att förstå vadkryptografi. När allt kommer omkring fungerar det bara med liknande operationer.
Congruence
Vissa operationer, som att hitta den diskreta logaritmen eller den kvadratiska kongruensen, verkar vara lika komplexa som heltalsfaktorisering och är därför utgångspunkten för kryptografiska algoritmer och kryptering. Dessa problem kan vara NP-mellanliggande.
Exempel
Följande är tre ganska snabba C-funktioner - två för att utföra modulär multiplikation och en för att höja till modulära tal för heltal utan tecken upp till 63 bitar, utan övergående spill.
Kort efter upptäckten av heltal (1, 2, 3, 4, 5…) blir det uppenbart att de är indelade i två grupper:
- Jämnt: delbart med 2 (0, 2, 4, 6..).
- Uda: inte delbart med 2 (1, 3, 5, 7…).
Varför är denna skillnad viktig? Detta är början på abstraktionen. Vi lägger märke till talets egenskaper (t.ex. jämnt eller udda) och inte bara själva talet ("37").
Detta tillåter oss att utforska matematiken på en djupare nivå och hitta samband mellan t altyper snarare än specifika.
Egenskaper för ett nummer
Att vara en "trea" är bara ytterligare en egenskap hos ett nummer. Kanske inte lika direkt användbar som jämn/udda, men den finns där. Vi kan skapa regler som "tretton x tre vener=tretton" och så vidare. Men det är galet. Vi kan inte skapa nya ord hela tiden.
Moduloperationen (förkortad mod eller "%" på många programmeringsspråk) är resten närdivision. Till exempel "5 mod 3=2", vilket betyder att 2 är resten när du dividerar 5 med 3.
När man konverterar vardagliga termer till matematik, är ett "jämnt tal" där det är "0 mod 2", vilket betyder att resten är 0 när det divideras med 2. Ett udda tal är "1 mod 2" (har en rest). av 1).
jämna och udda nummer
Vad är jämn x jämn x udda x udda? Tja, det är 0 x 0 x 1 x 1=0. Du kan faktiskt se om ett jämnt tal multipliceras någonstans, där hela resultatet blir noll.
Knepet med modulär matematik är att vi redan har använt det för att lagra tid - ibland kallat "klockaritmetik".
Till exempel: 7:00 am (am/pm - spelar ingen roll). Var är timvisaren om 7 timmar?
Modulations
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 är resten när 14 är dividerat med 12. Ekvation 14 mod 12=2 mod 12 betyder 14 timmar och 2 timmar. samma sak på en 12-timmars klocka. De är kongruenta, indikerade med ett trippelt likhetstecken: 14 ≡ 2 mod 12.
Ett annat exempel: klockan är 8:00. Var är den stora handen om 25 timmar?
Istället för att lägga till 25 till 8 kan du förstå att 25 timmar bara är "1 dag + 1 timme". Svaret är enkelt. Så klockan slutar 1 timme före - klockan 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Du konverterade intuitivt 25 till 1 och la till detta till 8, Med hjälp av klockan som en analogi kan vi ta reda på omreglerna för modulär aritmetik, och de fungerar.
Addition/Subtraction
Låt oss säga att två gånger ser likadana ut på vår klocka ("2:00" och "14:00"). Om vi lägger till samma x timmar till båda, vad händer? Tja, de byter för samma summa på klockan! 2:00 + 5 timmar ≡ 14:00 + 5 timmar – båda visas 7:00.
Varför? Vi kan helt enkelt lägga till 5 till de 2 resterna som båda har och de avancerar på samma sätt. För alla kongruenta tal (2 och 14) ger addition och subtraktion samma resultat.
Det är svårare att veta om multiplikationen förblir densamma. Om 14 ≡ 2 (mod 12), kan vi multiplicera båda talen och få samma resultat? Låt oss se vad som händer när vi multiplicerar med 3.
Tja, 2:003 × 6:00. Men vad är 14:003?
Kom ihåg, 14=12 + 2. Så vi kan säga
143=(12 + 2)3=(123) + (23)
Den första delen (123) kan ignoreras! Överflödet på 12 timmar som bär 14 upprepar sig helt enkelt flera gånger. Men vem bryr sig? Vi ignorerar brädden ändå.
Multiplication
När du multiplicerar är det bara resten som spelar roll, det vill säga samma 2 timmar för 14:00 och 2:00. Intuitivt är det så här jag ser att multiplikation inte förändrar sambandet med modulär matematik (du kan multiplicera båda sidor av ett modulärt samband och få samma resultat).
Vi gör det intuitivt, men det är trevligt att ge det ett namn. Du har ett flyg som anländer kl. 15.00. hanförsenad med 14 timmar. Vilken tid landar den?
14 ≡ 2 mod 12. Så tänk på att det är klockan 2, så planet landar klockan 5 på morgonen. Lösningen är enkel: 3 + 2=5 på morgonen. Det här är lite mer komplicerat än den enkla modulo-operationen, men principen är densamma.
