Yi la'akari da yanayin inda kuke buƙatar amintaccen ajiyar banki. Ana ɗaukarsa gaba ɗaya maras cikawa ba tare da maɓalli ba, wanda aka ba ku a ranar farko ta aiki. Manufar ku ita ce adana maɓalli amintacce.
Bari mu ce kun yanke shawarar kiyaye maɓalli tare da ku koyaushe, samar da damar yin amfani da ma'ajiyar gwargwadon buƙata. Amma da sauri za ku gane cewa irin wannan mafita ba ta da kyau a aikace, saboda ana buƙatar kasancewar jikin ku a duk lokacin da kuka buɗe ajiyar. Me game da hutun da aka yi muku alkawari? Bugu da ƙari, tambayar ta fi ban tsoro: menene idan kun rasa maɓallin ku kawai?
Tare da hutun ku a zuciya, kun yanke shawarar yin kwafin maɓallin kuma ku ba da shi ga wani ma'aikaci. Koyaya, kun fahimci cewa wannan ma bai dace ba. Ta hanyar ninka adadin maɓallai, kuna kuma ninka damar satar maɓalli.
A cikin matsananciyar damuwa, kun lalata kwafin kuma yanke shawarar raba maɓallin asali cikin rabi. Yanzu, kuna tsammanin mutane biyu amintattu waɗanda ke da ɓangarorin maɓalli dole ne su kasance a zahiri don tattara maɓalli kuma su buɗe rumbun. Wannan yana nufin cewa barawo yana buƙatar sata guda biyu, wanda ya ninka satar maɓalli ɗaya sau biyu. Duk da haka, da sannu za ku gane cewa wannan makirci bai fi maɓalli ɗaya kyau ba, domin idan wani ya rasa rabin maɓalli, ba za a iya dawo da cikakken maɓalli ba.
Ana iya magance matsalar tare da jerin ƙarin maɓalli da makullai, amma wannan hanyar za ta buƙaci da sauri много makullai da makullai. Ka yanke shawarar cewa kyakkyawan tsari shine raba maɓallin don kada tsaro ya dogara ga mutum ɗaya gaba ɗaya. Har ila yau, kun kammala cewa dole ne a sami ɗan kofa don adadin guntuwar ta yadda idan guntu ɗaya ya ɓace (ko kuma idan mutum ya tafi hutu), maɓallan gaba ɗaya ya kasance yana aiki.
Yadda ake raba sirri
Adi Shamir ya yi tunani game da wannan nau'in mahimmin tsarin gudanarwa a cikin 1979 lokacin da ya buga aikinsa . Labarin a taƙaice yayi bayanin abin da ake kira 
tsarin kofa don rarraba ƙimar sirri da kyau (kamar maɓalli na ɓoye) zuwa cikin sassa. Sa'an nan, lokacin da kawai lokacin da akalla daga an tattara sassa, zaka iya dawo da sirri cikin sauƙi .
Ta fuskar tsaro, muhimmiyar kadara ta wannan makirci ita ce, kada wanda ya kai harin ya san komai da komai sai dai idan yana da akalla. sassa. Ko da kasancewar sassan kada su ba da wani bayani. Muna kiran wannan dukiya tsaro na ilimin fassara.
Interpolation na polynomial
Shamir ƙofa tsarin gina a kusa da ra'ayi polynomial interpolation. Idan ba ku saba da wannan ra'ayi ba, hakika abu ne mai sauƙi. A zahiri, idan kun taɓa zana maki akan jadawali sannan ku haɗa su da layi ko lanƙwasa, kun riga kun yi amfani da shi!
Ta hanyar maki biyu za ku iya zana adadi mara iyaka na polynomials na digiri 2. Don zaɓar ɗaya daga cikinsu, kuna buƙatar aya ta uku. Misali:
Yi la'akari da polynomial mai digiri na ɗaya, . Idan kuna son tsara wannan aikin akan jadawali, maki nawa kuke buƙata? To, mun san cewa wannan aikin layi ne wanda ke samar da layi don haka yana buƙatar akalla maki biyu. Na gaba, la'akari da aikin polynomial tare da digiri na biyu, . Wannan aikin hudu ne, don haka ana buƙatar akalla maki uku don tsara jadawali. Yaya game da polynomial mai digiri uku? Akalla maki hudu. Da sauransu da sauransu.
Babban abin da ke da kyau game da wannan kadara shine, idan aka ba da matakin aikin polynomial kuma aƙalla maki, za mu iya samun ƙarin maki don wannan aikin mai yawa. Muna kiran karin waɗannan ƙarin maki polynomial interpolation.
Ƙirƙirar sirri
Wataƙila ka riga ka gane cewa a nan ne dabarar wayo ta Shamir ta shiga. Mu fadi sirrin mu Shin . Za mu iya juya zuwa aya akan jadawali kuma fito da aikin polynomial tare da digiri , wanda ya gamsar da wannan batu. Mu tuna da haka zai zama bakin kofa na ɓangarorin da ake buƙata, don haka idan muka saita bakin kofa zuwa gaɓoɓin guda uku, dole ne mu zaɓi aikin ɗabi'a tare da digiri na biyu.
Polynomial ɗin mu zai sami sifa inda и - tabbataccen adadin da aka zaɓa ba da gangan ba. Muna kawai gina polynomial tare da digiri , inda free coefficient - Wannan shine sirrin mu , kuma ga kowane daga cikin na gaba Sharuɗɗan akwai ƙayyadaddun ƙididdiga masu inganci da aka zaɓa. Idan muka koma ga ainihin misali kuma mu ɗauka cewa , to muna samun aikin .
A wannan lokaci za mu iya samar da gutsuttsura ta hanyar haɗawa na musamman lamba a inda (domin sirrinmu ne). A cikin wannan misalin, muna so mu rarraba guntu guda huɗu tare da kofa na uku, don haka muna samar da maki ba da gangan ba. kuma a aika da aya ɗaya ga kowane amintattun mutane huɗu, masu kula da maɓalli. Mun kuma sanar da mutane da cewa , tun da ana la'akari da wannan bayanin jama'a kuma yana da mahimmanci don farfadowa .
Maida sirrin
Mun riga mun tattauna manufar interpolation polynomial da kuma yadda yake ƙarƙashin tsarin kofa na Shamir. . Lokacin da kowane uku daga cikin amintattu huɗu ke son maidowa , kawai suna buƙatar shiga tsakani tare da nasa maki na musamman. Don yin wannan, za su iya ƙayyade maki da lissafin Lagrange interpolation polynomial ta amfani da dabara mai zuwa. Idan shirye-shirye sun fi bayyana a gare ku fiye da lissafi, to pi ainihin ma'aikaci ne for, wanda ke ninka duk sakamakon, kuma sigma shine for, wanda ke ƙara komai.
a za mu iya warware shi kamar haka kuma mu dawo da ainihin aikin mu na polynomial:
Tunda mun san haka , farfadowa yi a sauƙaƙe:
Yin amfani da ƙididdiga marasa aminci
Ko da yake mun yi nasarar aiwatar da ainihin tunanin Shamir , an bar mu da matsalar da muka yi watsi da ita har yanzu. Ayyukan mu na al'ada yana amfani da ƙididdiga marasa aminci. Lura cewa ga kowane ƙarin maki da maharin ya samu akan jadawali na aikinmu, akwai ƙarancin yuwuwar wasu maki. Kuna iya ganin wannan da idanunku lokacin da kuke ƙirƙira adadin maki mai yawa don aikin ɗabi'a ta amfani da lissafin lamba. Wannan ya saba wa burinmu na tsaro da aka bayyana, domin maharin ya kamata ya san kwata-kwata har sai sun samu akalla. gutsuttsura.
Don nuna raunin da'irar lissafin ƙididdiga, la'akari da yanayin da maharin ya sami maki biyu. kuma ya san bayanan jama'a cewa . Daga wannan bayanin zai iya zana , daidai da biyu, kuma toshe a cikin sanannun dabi'u a cikin dabara и .
Wanda ya kai harin zai iya samun , kirgawa :
Tunda mun ayyana a matsayin intigers masu inganci da aka zaɓa ba da gangan, akwai iyakataccen adadin yuwuwar . Yin amfani da wannan bayanin, mai kai hari zai iya ganowa , tunda duk abin da ya fi 5 zai yi korau. Wannan ya zama gaskiya tunda mun ƙaddara
Daga nan maharin zai iya ƙididdige ƙididdiga masu yiwuwa maye gurbin в :
Tare da iyakatattun zaɓuɓɓuka don ya bayyana a sarari yadda sauƙin zaɓi da duba ƙimar . Akwai zaɓuɓɓuka guda biyar kawai a nan.
Magance matsalar tare da ƙididdiga marasa aminci
Don kawar da wannan raunin, Shamir ya ba da shawarar yin amfani da lissafi na zamani, maye gurbin a kan inda и - saitin duk manyan lambobi.
Mu tuna da sauri yadda tsarin lissafi na zamani ke aiki. Agogo mai hannaye sanannen ra'ayi ne. Tana amfani da agogon wato . Da zarar hannun sa'a ya wuce sha biyu, sai ya koma daya. Wani abu mai ban sha'awa na wannan tsarin shine kawai ta hanyar kallon agogo, ba za mu iya tantance yawan juyi da hannun sa'a ya yi ba. Duk da haka, idan mun san cewa hannun sa'a ya wuce sau 12 sau hudu, za mu iya ƙayyade adadin sa'o'in da suka wuce ta amfani da tsari mai sauƙi. inda shine mai raba mu (nan ), shine ma'auni (sau nawa mai rarraba ya shiga lambar asali ba tare da saura ba, a nan ), da shi ne saura, wanda yawanci ke mayar da kiran ma'aikacin modulo (a nan ). Sanin duk waɗannan dabi'u yana ba mu damar warware lissafin don , amma idan muka rasa ƙididdiga, ba za mu taɓa iya dawo da ƙimar asali ba.
Za mu iya nuna yadda wannan ke inganta tsaro na makircinmu ta amfani da tsarin zuwa misalinmu na baya da kuma amfani da shi . Sabon aikin mu mai yawa , da sabbin maki . Yanzu masu kula da maɓalli na iya sake yin amfani da haɗin gwiwar polynomial don sake gina aikinmu, kawai a wannan lokacin ƙari da haɓaka ayyukan dole ne su kasance tare da rage modulo. (misali ).
Yin amfani da wannan sabon misali, bari mu ɗauka cewa maharin ya koyi biyu daga cikin waɗannan sabbin abubuwa, , da kuma bayanan jama'a . A wannan karon, maharin, bisa ga dukkan bayanan da yake da su, ya fitar da ayyuka masu zuwa, inda shine saitin duk intigers masu kyau, kuma yana wakiltar ma'aunin modules .
Yanzu maharin namu ya sake ganowa , lissafi :
Sannan ya sake gwadawa maye gurbin в :
A wannan karon yana da babbar matsala. Ƙimar da ta ɓace , и . Tun da akwai adadi mara iyaka na haɗuwa na waɗannan masu canji, ba zai iya samun ƙarin bayani ba.
La'akarin Tsaro
Shirin raba sirrin Shamir ya nuna tsaro daga mahangar ka'idar bayanai. Wannan yana nufin cewa lissafin yana da juriya ko da a kan maharin da ke da ikon sarrafa kwamfuta mara iyaka. Koyaya, da'irar har yanzu tana ƙunshe da sanannun batutuwa da yawa.
Misali, makircin Shamir ba ya halitta gutsattsarin da za a duba, wato, mutane na iya gabatar da ɓangarorin karya kuma su tsoma baki tare da dawo da ainihin sirrin. Maƙiyin guntu mai ƙiyayya tare da isassun bayanai na iya haifar da wani guntu ta hanyar canzawa bisa ga ra'ayinka. Ana magance wannan matsalar ta amfani da ingantaccen tsarin raba sirri, irin su makircin Feldman.
Wata matsala kuma ita ce tsayin kowane guntu yana daidai da tsawon sirrin da ya dace, don haka tsawon sirrin yana da sauƙin tantancewa. Ana iya magance wannan matsala ta hanyar banza padding asiri tare da lambobi na sabani har zuwa tsayayyen tsayi.
A ƙarshe, yana da mahimmanci a lura cewa damuwarmu ta tsaro na iya wucewa fiye da ƙirar kanta. Don aikace-aikacen sirrin sirri na zahiri, galibi ana samun barazanar hare-haren tasha ta gefe inda maharin ke ƙoƙarin fitar da bayanai masu amfani daga lokacin aiwatar da aikace-aikacen, caching, faɗuwa, da sauransu. Idan wannan abin damuwa ne, ya kamata a yi la'akari da hankali yayin ci gaba don amfani da matakan kariya kamar ayyuka da duban lokaci akai-akai, hana ƙwaƙwalwar ajiya daga adanawa zuwa faifai, da kuma wasu la'akari da yawa waɗanda suka wuce iyakar wannan labarin.
Demo
a kan Akwai nunin mu'amala na makircin raba sirrin Shamir. Zanga-zangar bisa laburare , wanda ita kanta tashar JavaScript ce ta shahararren shirin . Lura cewa ƙididdige ƙididdiga masu girma , и na iya ɗaukar lokaci.
source: www.habr.com