Matemātikā moduļu aritmētika ir veselu skaitļu aprēķinu sistēma, ar kuras palīdzību tie "apgriežas", sasniedzot noteiktu vērtību - moduli (vai to daudzskaitli). Mūsdienu pieeju šāda veida zinātnei izstrādāja Kārlis Frīdrihs Gauss savā 1801. gadā publicētajā Disquisitiones Arithmeticae. Datorzinātniekiem ļoti patīk izmantot šo metodi, jo tā ir ļoti interesanta un paver noteiktas jaunas iespējas darbībās ar skaitļiem.
Essence
" 12:00". "0:00". Galu galā 12 ir tas pats, kas 0 modulo 12.
Modulāro aritmētiku var apstrādāt matemātiski, ieviešot kongruentu relāciju ar veseliem skaitļiem, kas ir saderīga ar darbībām ar veseliem skaitļiemskaitļi: saskaitīšana, atņemšana un reizināšana. Pozitīvam veselam skaitlim n divi skaitļi a un b tiek uzskatīti par kongruentiem modulo n, ja to starpība a - b ir n daudzkārtņa (tas ir, ja pastāv vesels skaitlis k, ka a - b=kn).
Atskaitījumi
Teorētiskajā matemātikā moduļu aritmētika ir viens no skaitļu teorijas pamatiem, kas ietekmē gandrīz visus tās izpētes aspektus, un to plaši izmanto arī grupu, gredzenu, mezglu un abstraktās algebras teorijā. Lietišķās matemātikas jomā to izmanto datoralgebrā, kriptogrāfijā, datorzinātnēs, ķīmijā, vizuālajā mākslā un mūzikā.
Prakse
Ļoti praktisks pielietojums ir kontrolsummu aprēķināšana sērijas numuru identifikatoros. Piemēram, dažos izplatītos grāmatu standartos tiek izmantots aritmētikas modulo 11 (ja izlaists pirms 2007. gada 1. janvāra) vai modulo 10 (ja tas ir izlaists pirms vai pēc 2007. gada 1. janvāra). Līdzīgi, piemēram, starptautiskajos bankas kontu numuros (IBAN). Tas izmanto modulo 97 aritmētiku, lai noteiktu lietotāja ievades kļūdas bankas kontu numuros.
Ķīmijā CAS reģistrācijas numura (katra ķīmiskā savienojuma unikālais identifikācijas numurs) pēdējais cipars ir kontrolcipars. To aprēķina, CAS reģistrācijas numura pirmo divu daļu pēdējo ciparu reizinot ar 1, iepriekšējo ciparu 2 reizes, iepriekšējo ciparu 3 reizes utt., to visu saskaitot un aprēķinot summu modulo 10.
Kas ir kriptogrāfija? Fakts ir tādstai ir ļoti cieša saikne ar apspriežamo tēmu. Kriptogrāfijā modulārās aritmētikas likumi ir tieši pamatā tādām publiskās atslēgas sistēmām kā RSA un Difija-Helmane. Šeit tas nodrošina ierobežotos laukus, kas ir eliptisku līkņu pamatā. Izmanto dažādos simetrisko atslēgu algoritmos, tostarp uzlabotajā šifrēšanas standartā (AES), starptautiskajā datu šifrēšanas algoritmā un RC4.
Pieteikums
Šo metodi izmanto vietās, kur nepieciešams lasīt skaitļus. To izstrādāja matemātiķi, un visi to izmanto, īpaši datorzinātnieki. Tas ir labi dokumentēts tādās grāmatās kā Modulārā aritmētika manekeniem. Tomēr vairāki eksperti iesaka šādu literatūru neuztvert nopietni.
Datorzinātnēs modulāro aritmētiku bieži izmanto bitu pakāpē un citās operācijās, kas saistītas ar fiksēta platuma apļveida datu struktūrām. Analītiķiem patīk to izmantot. Moduļu darbība ir ieviesta daudzās programmēšanas valodās un kalkulatoros. Šajā gadījumā tas ir viens no šādas lietojumprogrammas piemēriem. Programmēšanā tiek izmantota arī moduļu salīdzināšana, dalīšana ar atlikumu un citi triki.
Mūzikā aritmētisko modulo 12 izmanto, aplūkojot divpadsmit toņu vienāda temperamenta sistēmu, kurā oktāva un enharmonika ir līdzvērtīgas. Citiem vārdiem sakot, taustiņi attiecībā 1-2 vai 2-1 ir līdzvērtīgi. Mūzikā un citās humanitārajās zinātnēs aritmētikai ir diezgan nozīmīga loma, bet mācību grāmatāsdatorzinātnieki parasti par to neraksta.
Deviņnieku samazināšanas metode
9s konversijas metode piedāvā ātru manuālo decimāldaļaritmētisko aprēķinu pārbaudi. Tas ir balstīts uz modulāro aritmētisko modulo 9 un jo īpaši uz izšķirošo īpašību 10 10 1.
ir arī citi piemēri. Aritmētiskais modulo 7 tiek izmantots algoritmos, kas nosaka nedēļas dienu konkrētam datumam. Konkrēti, Zellera kongruence un Pastardienas algoritms plaši izmanto aritmētisko modulo 7.
Citas lietojumprogrammas
Tas jau ir teikts par modulāro aritmētiku kriptogrāfijā. Šajā jomā viņa ir vienkārši neaizvietojama. Vispārīgāk, modulārā aritmētika atrod pielietojumu arī tādās disciplīnās kā tiesību zinātne, ekonomika (piemēram, spēļu teorija) un citās sociālo zinātņu jomās. Citiem vārdiem sakot, kur liela nozīme ir resursu proporcionālai sadalei un sadalei.
Tā kā moduļu aritmētikai ir tik plašs lietojumu klāsts, ir svarīgi zināt, cik grūti ir atrisināt salīdzināšanas sistēmu. Lineāru kongruenču sistēmu var atrisināt polinoma laikā Gausa eliminācijas veidā. To sīkāk apraksta lineārās kongruences teorēma. Pastāv arī tādi algoritmi kā Montgomerija samazināšana, kas ļauj efektīvi veikt vienkāršas aritmētiskās darbības. Piemēram, reizināšanas un kāpināšanas modulo n, lieliem skaitļiem. Tas ir ļoti svarīgi zināt, lai saprastu, kokriptogrāfija. Galu galā tas darbojas tikai ar līdzīgām darbībām.
Congruence
Dažas darbības, piemēram, diskrētā logaritma vai kvadrātiskās kongruences atrašana, šķiet tikpat sarežģītas kā veselu skaitļu faktorizācija, un tādējādi tās ir sākumpunkts kriptogrāfijas algoritmiem un šifrēšanai. Šīs problēmas var būt NP-vidēja līmeņa.
Piemēri
Tālāk ir norādītas trīs diezgan ātras C funkcijas - divas modulāras reizināšanas veikšanai un viena, lai palielinātu līdz moduļu skaitļiem neparakstītiem veseliem skaitļiem līdz 63 bitiem, bez pārejošas pārplūdes.
Īsi pēc veselu skaitļu (1, 2, 3, 4, 5…) atklāšanas kļūst skaidrs, ka tie ir sadalīti divās grupās:
- Pārpāra: dalās ar 2 (0, 2, 4, 6..).
- Nepāra: nedalās ar 2 (1, 3, 5, 7…).
Kāpēc šī atšķirība ir svarīga? Tas ir abstrakcijas sākums. Mēs pamanām skaitļa īpašības (piemēram, pāra vai nepāra), nevis tikai pašu skaitli ("37").
Tas ļauj mums izpētīt matemātiku dziļākā līmenī un atrast attiecības starp skaitļu veidiem, nevis konkrētiem.
Cipara īpašības
Būt "trīs" ir tikai vēl viena skaitļa īpašība. Varbūt ne tik uzreiz noderīgs kā pāra/nepāra, bet tas ir. Mēs varam izveidot noteikumus, piemēram, "trīspadsmit x trīs vēnas=trīspadsmit" un tā tālāk. Bet tas ir traki. Mēs nevaram visu laiku izveidot jaunus vārdus.
Moduļu darbība (saīsināti mod vai "%" daudzās programmēšanas valodās) ir atlikušā daļa, kadnodaļa. Piemēram, "5 mod 3=2", kas nozīmē, ka 2 ir atlikums, dalot 5 ar 3.
Pārveidojot ikdienas terminus par matemātiku, "pāra skaitlis" ir vieta, kur tas ir "0 mod 2", kas nozīmē, ka atlikums ir 0, dalīts ar 2. Nepāra skaitlis ir "1 mod 2" (ar atlikumu no 1).
Pāra un nepāra skaitļi
Kas ir pāra x pāra x nepāra x nepāra? Nu, tas ir 0 x 0 x 1 x 1=0. Patiesībā jūs varat redzēt, vai pāra skaitlis ir reizināts jebkurā vietā, kur viss rezultāts būs nulle.
Modulārās matemātikas viltība ir tāda, ka mēs to jau esam izmantojuši laika glabāšanai - dažreiz to sauc par "pulksteņa aritmētiku".
Piemēram: 7:00 (am/pm - nav nozīmes). Kur būs stundu rādītājs pēc 7 stundām?
Modulācijas
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 ir atlikums, ja 14 dala ar 12. Vienādojums 14 mod 12=2 mod 12 nozīmē 14 stundas un 2 stundas izskatās tas pats 12 stundu pulkstenī. Tie ir kongruenti, apzīmēti ar trīskāršu vienādības zīmi: 14 ≡ 2 mod 12.
Cits piemērs: ir pulksten 8:00. Kur būs lielā kombinācija pēc 25 stundām?
Tā vietā, lai pievienotu 25 pret 8, jūs varat saprast, ka 25 stundas ir tikai "1 diena + 1 stunda". Atbilde ir vienkārša. Tātad pulkstenis beigsies 1 stundu uz priekšu - plkst. 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Jūs intuitīvi konvertējāt 25 uz 1 un pievienojāt šo līdz 8.
Izmantojot pulksteni kā analoģiju, mēs varam noskaidrot, vaimodulārās aritmētikas likumi, un tie darbojas.
Saskaitīšana/atņemšana
Pieņemsim, ka mūsu pulkstenī divas reizes izskatās vienādi ("2:00" un "14:00"). Ja abām pieskaitām vienas un tās pašas x stundas, kas notiks? Nu viņi mainās par tādu pašu summu pulkstenī! 2:00 + 5 stundas ≡ 14:00 + 5 stundas - abi tiks rādīti 7:00.
Kāpēc? Mēs varam vienkārši pievienot 5 pie 2 atlikumiem, kas abiem ir, un tie virzās uz priekšu tādā pašā veidā. Visiem kongruentiem skaitļiem (2 un 14) saskaitīšanai un atņemšanai ir vienāds rezultāts.
Ir grūtāk noteikt, vai reizināšana paliek nemainīga. Ja 14 ≡ 2 (mod 12), vai varam reizināt abus skaitļus un iegūt tādu pašu rezultātu? Apskatīsim, kas notiek, reizinot ar 3.
Nu, 2:003 × 6:00. Bet kas ir 14:003?
Atcerieties, 14=12 + 2. Tātad mēs varam teikt
143=(12 + 2)3=(123) + (23)
Pirmo daļu (123) var ignorēt! 12 stundu pārplūde, kas nes 14, vienkārši atkārtojas vairākas reizes. Bet kam tas rūp? Mēs jebkurā gadījumā ignorējam pārplūdi.
Reizināšana
Reizinot, nozīme ir tikai atlikumam, tas ir, vienas un tās pašas 2 stundas 14:00 un 2:00. Intuitīvi šādi es redzu, ka reizināšana nemaina attiecības ar modulāro matemātiku (varat reizināt abas moduļu attiecības puses un iegūt tādu pašu rezultātu).
Mēs to darām intuitīvi, taču ir patīkami dot tam nosaukumu. Jums ir lidojums, kas ierodas pulksten 15.00. Viņškavējas par 14 stundām. Cikos tas nolaidīsies?
14 ≡ 2 mod 12. Tātad, domājiet par to kā pulksten 2, lai lidmašīna nolaidīsies pulksten 5 no rīta. Risinājums ir vienkāršs: 3 + 2=5 no rīta. Tas ir nedaudz sarežģītāks par vienkāršu modulo darbību, taču princips ir vienāds.
