Whakaarohia tetahi ahuatanga e hiahia ana koe ki te pupuri i tetahi putea putea. Ka whakaarohia he tino kore e taea te whakakore me te kore he ki, ka hoatu ki a koe i te ra tuatahi o te mahi. Ko to whainga ko te penapena haumaru i te ki.
Me kii ka whakatau koe ki te pupuri i te ki ki a koe i nga wa katoa, me te whai waahi ki te rokiroki ina hiahiatia. Engari ka tere koe ki te mohio ko taua otinga kaore e tino pai ana i roto i nga mahi, na te mea ka hiahiatia to waahi tinana i nga wa katoa ka whakatuwherahia e koe te rokiroki. He aha te hararei i oati ai koe? I tua atu, he tino whakamataku te patai: ka pehea mena ka ngaro to kii anake?
I runga i to whakaaro mo to hararei, ka whakatau koe ki te hanga kape o te ki ka tuku ki tetahi atu kaimahi. Heoi, kei te mohio koe ehara tenei i te mea pai. Ma te rearua i te maha o nga taviri, ka ruarua ano nga tupono o te tahae matua.
I te pouri, ka whakangaro koe i te taarua ka whakatau kia wehea te kii taketake kia haurua. Inaianei, ka whakaaro koe e rua nga tangata pono me nga kongakonga matua me noho a tinana ki te kohi i te ki me te whakatuwhera i te waahi. Ko te tikanga me tahae te tahae kia rua nga pihi, he ruarua te uaua ki te tahae i tetahi kii. Heoi, ka mohio koe kaore tenei kaupapa i te pai ake i te kii kotahi noa, na te mea ka ngaro te haurua ki tetahi, kaore e taea te whakahoki mai i te ki tonu.
Ka taea te whakatau i te raru me etahi atu taviri me nga raka, engari ko tenei huarahi ka tere много nga taviri me nga raka. Ka whakatau koe ko te hoahoa pai ko te tohatoha i te ki kia kore ai te haumarutanga e whakawhirinaki katoa ki te tangata kotahi. Ka whakatau ano koe me noho he paepae mo te maha o nga kongakonga na mena ka ngaro tetahi kongakonga (mehemea ka haere te tangata ki te hararei), ka mau tonu te mahi o te taviri katoa.
Me pehea te tiri i tetahi mea ngaro
Ko tenei momo kaupapa whakahaere matua i whakaarohia e Adi Shamir i te tau 1979 i tana whakaputanga i ana mahi
Mai i te tirohanga haumarutanga, ko tetahi taonga nui o tenei kaupapa ko te kore e tino mohio te kaitukino ki nga mea katoa mena kaore i te iti rawa. nga wahanga. Ara te aroaro kaua nga waahanga e tuku korero. Ka kiia tenei taonga haumarutanga kupu.
Te wawaotanga polynomial
Kaupapa paepae Shamir hangaia huri noa i te ariā wawaotanga polynomial. Mena kaore koe i te mohio ki tenei kaupapa, he tino ngawari. Inaa, mena kua tuhi koe i nga tohu ki runga kauwhata ka hono atu ki nga raina me nga pihinga, kua whakamahia e koe!
Ma roto i nga tohu e rua ka taea e koe te tuhi i te maha o nga polynomials o te tohu 2. Hei whiriwhiri i te mea kotahi mai i a raatau, me whai tohu tuatoru koe. Whakaahua:
Whakaarohia te polynomial me te tohu kotahi, . Mena kei te pirangi koe ki te tarai i tenei mahi ki runga kauwhata, e hia nga tohu e hiahia ana koe? Ana, e mohio ana matou he mahi raina tenei e hanga ana i te raina, no reira me rua nga tohu. Muri iho, whakaarohia he mahi polynomial me te tohu tuarua, . He mahi tapawha tenei, no reira kia toru nga tohu e hiahiatia ana hei tarai i te kauwhata. Me pehea te polynomial me te tohu tuatoru? Kia wha nga tohu. A pera tonu me era atu.
Ko te mea tino pai mo tenei taonga ko te tohu o te mahi polynomial me te iti rawa nga tohu, ka taea e tatou te tiki tohu taapiri mo tenei mahi polynomial. Ka kiia e matou te taapiri o enei tohu taapiri wawaotanga polynomial.
Te hanga mea ngaro
Kua mohio pea koe koinei te waahi ka uru mai te kaupapa mohio a Shamir. Me kii ta tatou mea ngaro Ko . Ka taea e tatou te huri ki tetahi tohu i runga i te kauwhata ka puta mai he mahi polynomial me te tohu , e tutuki ana tenei kaupapa. Kia maumahara matou ki a koe ka waiho hei paepae mo nga kongakonga e hiahiatia ana, na, ki te whakatauhia te paepae ki nga wahanga e toru, me whiriwhiri he mahi polynomial me te tohu tuarua.
Ka whai ahua to tatou polynomial te wahi и — kua tīpako matapōkeretia tauoti tōrunga. Kei te hanga noa tatou i te polynomial me te tohu , kei hea te whakarea kore utu - Ko to tatou ngaro tenei , mo ia o nga mea o muri mai kupu he taurangi pai kua tohua matapōkeretia. Mena ka hoki tatou ki te tauira taketake me te whakaaro , ka whiwhi tatou i te mahi .
I tenei wa ka taea e tatou te whakaputa kongakonga ma te hono tauoti ahurei i roto i te wahi (no te mea ko to tatou muna). I tenei tauira, e hiahia ana matou ki te tohatoha kia wha nga wahanga me te paepae o te toru, no reira ka whakaputa matapōkeretia e matou ka tuku i tetahi tohu ki ia tangata tokowha, ki nga kaitiaki o te ki. Ka whakamohio ano matou ki nga tangata , mai i te mea e kiia ana tenei ko nga korero a te iwi me te mea e tika ana mo te whakaora .
Te whakaora i te mea ngaro
Kua matapakihia e matou te ariā o te wawaotanga polynomial me te pehea o te whai i te kaupapa paepae a Shamir . Ina hiahia etahi o nga kaitiaki tokowha ki te whakaora , me whakauru noa ratou me ona ake tohu motuhake. Ki te mahi i tenei, ka taea e ratou te whakatau i o raatau tohu ka tātaihia te tauwaenga o Lagrange ma te whakamahi i te tauira e whai ake nei. Mēnā he mārama ake te hōtaka ki a koe i te pāngarau, ko te pi te tino kaiwhakahaere for
, e whakarea ana i nga hua katoa, me te sigma he for
, e taapiri ana i nga mea katoa.
i ka taea e tatou te whakaoti penei me te whakahoki i ta maatau mahi polynomial taketake:
No te mea e mohio ana tatou , whakaora mahia noa:
Te whakamahi tatau tauoti kore haumaru
Ahakoa kua pai te whakamahi i te whakaaro taketake a Shamir , ka mahue mai he raruraru kaore i arohia e matou tae noa ki tenei wa. Ka whakamahia e ta maatau mahi polynomial te tatauranga tauoti kore haumaru. Kia mahara, mo ia tohu taapiri ka riro i te kaitukino i runga i te kauwhata o ta maatau mahi, he iti ake nga waahi mo etahi atu tohu. Ka taea e koe te kite i tenei ma o kanohi ake ina tarai koe i te piki haere o nga tohu mo te mahi polynomial ma te whakamahi i te tatau tauoti. He kino tenei ki ta maatau whainga haumarutanga, na te mea me tino mohio te kaitukino kia tae ra ano ki a raatau kongakonga.
Hei whakaatu i te ngoikore o te iahiko tatau tauoti, whakaarohia he ahuatanga i whiwhi ai te kaitukino i nga tohu e rua. me te mohio ki nga korero a te iwi . Mai i enei korero ka taea e ia te whakatau , e rite ana ki te rua, ka whakauru i nga uara e mohiotia ana ki te tauira и .
Ka kitea e te kaitukino , tatau :
I te mea kua tautuhia e matou hei tauoti takatika kua tohua, he iti noa te maha ka taea . Ma te whakamahi i enei korero, ka taea e te kaiwhaiwhai te whakatau , no te mea he nui ake i te 5 ka mahi kino. Ka puta tenei ki te pono mai i ta maatau whakatau
Ka taea e te kaiwhaiwhai te tatau i nga uara ka taea whakakapi в :
Me te iti o nga whiringa mo ka marama te ngawari ki te kowhiri me te tirotiro i nga uara . E rima noa nga whiringa i konei.
Te whakaoti rapanga ma te tatau tauoti kore haumaru
Hei whakakore i tenei whakaraeraetanga, e kii ana a Shamir ki te whakamahi i te taurangi modular, whakakapi i runga i te wahi и — te huinga o nga tau pirimia katoa.
Kia hohoro te maumahara me pehea te mahi aritmetika modular. He karaka ringa he ariā taunga. Ka whakamahia e ia he mataaratanga . Ka pahemo te ringa haora i te tekau ma rua, ka hoki ki te kotahi. Ko tetahi mea whakamere o tenei punaha ko te titiro noa ki te karaka, kaore e taea te whakatau i te maha o nga hurihanga kua mahia e te ringaringa haora. Heoi, ki te mohio tatou kua pahemo te ringa haora i te 12 e wha nga wa, ka taea e tatou te whakatau i te maha o nga haora kua pahemo ma te whakamahi i tetahi tauira ngawari. te wahi ko to tatou wehewehe (i konei ), ko te whakarea (e hia nga wa ka uru te kaiwehewehe ki te tau taketake kaore he toenga, i konei ), me ko te toenga, ka hoki mai he waea kaiwhakahaere modulo (i konei ). Ma te mohio ki enei uara katoa ka taea e tatou te whakaoti i te wharite mo , engari ki te ngaro tatou i te whakarea, e kore rawa e taea te whakahoki mai i te uara taketake.
Ka taea e tatou te whakaatu me pehea te whakapai ake i te haumarutanga o ta maatau kaupapa ma te whakamahi i te kaupapa ki o taatau tauira o mua me te whakamahi . To tatou mahi polynomial hou , me nga tohu hou . Inaianei ka taea ano e nga kaitiaki matua te whakamahi i te wawaotanga polynomial ki te hanga ano i a maatau mahi, engari i tenei waa me whai tahi nga mahi taapiri me te whakareatanga me te whakaiti modulo. (hei tauira ).
Ma te whakamahi i tenei tauira hou, me whakaaro e rua o enei tohu hou i akohia e te tangata whakaeke, , me nga korero mo te iwi . I tenei wa, ko te kaiwhaiwhai, i runga i nga korero katoa kei a ia, ka whakaputa i nga mahi e whai ake nei, kei hea ko te huinga o nga tauoti takatika katoa, a e tohu ana i te whakareatanga modulus .
Inaianei kua kitea ano e to tatou kaitukino , tātai :
Na ka ngana ano ia whakakapi в :
I tenei wa he raru nui tana. Kua ngaro nga uara tātai , и . I te mea he maha nga huinga huinga o enei taurangi, kaore e taea e ia te whiwhi korero taapiri.
Nga Whakaaro Haumarutanga
Ko te kaupapa tiritiri ngaro a Shamir e kii ana haumarutanga mai i te tirohanga o te ariā korero. Ko te tikanga he atete te pangarau ahakoa ki te kaitukino me te mana rorohiko mutunga kore. Heoi, he maha tonu nga take e mohiotia ana e te ara iahiko.
Hei tauira, kaore te kaupapa a Shamir i hanga nga kongakonga kia tirohia, ara, ka taea e te tangata te whakaatu noa i nga kongakonga rūpahu me te pokanoa ki te whakaora i te mea ngaro tika. Ka taea e te kaipupuri kongakonga kino me te nui o nga korero ka whakaputa i tetahi atu kongakonga ma te huri i runga i to whakaaro. Ka whakatauhia tenei raru ma te whakamahi kaupapa tiritiri ngaro manatoko, penei i te kaupapa a Feldman.
Ko tetahi atu raruraru ko te roa o tetahi kongakonga he rite ki te roa o te mea ngaro e rite ana, na reira he ngawari te whakatau i te roa o te mea ngaro. Ka taea te whakaoti i tenei raruraru ma te iti noa whakapuru mea huna me nga nama noa ake ki te roa kua whakaritea.
Ka mutu, he mea nui kia mahara ko o tatou awangawanga haumaru ka toro atu ki tua atu o te hoahoa. Mo nga tono cryptographic o te ao, he maha tonu te riri o nga whakaeke taha-taha i reira ka ngana te kaitukino ki te tango korero whai hua mai i te wa mahi tono, te keteroki, nga tukinga, aha atu. Mēnā he āwangawanga tēnei, me āta whakaaro i te wā o te whakawhanaketanga ki te whakamahi i nga tikanga whakamarumaru penei i nga mahi me te tirotiro i nga wa tonu, te aukati i te mahara kia tiakina ki te kopae, me etahi atu whakaaro kei tua atu i te waahanga o tenei tuhinga.
Tauwehe
I roto i te
Source: will.com