I matematik er modulær aritmetik et regnesystem for heltal, ved hjælp af hvilket de "vender", når de når en bestemt værdi - modulet (eller flertallet af dem). Den moderne tilgang til denne form for videnskab blev udviklet af Carl Friedrich Gauss i hans Disquisitiones Arithmeticae offentliggjort i 1801. Dataloger er meget glade for at bruge denne metode, da den er meget interessant og åbner op for visse nye muligheder i operationer med tal.
Essence
Fordi antallet af timer starter igen efter det når 12, er det aritmetisk modulo 12. Ifølge definitionen nedenfor svarer 12 ikke kun til 12, men også til 0, så man kan også navngive tiden kaldet " 12:00". "0:00". Når alt kommer til alt er 12 det samme som 0 modulo 12.
Modulær aritmetik kan behandles matematisk ved at indføre en kongruent relation til heltal, der er kompatibel med operationer på helt altal: addition, subtraktion og multiplikation. For et positivt heltal n siges to tal a og b at være kongruente modulo n, hvis deres forskel a - b er et multiplum af n (det vil sige, hvis der findes et heltal k, således at a - b=kn).
Fradrag
I teoretisk matematik er modulær aritmetik et af grundlaget for t alteori, der påvirker næsten alle aspekter af dens undersøgelse, og er også meget brugt i teorien om grupper, ringe, knob og abstrakt algebra. Inden for anvendt matematik bruges det i computeralgebra, kryptografi, datalogi, kemi, billedkunst og musik.
Øv
En meget praktisk anvendelse er beregningen af kontrolsummer i serienummeridentifikatorer. For eksempel bruger nogle almindelige bogstandarder aritmetisk modulo 11 (hvis udgivet før 1. januar 2007) eller modulo 10 (hvis udgivet før eller efter 1. januar 2007). Tilsvarende, for eksempel i internationale bankkontonumre (IBAN). Dette bruger modulo 97 aritmetik til at opdage brugerindtastningsfejl i bankkontonumre.
I kemi er det sidste ciffer i CAS-registreringsnummeret (det unikke identifikationsnummer for hver kemisk forbindelse) kontrolcifferet. Det beregnes ved at tage det sidste ciffer af de første to dele af CAS-registreringsnummeret ganget med 1, det foregående ciffer 2 gange, det foregående ciffer 3 gange osv., lægge det hele sammen og beregne summen modulo 10.
Hvad er kryptografi? Faktum er, atdet har en meget stærk forbindelse med det emne, der diskuteres. I kryptografi ligger lovene for modulær aritmetik direkte til grund for offentlige nøglesystemer såsom RSA og Diffie-Hellman. Her giver den de endelige felter, der ligger til grund for elliptiske kurver. Anvendes i forskellige symmetriske nøglealgoritmer, herunder Advanced Encryption Standard (AES), International Data Encryption Algorithm og RC4.
Application
Denne metode bruges i områder, hvor du skal læse tal. Det er udviklet af matematikere, og alle bruger det, især dataloger. Dette er veldokumenteret i bøger som Modular Arithmetic for Dummies. En række eksperter anbefaler dog ikke at tage sådan litteratur alvorligt.
I datalogi bruges modulær aritmetik ofte i bitvise og andre operationer, der involverer cirkulære datastrukturer med fast bredde. Analytikere elsker at bruge det. Modulo-operationen er implementeret i mange programmeringssprog og regnemaskiner. I dette tilfælde er det et eksempel på en sådan applikation. Modulo-sammenligning, division med en rest og andre tricks bruges også i programmering.
I musik bruges aritmetisk modulo 12, når man betragter et system med lige temperament på tolv toner, hvor oktaven og enharmonien er ækvivalente. Med andre ord er tasterne i forholdet 1-2 eller 2-1 ækvivalente. I musik og andre humanistiske videnskaber spiller aritmetik en ret væsentlig rolle, men i lærebøgerdataloger plejer ikke at skrive om det.
Metode til at reducere niere
Ni-konverteringsmetoden giver en hurtig kontrol af manuelle decimalregninger. Den er baseret på modulær aritmetik modulo 9 og især på den afgørende egenskab 10 10 1.
der er andre eksempler. Aritmetisk modulo 7 bruges i algoritmer, der bestemmer ugedagen for en bestemt dato. Især Zellers kongruens og Doomsday-algoritmen gør stor brug af aritmetisk modulo 7.
Andre applikationer
Det er allerede blevet sagt om modulær aritmetik i kryptografi. På dette område er hun simpelthen uerstattelig. Mere generelt finder modulær aritmetik også anvendelser i discipliner som jura, økonomi (såsom spilteori) og andre områder af samfundsvidenskaberne. Med andre ord, hvor den forholdsmæssige opdeling og fordeling af ressourcer spiller en stor rolle.
Fordi modulær aritmetik har så mange anvendelsesmuligheder, er det vigtigt at vide, hvor svært det er at løse et sammenligningssystem. Et lineært system af kongruenser kan løses i polynomisk tid i form af Gauss elimination. Dette er beskrevet mere detaljeret af den lineære kongruenssætning. Algoritmer såsom Montgomery-reduktion findes også for at tillade, at simple aritmetiske operationer kan udføres effektivt. For eksempel multiplikation og eksponentiering modulo n, for store tal. Dette er meget vigtigt at vide for at forstå hvadkryptografi. Når alt kommer til alt, fungerer det bare med lignende operationer.
Congruence
Nogle operationer, såsom at finde den diskrete logaritme eller den kvadratiske kongruens, ser ud til at være lige så komplekse som heltalsfaktorisering og er derfor udgangspunktet for kryptografiske algoritmer og kryptering. Disse problemer kan være NP-mellemliggende.
Eksempler
Det følgende er tre ret hurtige C-funktioner - to til at udføre modulær multiplikation og en til at hæve til modulære tal for heltal uden fortegn op til 63 bit, uden forbigående overløb.
Kort efter opdagelsen af heltal (1, 2, 3, 4, 5…) bliver det tydeligt, at de er opdelt i to grupper:
- Lige: deleligt med 2 (0, 2, 4, 6..).
- Ulige: ikke deleligt med 2 (1, 3, 5, 7…).
Hvorfor er denne sondring vigtig? Dette er begyndelsen på abstraktion. Vi bemærker tallets egenskaber (f.eks. lige eller ulige) og ikke kun selve tallet ("37").
Dette giver os mulighed for at udforske matematikken på et dybere niveau og finde relationer mellem t altyper frem for specifikke.
Egenskaber for et nummer
At være en "tre" er blot endnu en egenskab ved et tal. Måske ikke så umiddelbart brugbart som lige/ulige, men det er der. Vi kan oprette regler som "tretten x tre vener=tretten" og så videre. Men det er skørt. Vi kan ikke lave nye ord hele tiden.
Modulo-operationen (forkortet mod eller "%" på mange programmeringssprog) er resten, nårdivision. For eksempel "5 mod 3=2", hvilket betyder, at 2 er resten, når du dividerer 5 med 3.
Når du konverterer almindelige termer til matematik, er et "lige tal", hvor det er "0 mod 2", hvilket betyder, at resten er 0, når det divideres med 2. Et ulige tal er "1 mod 2" (har en rest) af 1).
Lige og ulige tal
Hvad er lige x lige x ulige x ulige? Nå, det er 0 x 0 x 1 x 1=0. Faktisk kan du se, om et lige tal ganges hvor som helst, hvor hele resultatet bliver nul.
Tricket med modulær matematik er, at vi allerede har brugt det til at gemme tid - nogle gange kaldet "ur aritmetik".
For eksempel: 7:00 am (am/pm - betyder ikke noget). Hvor er timeviseren om 7 timer?
Modulations
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 er resten, når 14 er divideret med 12. Ligning 14 mod 12=2 mod 12 betyder 14 timer og 2 timers udseende det samme på et 12-timers ur. De er kongruente, angivet med et tredobbelt lighedstegn: 14 ≡ 2 mod 12.
Et andet eksempel: klokken er 8:00. Hvor er den store hånd om 25 timer?
I stedet for at tilføje 25 til 8, kan du forstå, at 25 timer bare er "1 dag + 1 time". Svaret er enkelt. Så uret slutter 1 time før - klokken 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Du konverterede intuitivt 25 til 1 og tilføjede dette til 8, Ved at bruge uret som en analogi kan vi finde ud af, omreglerne for modulær aritmetik, og de virker.
Addition/Subtraktion
Lad os sige, at to gange ser ens ud på vores ur ("2:00" og "14:00"). Hvis vi tilføjer de samme x timer til begge, hvad sker der så? Nå, de skifter for det samme beløb på uret! 2:00 + 5 timer ≡ 14:00 + 5 timer - begge vil vise 7:00.
Hvorfor? Vi kan blot tilføje 5 til de 2 rester, som begge har, og de går videre på samme måde. For alle kongruente tal (2 og 14) har addition og subtraktion det samme resultat.
Det er sværere at vide, om multiplikationen forbliver den samme. Hvis 14 ≡ 2 (mod 12), kan vi gange begge tal og få det samme resultat? Lad os se, hvad der sker, når vi ganger med 3.
Nå, 2:003 × 6:00. Men hvad er 14:003?
Husk, 14=12 + 2. Så vi kan sige
143=(12 + 2)3=(123) + (23)
Den første del (123) kan ignoreres! Overløbet på 12 timer, der bærer 14, gentager sig ganske enkelt flere gange. Men hvem bekymrer sig? Vi ignorerer alligevel overløbet.
Multiplikation
Når du multiplicerer, er det kun resten, der betyder noget, det vil sige de samme 2 timer for 14:00 og 2:00. Intuitivt er det sådan, jeg ser, at multiplikation ikke ændrer sammenhængen med modulær matematik (du kan gange begge sider af et modulært forhold og få det samme resultat).
Vi gør det intuitivt, men det er rart at give det et navn. Du har et fly, der ankommer kl. 15.00. Hanforsinket med 14 timer. Hvad tid lander den?
14 ≡ 2 mod 12. Så tænk på det som klokken 2, så flyet vil lande klokken 5 om morgenen. Løsningen er enkel: 3 + 2=5 om morgenen. Dette er lidt mere kompliceret end den simple modulo-operation, men princippet er det samme.
