Ngā Kaupapa Taketake o te Ariā Tau
Ko te ariā tau he peka o te pāngarau e ako ana i ngā āhuatanga o ngā tauoti. Ahakoa te āhua māmā noa iho—nā te mea ko ngā tauoti anake kei roto ko te …, -2, -1, 0, 1, 2, …—he hanganga tino whai kiko kei roto i te ariā tau. He maha ngā ariā nui i roto i te pāngarau hou, te whakamunatanga, me te pūtaiao rorohiko e ahu mai ana i ngā ariā taketake o te ariā tau , pērā i te wehewehenga, te tūāpapa, me te ōritetanga. Ka arotakehia e tēnei tuhinga ngā kaupapa matua o te ariā tau: te wehewehenga me te rauropi a Euclid, ngā tau matua me te tauwehewehe , te tauākī modulo, me ētahi tono me ngā ahunga matatau.
1. Ngā tauoti me ngā mahi taketake
Ko te ariā tau e mahi ana i runga i te huinga o ngā tauoti, e tohuhia ana e te ℤ. Ko ngā mahi matua e whakamahia ana ko te tāpiri, te tango, me te whakarea. He rerekē ki ngā tau whaitake, ki ngā tau tūturu rānei, kāore te wehenga mā ngā tauoti e hua ake he tauoti. Koinei te wāhi e noho matua ai te ariā o te wehenga me te toenga.
Ko tētahi whanaungatanga nui i roto i te ariā tau ko te wehewehenga. Mō ngā tauoti \(a\) me \(b\), ka tuhia e mātou \(a \mid b\) mēnā he tauoti \(k\) kei reira \(b = ak\). Hei tauira, \(3 \mid 12\) nā te mea \(12 = 3 \times 4\), engari \(5 \nmid 12\) nā te mea kāore he tauoti \(k\) e \(12 = 5k\).
Ko ngā āhuatanga matua o te wehewehenga:
– Mēnā ko \(a \mid b\) me \(a \mid c\), ko \(a \mid (b+c)\) me \(a \mid (bc)\).
– Mēnā ko \(a \mid b\), kāti mō ia tauoti \(k\), ko \(a \mid (bk)\).
– Mēnā ko \(a \mid b\) me \(b \mid c\), ko \(a \mid c\) te ingoa.
Ka whakamahia ēnei āhuatanga māmā hei taputapu mō te whakamatau i ngā kōrero maha mō ngā tauoti.
2. Rautaki wehewehe
E kī ana te ariā wehewehe: mō ia tauoti \(a\) me ia tauoti pai \(b\), he tauoti ahurei \(q\) me \(r\) kia:
\[
a = bq + r,\quad 0 \le r < b \] I konei ka kiia ko \(q\) te wāhanga hua, ā, ko \(r\) te toenga. Hei tauira: mēnā ko \(a=29\) me \(b=5\), kāti ko \(29 = 5\cdot 5 + 4\), kia rite ai ko \(q=5\) me \(r=4\). He mea nui tēnei ariā nā te mea koinei te pūtake Te mahi modulo me te rauropi a Euclid hei kimi i te GCD. 3. Te Wehewehenga Noa Nui (GCD) me te rauropi a Euclid Mō ngā tauoti e rua \(a\) me \(b\) (ehara i te kore e rua), ko te wehewehenga noa nui rawa, te GCD rānei—e tohuhia ana ko \(\gcd(a,b)\)—ko te tauotinga pai nui rawa atu e wehewehe ana i a rāua e rua. Ko te huarahi tino whai hua ki te tatau i te GCD ko te rauropi a Euclid. Mā te ariā wehewehe, mēnā: \[ a = bq + r \] kātahi: \[ \gcd(a,b) = \gcd(b,r) \] Ka whakahokia tēnei tukanga kia 0 rā anō te toenga \(r\). I te taahiraa whakamutunga, ko te GCD te wehewehenga whakamutunga ehara i te kore. Tauira tere: kimihia \(\gcd(48,18)\). – \(48 = 18\cdot 2 + 12\) – \(18 = 12\cdot 1 + 6\) – \(12 = 6\cdot 2 + 0\) Kātahi \(\gcd(48,18)=6\). He mea tino nui te rauropi a Euclid nā te mea he tere ahakoa mō ngā tau nui, ā, he tino whai hua i roto i te tatau. 4. Ngā huinga rārangi me te tuakiri a Bézout Ko tētahi hua matua ko te tuakiri a Bézout: mō ngā tauoti \(a\) me \(b\) kāore i te kore, kei reira ngā tauoti \(x\) me \(y\) kia penei: \[ \gcd(a,b) = ax + by \] Ko te tikanga o tēnei ka taea te tuhi i te GCD hei huinga rārangi o \(a\) me \(b\). Ka taea te kimi i ngā uara o \(x\) me \(y\) mā te rauropi whānui a Euclid. He mea nui te tuakiri o Bézout hei whakaoti rapanga: – te whārite Diophantine rārangi \(ax+by=c\), – te kimi i tōna modulo inverse (he mea nui i roto i te whakamunatanga). 5. Ngā tau matua me te tauwehenga He tau matua he tauoti pai ake i te 1 e rua noa iho ngā wehewehe pai: 1 me ia anō. Ko ngā tau pēnei i te 2, 3, 5, 7, 11 he tauoti. Ko ngā tau nui ake i te 1 engari ehara i te tauoti ka kiia he hiato, hei tauira 12, 21, 35. Ko te ariā rongonui ko te Kaupapa Taketake o te Arithmetic: ka taea te tuhi motuhake i ia tauoti \(n>1\) (kia rite ki te raupapa) hei hua o ngā tau matua:
\[
n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}
\]
Hei tauira:
\[
360 = 2^3 \cdot 3^2 \cdot 5
\]
Ko tēnei ahurei o te tauwehewehe te tūāpapa o ngā kaupapa matatau maha, tae atu ki te whakamunatanga RSA e whakawhirinaki ana ki te uauatanga o te tauwehewehe i ngā tau nui.
6. Te ōritetanga me te taunga tātaitanga modulo
Ka ako te Modulo arithmetic i ngā tau e ahu mai ana i te toenga o te wehenga. Ka mea mātou:
\[
a \equiv b \pmod{m}
\]
mēnā ko \(m \mid (ab)\), ko te tikanga he ōrite te toenga o \(a\) me \(b\) ina wehea ki \(m\).
Tauira: \(17 \equiv 5 \pmod{12}\) nā te mea ka taea te wehewehe i te \(17-5=12\) mā te 12. I roto i te modulo 12, e kiia ana he ōrite te 17 me te 5.
He rite tonu ngā āhuatanga o te ōritetanga ki ngā mahi noa:
– Mēnā ko \(a \equiv b \pmod{m}\) me \(c \equiv d \pmod{m}\), kātahi
\(a+c \equiv b+d \pmod{m}\) me \(ac \equiv bd \pmod{m}\).
He tino whai hua te Modulo arithmetic mō:
– te whakatau i ngā tauira ā-wā,
– tirohia ngā maha,
– te hoahoa i ngā rauropi rorohiko whai hua,
– me te whakamunatanga o ēnei rā.
7. Ngā whārite whakamuri me te ōritetanga modulo
He modulo whakamuri te tau \(a\) mēnā he tau \(x\) pēnei:
\[
toki \equiv 1 \pmod{m}
\]
Ka noho tēnei whakahuri mēnā ko \(\gcd(a,m)=1\, ā, mēnā anake ko \(\gcd(a,m)=1\). Hei tauira, he whakahuri modulo 7 tā te 3 nā te mea ko \(3\cdot 5=15\equiv 1 \pmod{7}\), nō reira ko tōna whakahuri ko 5.
Mā te ariā o te modulo inverse ka māmā ake te whakaoti i ngā whārite pēnei i:
\[
toki \equiv b \pmod{m}
\]
Mena kei te wātea te whakahuri o \(a^{-1}\), ka taea te whiwhi i te otinga mā te whakarea i ngā taha e rua:
\[
x \equiv a^{-1} b \pmod{m}
\]
8. Te ariā iti a Fermat me te ariā a Euler
E rua ngā hua rongonui o te ariā tau taketake:
1. Te Ariā Iti a Fermat: mēnā ko te \(p\) te matua, ā, kāore a \(a\) e taea te wehewehe e \(p\), kāti:
\[
a^{p-1} \equiv 1 \pmod{p}
\]
2. Te ariā a Euler (whakawhānuitanga): mēnā \(\gcd(a,m)=1\), kāti:
\[
a^{\varphi(m)} \equiv 1 \pmod{m}
\]
ko \(\varphi(m)\) te mahi totien a Euler (te maha o ngā tau i waenga i te 1 me te \(m\) e rite ana ki te matua ki te \(m\)).
Ko ēnei ariā te pūtake o ngā tikanga whakamuna me ngā tikanga tatau modulo tere.
9. Ngā tono me ngā tohutohu matatau
Ahakoa i tīmata hei pātai māmā mō ngā tauoti, kua whānui haere te ariā tau. Ko ōna tono ko:
– Whakamunatanga: Ka whakamahia e te RSA, Diffie–Hellman, me ngā ānau porowhita ngā āhuatanga matua, ōritenga, me te modulo whakamuri.
– Pūtaiao rorohiko: tātaitanga, ngā kaihanga tau matapōkere, me ngā rauropi rorohiko tau nui.
– Te ariā whakakotahitanga me te ariā waehere: te hanga waehere whakatika-hapa me ngā hanganga motuhake.
Ko ngā kaupapa matatau e akohia ana i muri i ēnei kaupapa matua ko ngā whārite Diophantine kore-raina, ngā toenga tapawhā, te ariā tau taurangi, me te tohatoha o ngā tau matua.
Te Katinga
Ko ngā kaupapa matua o te ariā tau e ahu mai ana i ngā ariā o te wehewehenga, te GCF, ngā tau matua, me te ōritetanga. Mai i te rauropi a Euclid ki te modulo arithmetic, ko ia ariā te tūāpapa mō te mārama ki te hanganga o ngā tauoti, ā, ka whakatakoto i te ara mō ngā tono o te ao tūturu, inā koa i te ao matihiko. Mā te matatau ki ēnei ariā taketake ka whakaratohia he taputapu kaha mō te tātari i ngā raruraru pāngarau motuhake me te ruku hohonu ki ngā kaupapa hohonu o te ariā tau hou.
