I matematikk er modulær aritmetikk et regnesystem for heltall, ved hjelp av hvilket de "snur" når de når en viss verdi - modulen (eller flertallet av dem). Den moderne tilnærmingen til denne typen vitenskap ble utviklet av Carl Friedrich Gauss i hans Disquisitiones Arithmeticae publisert i 1801. Informatikere er veldig glade i å bruke denne metoden, siden den er veldig interessant og åpner for visse nye muligheter i operasjoner med tall.
Essence
Fordi timetallet starter igjen etter at det når 12, er det aritmetisk modulo 12. I følge definisjonen nedenfor tilsvarer 12 ikke bare 12, men også 0, så man kan også navngi tiden k alt " 12:00". "0:00". Tross alt er 12 det samme som 0 modulo 12.
Modulær aritmetikk kan behandles matematisk ved å introdusere en kongruent relasjon til heltall som er kompatibel med operasjoner på heltalltall: addisjon, subtraksjon og multiplikasjon. For et positivt heltall n sies to tall a og b å være kongruente modulo n hvis forskjellen deres a - b er et multiplum av n (det vil si hvis det finnes et heltall k slik at a - b=kn).
Deductions
I teoretisk matematikk er modulær aritmetikk et av grunnlagene for tallteori, som påvirker nesten alle aspekter av studiet, og er også mye brukt i teorien om grupper, ringer, knuter og abstrakt algebra. Innenfor anvendt matematikk brukes det innen dataalgebra, kryptografi, informatikk, kjemi, visuell kunst og musikk.
Øv
En veldig praktisk applikasjon er beregning av kontrollsummer i serienummeridentifikatorer. For eksempel bruker noen vanlige bokstandarder aritmetisk modulo 11 (hvis utgitt før 1. januar 2007) eller modulo 10 (hvis utgitt før eller etter 1. januar 2007). Tilsvarende, for eksempel i internasjonale bankkontonumre (IBAN). Dette bruker modulo 97 aritmetikk for å oppdage brukerinndatafeil i bankkontonumre.
I kjemi er det siste sifferet i CAS-registreringsnummeret (det unike identifikasjonsnummeret for hver kjemisk forbindelse) kontrollsifferet. Det beregnes ved å ta det siste sifferet av de to første delene av CAS-registreringsnummeret multiplisert med 1, det forrige sifferet 2 ganger, det forrige sifferet 3 ganger osv., legge det hele sammen og beregne summen modulo 10.
Hva er kryptografi? Faktum er detden har en veldig sterk sammenheng med temaet som diskuteres. I kryptografi ligger lovene for modulær aritmetikk direkte til grunn for offentlige nøkkelsystemer som RSA og Diffie-Hellman. Her gir den de endelige feltene som ligger til grunn for elliptiske kurver. Brukes i ulike symmetriske nøkkelalgoritmer, inkludert Advanced Encryption Standard (AES), International Data Encryption Algorithm og RC4.
Application
Denne metoden brukes i områder der du trenger å lese tall. Den ble utviklet av matematikere, og alle bruker den, spesielt informatikere. Dette er godt dokumentert i bøker som Modular Arithmetic for Dummies. En rekke eksperter anbefaler imidlertid å ikke ta slik litteratur på alvor.
I informatikk brukes modulær aritmetikk ofte i bitvise og andre operasjoner som involverer sirkulære datastrukturer med fast bredde. Analytikere elsker å bruke det. Modulo-operasjonen er implementert i mange programmeringsspråk og kalkulatorer. I dette tilfellet er det ett eksempel på en slik applikasjon. Modulo-sammenligning, divisjon med en rest og andre triks brukes også i programmering.
I musikk brukes aritmetikk modulo 12 når man vurderer et system med likt temperament på tolv toner, der oktaven og enharmonien er likeverdige. Med andre ord, nøklene i forholdet 1-2 eller 2-1 er likeverdige. I musikk og annen humaniora spiller aritmetikk en ganske betydelig rolle, men i lærebøkerinformatikere skriver vanligvis ikke om det.
Metode for å redusere niere
Ni-konverteringsmetoden gir en rask sjekk av manuelle desimalregninger. Den er basert på modulær aritmetikk modulo 9 og spesielt på den avgjørende egenskapen 10 10 1.
det er andre eksempler. Aritmetisk modulo 7 brukes i algoritmer som bestemmer ukedagen for en bestemt dato. Spesielt Zellers kongruens og Doomsday-algoritmen gjør mye bruk av aritmetisk modulo 7.
Andre applikasjoner
Det har allerede blitt sagt om modulær aritmetikk i kryptografi. På dette området er hun rett og slett uerstattelig. Mer generelt finner modulær aritmetikk også anvendelser i disipliner som juss, økonomi (som spillteori) og andre områder av samfunnsvitenskapene. Med andre ord, hvor proporsjonal fordeling og fordeling av ressurser spiller en stor rolle.
Fordi modulær aritmetikk har så mange bruksområder, er det viktig å vite hvor vanskelig det er å løse et sammenligningssystem. Et lineært system av kongruenser kan løses i polynomisk tid i form av gaussisk eliminering. Dette er beskrevet mer detaljert ved lineær kongruenssetning. Algoritmer som Montgomery-reduksjon eksisterer også for å tillate at enkle aritmetiske operasjoner utføres effektivt. For eksempel multiplikasjon og eksponentiering modulo n, for store tall. Dette er veldig viktig å vite for å forstå hvakryptografi. Tross alt fungerer det bare med lignende operasjoner.
Congruence
Noen operasjoner, som å finne den diskrete logaritmen eller den kvadratiske kongruensen, ser ut til å være like komplekse som heltallsfaktorisering og er derfor utgangspunktet for kryptografiske algoritmer og kryptering. Disse problemene kan være NP-mellomliggende.
Eksempler
Følgende er tre ganske raske C-funksjoner - to for å utføre modulær multiplikasjon og en for å øke til modulære tall for heltall uten fortegn opp til 63 biter, uten forbigående overløp.
Kort etter oppdagelsen av heltall (1, 2, 3, 4, 5…) blir det tydelig at de er delt inn i to grupper:
- Even: delelig med 2 (0, 2, 4, 6..).
- Odd: ikke delelig med 2 (1, 3, 5, 7…).
Hvorfor er denne forskjellen viktig? Dette er begynnelsen på abstraksjon. Vi legger merke til egenskapene til tallet (f.eks. partall eller oddetall) og ikke bare selve tallet ("37").
Dette lar oss utforske matematikken på et dypere nivå og finne sammenhenger mellom talltyper i stedet for spesifikke.
Egenskaper til et tall
Å være en "tre" er bare en annen egenskap ved et tall. Kanskje ikke like umiddelbart nyttig som partall/oddetall, men det er der. Vi kan lage regler som "tretten x tre årer=tretten" og så videre. Men det er galskap. Vi kan ikke lage nye ord hele tiden.
Moduloperasjonen (forkortet mod eller "%" på mange programmeringsspråk) er resten nårinndeling. For eksempel, "5 mod 3=2", som betyr at 2 er resten når du deler 5 på 3.
Når du konverterer daglige termer til matematikk, er et "partall" der det er "0 mod 2", som betyr at resten er 0 når delt på 2. Et oddetall er "1 mod 2" (har en rest) av 1).
partall og oddetall
Hva er partall x partall x oddetall x oddetall? Vel, det er 0 x 0 x 1 x 1=0. Du kan faktisk se om et partall multipliseres hvor som helst, der hele resultatet blir null.
Trikset med modulær matematikk er at vi allerede har brukt den til å lagre tid - noen ganger k alt "klokkearitmetikk".
For eksempel: 7:00 am (am/pm - spiller ingen rolle). Hvor vil timeviseren være om 7 timer?
Modulations
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 er resten når 14 er delt på 12. Ligning 14 mod 12=2 mod 12 betyr 14 timer og 2 timer. samme på en 12-timers klokke. De er kongruente, indikert med et trippelt likhetstegn: 14 ≡ 2 mod 12.
Et annet eksempel: klokken er 8:00. Hvor er den store hånden om 25 timer?
I stedet for å legge til 25 til 8, kan du forstå at 25 timer bare er "1 dag + 1 time". Svaret er enkelt. Så klokken slutter 1 time foran – klokken 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Du konverterte intuitivt 25 til 1 og la til dette til 8, Ved å bruke klokken som en analogi kan vi finne ut omreglene for modulær aritmetikk, og de fungerer.
Addisjon/Subtraksjon
La oss si at to ganger ser like ut på klokken vår ("2:00" og "14:00"). Hvis vi legger til de samme x timene til begge, hva skjer? Vel, de endres for samme beløp på klokken! 2:00 + 5 timer ≡ 14:00 + 5 timer - begge vises 7:00.
Hvorfor? Vi kan ganske enkelt legge til 5 til de 2 restene som begge har, og de går videre på samme måte. For alle kongruente tall (2 og 14) gir addisjon og subtraksjon samme resultat.
Det er vanskeligere å vite om multiplikasjonen forblir den samme. Hvis 14 ≡ 2 (mod 12), kan vi multiplisere begge tallene og få samme resultat? La oss se hva som skjer når vi multipliserer med 3.
Vel, 2:003 × 6:00. Men hva er 14:003?
Husk, 14=12 + 2. Så vi kan si
143=(12 + 2)3=(123) + (23)
Den første delen (123) kan ignoreres! Overløpet på 12 timer som bærer 14 gjentar seg ganske enkelt flere ganger. Men hvem bryr seg? Vi ignorerer overløpet uansett.
Multiplikasjon
Når du multipliserer, er det bare resten som betyr noe, det vil si de samme 2 timene for 14:00 og 2:00. Intuitivt er det slik jeg ser at multiplikasjon ikke endrer forholdet med modulær matematikk (du kan multiplisere begge sider av et modulært forhold og få samme resultat).
Vi gjør det intuitivt, men det er fint å gi det et navn. Du har et fly som ankommer kl. 15.00. Hanforsinket med 14 timer. Når lander den?
14 ≡ 2 mod 12. Så, tenk på det som klokken 2, så flyet vil lande klokken 5 om morgenen. Løsningen er enkel: 3 + 2=05.00. Dette er litt mer komplisert enn den enkle modulo-operasjonen, men prinsippet er det samme.
