In matematica, l'aritmetica modulare è un sistema di calcolo per numeri interi, con l'aiuto del quale "rib altano" quando raggiungono un certo valore - il modulo (o il plurale di essi). L'approccio moderno a questo tipo di scienza è stato sviluppato da Carl Friedrich Gauss nella sua Disquisitiones Arithmeticae pubblicata nel 1801. Gli informatici amano molto usare questo metodo, poiché è molto interessante e apre nuove possibilità nelle operazioni con i numeri.
Essenza
Poiché il numero di ore ricomincia dopo aver raggiunto 12, è aritmetica modulo 12. Secondo la definizione seguente, 12 corrisponde non solo a 12, ma anche a 0, quindi si può anche nominare il tempo chiamato " 12:00". "0:00". Dopotutto, 12 è uguale a 0 modulo 12.
L'aritmetica modulare può essere elaborata matematicamente introducendo una relazione congruente agli interi che sia compatibile con le operazioni sugli interinumeri: addizione, sottrazione e moltiplicazione. Per un intero positivo n, due numeri aeb si dicono congruenti modulo n se la loro differenza a - b è un multiplo di n (cioè, se esiste un intero k tale che a - b=kn).
Deduzioni
Nella matematica teorica, l'aritmetica modulare è uno dei fondamenti della teoria dei numeri, interessa quasi tutti gli aspetti del suo studio, ed è anche ampiamente utilizzata nella teoria dei gruppi, degli anelli, dei nodi e dell'algebra astratta. Nel campo della matematica applicata, è utilizzato nell'algebra informatica, nella crittografia, nell'informatica, nella chimica, nelle arti visive e nella musica.
Pratica
Un'applicazione molto pratica è il calcolo dei checksum negli identificatori del numero di serie. Ad esempio, alcuni standard di libri comuni utilizzano l'aritmetica modulo 11 (se rilasciato prima del 1 gennaio 2007) o modulo 10 (se rilasciato prima o dopo il 1 gennaio 2007). Allo stesso modo, ad esempio, in International Bank Account Numbers (IBAN). Questo utilizza l'aritmetica modulo 97 per rilevare gli errori di input dell'utente nei numeri di conto bancario.
In chimica, l'ultima cifra del numero di registrazione CAS (il numero di identificazione univoco per ogni composto chimico) è la cifra di controllo. Si calcola prendendo l'ultima cifra delle prime due parti del numero di registrazione CAS moltiplicata per 1, la cifra precedente 2 volte, la cifra precedente 3 volte, ecc., sommando il tutto e calcolando la somma modulo 10.
Cos'è la crittografia? Il fatto è cheha una connessione molto forte con l'argomento in discussione. In crittografia, le leggi dell'aritmetica modulare sono direttamente alla base dei sistemi a chiave pubblica come RSA e Diffie-Hellman. Qui fornisce i campi finiti che stanno alla base delle curve ellittiche. Utilizzato in vari algoritmi a chiave simmetrica, tra cui Advanced Encryption Standard (AES), International Data Encryption Algorithm e RC4.
Applicazione
Questo metodo viene utilizzato nelle aree in cui è necessario leggere i numeri. È stato sviluppato da matematici e tutti lo usano, specialmente gli informatici. Questo è ben documentato in libri come Modular Arithmetic for Dummies. Tuttavia, numerosi esperti raccomandano di non prendere sul serio tale letteratura.
In informatica, l'aritmetica modulare viene spesso utilizzata in operazioni bit a bit e in altre operazioni che coinvolgono strutture di dati circolari a larghezza fissa. Gli analisti amano usarlo. L'operazione modulo è implementata in molti linguaggi di programmazione e calcolatrici. In questo caso, è un esempio di tale applicazione. Nella programmazione vengono utilizzati anche il confronto modulo, la divisione con un resto e altri trucchi.
In musica si usa l'aritmetica modulo 12 quando si considera un sistema di temperamento equabile di dodici toni, in cui l'ottava e l'enarmonico sono equivalenti. In altre parole, le chiavi nel rapporto 1-2 o 2-1 sono equivalenti. Nella musica e in altre discipline umanistiche, l'aritmetica gioca un ruolo piuttosto significativo, ma nei libri di testogli informatici di solito non ne scrivono.
Metodo per ridurre i nove
Il metodo di conversione 9s offre un rapido controllo dei calcoli aritmetici decimali manuali. Si basa sull'aritmetica modulare modulo 9 e in particolare sulla proprietà decisiva 10 10 1.
ci sono altri esempi. Il modulo aritmetico 7 viene utilizzato negli algoritmi che determinano il giorno della settimana per una data particolare. In particolare, la congruenza di Zeller e l'algoritmo Doomsday fanno un uso massiccio dell'aritmetica modulo 7.
Altre applicazioni
Si è già detto dell'aritmetica modulare in crittografia. In questo settore, è semplicemente insostituibile. Più in generale, l'aritmetica modulare trova applicazioni anche in discipline come il diritto, l'economia (come la teoria dei giochi) e altre aree delle scienze sociali. In altre parole, dove la divisione proporzionale e la distribuzione delle risorse gioca un ruolo importante.
Poiché l'aritmetica modulare ha una gamma così ampia di usi, è importante sapere quanto sia difficile risolvere un sistema di confronti. Un sistema lineare di congruenze può essere risolto in tempo polinomiale sotto forma di eliminazione gaussiana. Ciò è descritto più dettagliatamente dal teorema della congruenza lineare. Esistono anche algoritmi come la riduzione di Montgomery per consentire l'esecuzione efficiente di semplici operazioni aritmetiche. Ad esempio, moltiplicazione ed esponenziazione modulo n, per numeri grandi. Questo è molto importante da sapere per capire cosacrittografia. Dopotutto, funziona solo con operazioni simili.
Congruenza
Alcune operazioni, come trovare il logaritmo discreto o la congruenza quadratica, sembrano essere complesse quanto la fattorizzazione di interi e quindi sono il punto di partenza per algoritmi crittografici e crittografia. Questi problemi possono essere NP-intermedi.
Esempi
Le seguenti sono tre funzioni C abbastanza veloci: due per eseguire moltiplicazioni modulari e una per aumentare a numeri modulari per interi senza segno fino a 63 bit, senza overflow transitorio.
Poco dopo la scoperta degli interi (1, 2, 3, 4, 5…) diventa evidente che sono divisi in due gruppi:
- Pari: divisibile per 2 (0, 2, 4, 6..).
- Dispari: non divisibile per 2 (1, 3, 5, 7…).
Perché questa distinzione è importante? Questo è l'inizio dell'astrazione. Notiamo le proprietà del numero (ad es. pari o dispari) e non solo il numero stesso ("37").
Questo ci permette di esplorare la matematica a un livello più profondo e trovare relazioni tra tipi di numeri piuttosto che specifici.
Proprietà di un numero
Essere un "tre" è solo un' altra proprietà di un numero. Forse non è immediatamente utile come pari/dispari, ma è lì. Possiamo creare regole come "tredici x tre vena=tredici" e così via. Ma è pazzesco. Non possiamo scrivere sempre nuove parole.
L'operazione modulo (abbreviata mod o "%" in molti linguaggi di programmazione) è il resto quandodivisione. Ad esempio, "5 mod 3=2", che significa 2 è il resto quando dividi 5 per 3.
Quando si convertono i termini di tutti i giorni in matematica, un "numero pari" è dove è "0 mod 2", il che significa che il resto è 0 quando diviso per 2. Un numero dispari è "1 mod 2" (ha un resto di 1).
Numeri pari e dispari
Che cos'è pari x pari x dispari x dispari? Bene, è 0 x 0 x 1 x 1=0. In re altà, puoi vedere se un numero pari viene moltiplicato ovunque, dove l'intero risultato sarà zero.
Il trucco con la matematica modulare è che l'abbiamo già usata per memorizzare il tempo, a volte chiamato "aritmetica dell'orologio".
Ad esempio: 7:00 (am/pm - non importa). Dove sarà la lancetta delle ore tra 7 ore?
Modulazioni
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 è il resto quando 14 è diviso per 12. Equazione 14 mod 12=2 mod 12 significa 14 ore e 2 ore guarda il lo stesso su un orologio a 12 ore. Sono congruenti, indicati da un triplo segno di uguale: 14 ≡ 2 mod 12.
Un altro esempio: sono le 8:00. Dove sarà la grande mano tra 25 ore?
Invece di aggiungere 25 a 8, puoi capire che 25 ore sono solo "1 giorno + 1 ora". La risposta è semplice. Quindi, l'orologio finirà 1 ora prima - alle 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Hai convertito intuitivamente 25 in 1 e aggiunto questo a 8.
Usando l'orologio come analogia, possiamo capire se ille regole dell'aritmetica modulare e funzionano.
Addizione/Sottrazione
Diciamo che due volte sono uguali sul nostro orologio ("2:00" e "14:00"). Se aggiungiamo le stesse x ore a entrambi, cosa succede? Bene, cambiano per la stessa quantità sull'orologio! 2:00 + 5 ore ≡ 14:00 + 5 ore - entrambi mostreranno 7:00.
Perché? Possiamo semplicemente aggiungere 5 ai 2 resti che hanno entrambi e avanzano allo stesso modo. Per tutti i numeri congruenti (2 e 14), addizione e sottrazione hanno lo stesso risultato.
È più difficile sapere se la moltiplicazione rimane la stessa. Se 14 ≡ 2 (mod 12), possiamo moltiplicare entrambi i numeri e ottenere lo stesso risultato? Vediamo cosa succede quando moltiplichiamo per 3.
Bene, 2:003 × 6:00. Ma cosa sono 14:003?
Ricorda, 14=12 + 2. Quindi possiamo dire
143=(12 + 2)3=(123) + (23)
La prima parte (123) può essere ignorata! L'overflow di 12 ore che porta 14 semplicemente si ripete più volte. Ma a chi importa? Ignoriamo comunque l'overflow.
Moltiplicazione
Quando si moltiplica, conta solo il resto, ovvero le stesse 2 ore per le 14:00 e le 2:00. Intuitivamente, è così che vedo la moltiplicazione che non cambia la relazione con la matematica modulare (puoi moltiplicare entrambi i lati di una relazione modulare e ottenere lo stesso risultato).
Lo facciamo in modo intuitivo, ma è bello dargli un nome. Hai un volo in arrivo alle 15:00. Luiritardato di 14 ore. A che ora atterrerà?
14 ≡ 2 mod 12. Quindi, pensa che siano le 2, quindi l'aereo atterrerà alle 5 del mattino. La soluzione è semplice: 3 + 2=5 del mattino. Questo è un po' più complicato della semplice operazione modulo, ma il principio è lo stesso.
