Sa matematika, ang modular arithmetic ay isang sistema ng pagkalkula para sa mga integer, sa tulong ng kung saan sila "ibabalik" kapag naabot nila ang isang tiyak na halaga - ang module (o ang maramihan ng mga ito). Ang modernong diskarte sa ganitong uri ng agham ay binuo ni Carl Friedrich Gauss sa kanyang Disquisitiones Arithmeticae na inilathala noong 1801. Ang mga computer scientist ay gustong-gustong gumamit ng paraang ito, dahil ito ay lubhang kawili-wili at nagbubukas ng ilang partikular na bagong posibilidad sa mga operasyong may mga numero.
Essence
Dahil ang bilang ng mga oras ay magsisimula muli pagkatapos na umabot sa 12, ito ay arithmetic modulo 12. Ayon sa kahulugan sa ibaba, ang 12 ay tumutugma hindi lamang sa 12, kundi pati na rin sa 0, kaya maaari ding pangalanan ang oras na tinatawag na " 12:00". "0:00". Pagkatapos ng lahat, ang 12 ay kapareho ng 0 modulo 12.
Ang modular na arithmetic ay maaaring iproseso sa matematika sa pamamagitan ng pagpapakilala ng kaparehong kaugnayan sa mga integer na tugma sa mga operasyon sa mga integermga numero: karagdagan, pagbabawas at pagpaparami. Para sa isang positibong integer n, ang dalawang numero a at b ay sinasabing magkaparehong modulo n kung ang kanilang pagkakaiba a - b ay isang multiple ng n (iyon ay, kung mayroong isang integer k na ang a - b=kn).
Deductions
Sa teoretikal na matematika, ang modular arithmetic ay isa sa mga pundasyon ng teorya ng numero, na nakakaapekto sa halos lahat ng aspeto ng pag-aaral nito, at malawak ding ginagamit sa teorya ng mga grupo, singsing, buhol at abstract algebra. Sa larangan ng applied mathematics, ginagamit ito sa computer algebra, cryptography, computer science, chemistry, visual arts at music.
Pagsasanay
Ang isang napakapraktikal na aplikasyon ay ang pagkalkula ng mga checksum sa mga serial number identifier. Halimbawa, ang ilang karaniwang pamantayan ng libro ay gumagamit ng arithmetic modulo 11 (kung inilabas bago ang Enero 1, 2007) o modulo 10 (kung inilabas bago o pagkatapos ng Enero 1, 2007). Katulad nito, halimbawa, sa International Bank Account Numbers (IBANs). Gumagamit ito ng modulo 97 arithmetic para makita ang mga error sa pag-input ng user sa mga bank account number.
Sa chemistry, ang huling digit ng CAS registration number (ang natatanging identification number para sa bawat chemical compound) ay ang check digit. Kinakalkula ito sa pamamagitan ng pagkuha ng huling digit ng unang dalawang bahagi ng CAS registration number na minu-multiply sa 1, ang nakaraang digit 2 beses, ang nakaraang digit 3 beses, atbp., pagdaragdag ng lahat ng ito at pagkalkula ng sum modulo 10.
Ano ang cryptography? Sa katotohanan ayito ay may napakalakas na koneksyon sa paksang tinatalakay. Sa cryptography, ang mga batas ng modular arithmetic ay direktang sumasailalim sa mga public-key system gaya ng RSA at Diffie-Hellman. Dito nagbibigay ito ng may hangganan na mga field na sumasailalim sa mga elliptic curve. Ginagamit sa iba't ibang symmetric key algorithm, kabilang ang Advanced Encryption Standard (AES), International Data Encryption Algorithm, at RC4.
Application
Ang paraang ito ay ginagamit sa mga lugar kung saan kailangan mong magbasa ng mga numero. Ito ay binuo ng mga mathematician, at lahat ay gumagamit nito, lalo na ang mga computer scientist. Ito ay mahusay na dokumentado sa mga aklat tulad ng Modular Arithmetic for Dummies. Gayunpaman, inirerekomenda ng ilang eksperto na huwag seryosohin ang naturang literatura.
Sa computer science, ang modular arithmetic ay kadalasang ginagamit sa bitwise at iba pang mga operasyong kinasasangkutan ng fixed-width circular data structures. Gustung-gusto ng mga analyst na gamitin ito. Ang modulo operation ay ipinatupad sa maraming programming language at calculators. Sa kasong ito, ito ay isang halimbawa ng naturang aplikasyon. Ang paghahambing ng modulo, paghahati sa natitira, at iba pang mga trick ay ginagamit din sa programming.
Sa musika, ang arithmetic modulo 12 ay ginagamit kapag isinasaalang-alang ang isang sistema ng pantay na temperament ng labindalawang tono, kung saan ang octave at enharmonic ay katumbas. Sa madaling salita, ang mga susi sa ratio na 1-2 o 2-1 ay katumbas. Sa musika at iba pang mga humanidad, ang aritmetika ay gumaganap ng isang makabuluhang papel, ngunit sa mga aklat-aralinAng mga computer scientist ay hindi karaniwang nagsusulat tungkol dito.
Paraan ng pagbabawas ng siyam
Ang paraan ng conversion ng 9s ay nag-aalok ng mabilis na pagsusuri ng mga manu-manong kalkulasyon ng aritmetika ng decimal. Ito ay batay sa modular arithmetic modulo 9 at partikular sa mapagpasyang katangian 10 10 1.
may iba pang mga halimbawa. Ang arithmetic modulo 7 ay ginagamit sa mga algorithm na tumutukoy sa araw ng linggo para sa isang partikular na petsa. Sa partikular, ang congruence ni Zeller at ang Doomsday algorithm ay lubos na gumagamit ng arithmetic modulo 7.
Iba pang mga application
Nasabi na ang tungkol sa modular arithmetic sa cryptography. Sa lugar na ito, siya ay hindi mapapalitan. Sa pangkalahatan, ang modular arithmetic ay nakakahanap din ng mga aplikasyon sa mga disiplina tulad ng batas, ekonomiya (tulad ng teorya ng laro), at iba pang mga bahagi ng agham panlipunan. Sa madaling salita, kung saan ang proporsyonal na paghahati at pamamahagi ng mga mapagkukunan ay may malaking papel.
Dahil ang modular arithmetic ay may malawak na hanay ng mga gamit, mahalagang malaman kung gaano kahirap lutasin ang isang sistema ng mga paghahambing. Ang isang linear na sistema ng mga congruence ay maaaring malutas sa polynomial time sa anyo ng Gaussian elimination. Ito ay inilalarawan nang mas detalyado ng linear congruence theorem. Umiiral din ang mga algorithm tulad ng Montgomery reduction upang payagan ang mga simpleng operasyon ng arithmetic na maisagawa nang mahusay. Halimbawa, multiplication at exponentiation modulo n, para sa malalaking numero. Ito ay napakahalagang malaman upang maunawaan kung anokriptograpiya. Pagkatapos ng lahat, gumagana lang ito sa mga katulad na operasyon.
Congruence
Ang ilang mga operasyon, gaya ng paghahanap ng discrete logarithm o ang quadratic congruence, ay mukhang kasing kumplikado ng integer factorization at sa gayon ay ang panimulang punto para sa cryptographic algorithm at encryption. Maaaring NP-intermediate ang mga problemang ito.
Mga Halimbawa
Ang sumusunod ay tatlong medyo mabilis na C function - dalawa para sa pagsasagawa ng modular multiplication at isa para sa pagtaas sa modular na mga numero para sa mga unsigned integer hanggang 63 bits, nang walang lumilipas na overflow.
Di-nagtagal pagkatapos ng pagtuklas ng mga integer (1, 2, 3, 4, 5…) ay nagiging maliwanag na nahahati sila sa dalawang grupo:
- Even: mahahati ng 2 (0, 2, 4, 6..).
- Kakaiba: hindi nahahati sa 2 (1, 3, 5, 7…).
Bakit mahalaga ang pagkakaibang ito? Ito ang simula ng abstraction. Napansin namin ang mga katangian ng numero (hal., kahit o kakaiba) at hindi lang ang numero mismo ("37").
Nagbibigay-daan ito sa amin na tuklasin ang matematika sa mas malalim na antas at maghanap ng mga ugnayan sa pagitan ng mga uri ng numero kaysa sa mga partikular.
Mga katangian ng isang numero
Ang pagiging "tatlo" ay isa lamang pag-aari ng isang numero. Maaaring hindi kaagad kapaki-pakinabang gaya ng kahit na/kakaiba, ngunit nariyan ito. Maaari tayong lumikha ng mga panuntunan tulad ng "labing tatlo x tatlong ugat=labintatlo" at iba pa. Pero nakakabaliw. Hindi kami makakagawa ng mga bagong salita sa lahat ng oras.
Ang modulo operation (pinaikling mod o "%" sa maraming programming language) ay ang natitira kapagdibisyon. Halimbawa, "5 mod 3=2", ibig sabihin, 2 ang natitira kapag hinati mo ang 5 sa 3.
Kapag nagko-convert ng mga pang-araw-araw na termino sa math, ang isang "even number" ay kung saan ito ay "0 mod 2", ibig sabihin ang natitira ay 0 kapag hinati sa 2. Ang isang odd na numero ay "1 mod 2" (may natitira ng 1).
Even at odd na numero
Ano ang even x even x odd x odd? Well, ito ay 0 x 0 x 1 x 1=0. Sa totoo lang, makikita mo kung ang isang even na numero ay i-multiply kahit saan, kung saan ang buong resulta ay magiging zero.
Ang trick sa modular math ay nagamit na namin ito upang mag-imbak ng oras - kung minsan ay tinatawag na "clock arithmetic".
Halimbawa: 7:00 am (am/pm - hindi mahalaga). Nasaan ang orasan sa loob ng 7 oras?
Modulations
(7 + 7) mod 12=(14) mod 12=2 mod 12 [2 ang natitira kapag ang 14 ay hinati sa 12. Ang equation 14 mod 12=2 mod 12 ay nangangahulugang 14 na oras at 2 oras tingnan ang pareho sa isang 12-oras na orasan. Ang mga ito ay magkatugma, na ipinapahiwatig ng isang triple equal sign: 14 ≡ 2 mod 12.
Isa pang halimbawa: 8:00 am na. Nasaan ang malaking kamay sa loob ng 25 oras?
Sa halip na magdagdag ng 25 sa 8, mauunawaan mong "1 araw + 1 oras" lang ang 25 oras. Simple lang ang sagot. Kaya, ang orasan ay magtatapos nang 1 oras nang mas maaga - sa 9:00.
(8 + 25) mod 12 ≡ (8) mod 12 + (25) mod 12 ≡ (8) mod 12 + (1) mod 12 ≡ 9 mod 12. Intuitively mong na-convert ang 25 sa 1 at idinagdag ito hanggang 8.
Gamit ang orasan bilang pagkakatulad, malalaman natin kung angang mga panuntunan ng modular arithmetic, at gumagana ang mga ito.
Addition/Subtraction
Sabihin nating dalawang beses na magkapareho ang hitsura sa ating orasan ("2:00" at "14:00"). Kung idadagdag natin ang parehong x na oras sa pareho, ano ang mangyayari? Well, nagbabago sila para sa parehong halaga sa orasan! 2:00 + 5 oras ≡ 14:00 + 5 oras - parehong magpapakita ng 7:00.
Bakit? Maaari lamang tayong magdagdag ng 5 sa 2 nalalabi na parehong mayroon at sumusulong sila sa parehong paraan. Para sa lahat ng magkakaparehong numero (2 at 14), ang pagdaragdag at pagbabawas ay may parehong resulta.
Mas mahirap malaman kung mananatiling pareho ang multiplication. Kung 14 ≡ 2 (mod 12), maaari ba nating i-multiply ang parehong mga numero at makakuha ng parehong resulta? Tingnan natin kung ano ang mangyayari kapag nag-multiply tayo sa 3.
Bueno, 2:003 × 6:00. Ngunit ano ang 14:003?
Tandaan, 14=12 + 2. Kaya masasabi nating
143=(12 + 2)3=(123) + (23)
Ang unang bahagi (123) ay maaaring balewalain! Ang pag-apaw ng 12 oras na nagdadala ng 14 ay paulit-ulit lang ng ilang beses. Ngunit sino ang nagmamalasakit? Hindi namin pinapansin ang overflow.
Multiplikasyon
Kapag nag-multiply, ang natitira lang ang mahalaga, ibig sabihin, ang parehong 2 oras para sa 14:00 at 2:00. Sa madaling salita, ganito ang nakikita kong multiplication na hindi nagbabago ng relasyon sa modular math (maaari mong i-multiply ang magkabilang panig ng isang modular na relasyon at makakuha ng parehong resulta).
Ginagawa namin ito nang intuitive, ngunit magandang bigyan ito ng pangalan. May flight kang darating ng 3pm. Siyanaantala ng 14 na oras. Anong oras ito lalapag?
14 ≡ 2 mod 12. Kaya, isipin mo ito bilang 2 o'clock, kaya alas-5 ng umaga lalapag ang eroplano. Ang solusyon ay simple: 3 + 2=5 am. Ito ay medyo mas kumplikado kaysa sa simpleng modulo operation, ngunit pareho ang prinsipyo.
