Senaryoyek ku hûn hewce ne ku kasa bankek ewleh bikin bifikirin. Ew bêyî mifteyê ku di roja yekem a xebatê de tê dayîn, bêkêmasî tê hesibandin. Armanca we ew e ku hûn mifteyê bi ewlehî hilînin.
Ka em bibêjin hûn biryar didin ku hûn her gav mifteyê bi xwe re bihêlin, li gorî hewcedariyê gihîştina hilanînê peyda bikin. Lê hûn ê zû fam bikin ku çareseriyek wusa di pratîkê de baş nayê pîvandin, ji ber ku her gava ku hûn hilanînê vedikin hebûna weya laşî hewce ye. Li ser betlaneya ku we soz dabû? Wekî din, pirs hê bêtir tirsnak e: heke we mifteya xweya yekane winda bike çi dibe?
Di hişê betlaneya xwe de, hûn biryar didin ku hûn kopiyek mifteyê çêbikin û wê bispêrin karmendek din. Lêbelê, hûn fêm dikin ku ev jî ne îdeal e. Bi ducarkirina hejmara kilîtan, hûn jî şansê dizîna mifteyê ducar dikin.
Di bêhêvîtiyê de, hûn dubareyê hilweşînin û biryar didin ku mifteya orîjînal di nîvê de parçe bikin. Naha, hûn ê bifikirin ku du mirovên pêbawer ên bi perçeyên sereke divê bi fizîkî amade bin da ku mifteyê berhev bikin û kavilê vekin. Ev tê wê wateyê ku dizek pêdivî ye ku du perçeyan dizîne, ku du caran ji dizîna yek key dijwartir e. Lêbelê, hûn zû pê dihesin ku ev nexşe ji yek mifteyê ne pir çêtir e, ji ber ku heke kesek nîv mifteyê winda bike, mifteya tevahî nayê vegerandin.
Pirsgirêk dikare bi rêzek kilît û kilîdên zêde were çareser kirin, lê ev nêzîkatî dê zû hewce bike много kilît û qefle. Hûn biryar didin ku sêwirana îdeal dê parvekirina mifteyê be da ku ewlehî bi tevahî li ser yek kesî nemîne. Di heman demê de hûn vê encamê didin ku divê ji bo hejmara perçeyan hin bendek hebe da ku heke perçeyek wenda bibe (an ger kesek biçe betlaneyê), kilît tevahî fonksiyonel bimîne.
Meriv çawa razek parve dike
Adî Şamir di sala 1979'an de dema ku xebatên xwe weşand, ev cure plansaziya rêveberiya sereke hate fikirîn . Gotar bi kurtî rave dike ku tê gotin 
pilana tixûbê ji bo dabeşkirina bi bandor a nirxek veşartî (wek mifteya krîptografî) nav de 
parçeyên. Wê demê, kengê û tenê dema ku bi kêmanî 
ji 
parçe têne civandin, hûn dikarin bi hêsanî sirê vegerînin 
.
Ji hêla ewlehiyê ve, taybetmendiyek girîng a vê planê ev e ku êrîşkar divê bi tevahî tiştek nizanibe heya ku bi kêmanî hebe. 
parçeyên. Heta hebûna 
beşên divê tu agahî ne. Em ji vê milkê re dibêjin ewlehiya semantîk.
Interpolation polynomial
Plana sînorê Şamir 
li dora konseptê hatiye avakirin interpolation polynomial. Heke hûn bi vê têgehê nizanin, ew bi rastî pir hêsan e. Bi rastî, heke we çu carî xalên li ser grafîkê xêz kirin û dûv re wan bi xêz an kêşan ve girêda, we berê wê bikar aniye!
Bi rêya du xalan hûn dikarin hejmareke bêsînor a pirnomîlên pileya 2 bikşînin. Ji bo ku yek ji wan hilbijêrin, hûn xalek sêyemîn hewce ne. Xetkirî:
Pirnomîlek bi dereceya yekê bihesibînin, 
. Ger hûn bixwazin vê fonksiyonê li ser grafekê binivîsin, çend xal ji we re lazim in? Welê, em dizanin ku ev fonksiyonek xêzek e ku xêzek çêdike û ji ber vê yekê herî kêm du xal hewce dike. Dûv re, fonksiyonek pirnomî ya bi pileya duyan bihesibînin, 
. Ev fonksiyonek çargoşe ye, ji ber vê yekê bi kêmî ve sê xal hewce ne ku grafiyê çêbikin. Çawa li ser pirnomîlek bi pileya sê? Bi kêmanî çar xal. Û filan û bêvan.
Tişta bi rastî xweş di derbarê vê taybetmendiyê de ev e ku, ji asta fonksiyona pirnomîal û bi kêmî ve 
xalan, em dikarin xalên zêde ji bo vê fonksiyona pirnomial derxînin. Em ji van xalên zêde re dibêjin ekstrapolasyon interpolation polynomial.
Çêkirina sirekî
Dibe ku we jixwe fêm kiribe ku li vir pîlana biaqil a Şamir derdikeve pêş. Em sira xwe bêjin 
Ye 
. Em dikarin bizivirin 
bi xalek li ser grafiyê 
û bi derece fonksiyonek pirnomîal derxe holê 
, ku vê xalê têr dike. Ka em vê yekê bînin bîra xwe 
dê bendeya me ya perçeyên pêwîst be, ji ber vê yekê heke em bendeyê deynin ser sê perçeyan, divê em fonksiyonek polînomî ya bi pileya duyemîn hilbijêrin.
Pirnomîka me dê xwedî form be 
ko 
и 
- jimareyên erênî yên rasthatî hatine hilbijartin. Em tenê pirnomîlek bi derece ava dikin 
, Li ku derê rêjeya belaş 
- Ev sira me ye 
, û ji bo her yek ji yên paşîn 
şert û mercên bi korfelaqî hilbijartî ya erênî heye. Ger em vegerin ser mînaka eslî û wisa bihesibînin 
, paşê em fonksiyonê bistînin 
.
Di vê xalê de em dikarin bi girêdanê perçeyan çêbikin 
hejmarên yekta di nav de 
ko 
(ji ber ku ew sira me ye). Di vê nimûneyê de, em dixwazin çar perçeyên bi berdêla sêyan belav bikin, ji ber vê yekê em bi rasthatinî xalan çêdikin. 
û ji her çar kesên pêbawer, parêzgerên mifteyê re xalek bişîne. Em jî vê yekê ji gel re didin zanîn 
, ji ber ku ev agahdariya gelemperî tête hesibandin û ji bo başbûnê hewce ye 
.
Vegerandina sirê
Me berê jî li ser têgeha navberkirina pirnomî û çawa ew di binê pilana sînorê Şamir de ye nîqaş kir. 
. Gava ku ji çar pêbaweran yek sêyek bixwaze vegere 
, ew tenê hewce ne ku navber bikin 
bi xalên xwe yên yekta. Ji bo vê yekê, ew dikarin xalên xwe diyar bikin 
û bi formula jêrîn pirnomîleya interpolasyona Lagrange bihejmêre. Ger bername ji we re ji matematîkê zelaltir e, wê hingê pi bi bingehîn operatorek e for, ku hemî encaman zêde dike, û sigma ye for, ku her tiştî zêde dike.
de hate 
em dikarin bi vî rengî çareser bikin û fonksiyona xweya pirnomî ya orîjînal vegerînin:
Ji ber ku em dizanin 
, başbûn 
bi hêsanî kirin:
Bikaranîna jimareya jimareya ne ewledar
Tevî ku me fikra bingehîn a Şamîr bi serkeftî bi cih anî 
, em bi pirsgirêkek ku heya nuha me paşguh kiriye re mane. Fonksiyona meya polînomîal arîtmetîka jimareke neewle bikar tîne. Bala xwe bidinê ku ji bo her xalek zêde ku êrîşkar li ser grafika fonksiyona me bi dest dixe, ji bo xalên din kêmtir îmkan hene. Hûn dikarin vê yekê bi çavên xwe bibînin dema ku hûn hejmareke zêde xalan ji bo fonksiyonek pirnomîal bi karanîna jimareya yekjimar xêz dikin. Ev ji armanca me ya ewlehiyê ya diyarkirî re berevajî ye, ji ber ku êrîşkar divê bi tevahî tiştek nezane heya ku kêmasî hebe 
perçeyên.
Ji bo ku nîşan bidin ka qelsiya jimareya bêkêmasî çiqas qels e, senaryoyek ku tê de êrîşkar du xal bi dest xistiye binêre. 
û agahdariya gelemperî dizane ku 
. Ji van agahiyan ew dikare derbikeve 
, du wekhev e, û nirxên naskirî têxin nav formula 
и 
.
Wê demê êrîşkar dikare bibîne 
, jimartin 
:
Ji ber ku me diyar kiriye 
wekî jimareyên erênî yên bi rasthatinî hatine hilbijartin, hejmareke bisînor a gengaz hene 
. Bi karanîna vê agahiyê, êrîşkar dikare derxîne 
, ji ber ku tiştek ji 5 mezintir dê bike 
nebaş. Ji ber ku me biryar daye ev rast derdikeve holê 
Dûv re êrîşkar dikare nirxên gengaz hesab bike 
, li şûna 
в 
:
Bi vebijarkên sînorkirî ji bo 
Ew eşkere dibe ku ew çiqas hêsan e ku nirxan hilbijêrin û kontrol bikin 
. Li vir tenê pênc vebijark hene.
Çareserkirina pirsgirêkê bi jimareya jimareya ne ewledar
Ji bo rakirina vê lawaziyê, Shamir pêşniyar dike ku bi karanîna arithmetîka modular, li şûna xwe bikar bînin 
li ser 
ko 
и 
- komek ji hemû hejmarên yekem.
Werin em zû bi bîr bînin ka arîtmetîka modular çawa dixebite. Saetek bi destan têgehek naskirî ye. Ew demjimêrek bikar tîne ku ew e 
. Hema ku jimareya saetê diwanzdeh derbas dibe, vedigere yekî. Taybetmendiyek balkêş a vê pergalê ew e ku bi tenê bi lênihêrîna demjimêrê, em nikanin têbikoşin ka saetê çend şoreş çêkiriye. Lêbelê, heke em zanibin ku destana saetê 12 çar caran derbas bûye, em dikarin bi formulayek hêsan hejmara demjimêrên ku derbas bûne bi tevahî destnîşan bikin. 
ko 
dabeşkerê me ye (li vir 
), 
jimare ye (çiqas caran dabeşker bêyî mayî diçe nav hejmara eslî, li vir 
), û 
mayî ye, ku bi gelemperî bangek operatorê modulo vedigerîne (li vir 
). Zanîna van hemî nirxan dihêle ku em hevkêşeyê çareser bikin 
, lê heke em hevberê ji dest bidin, em ê çu carî nikaribin nirxa orîjînal vegerînin.
Em dikarin destnîşan bikin ka ev çawa ewlehiya pilana me bi sepandina nexşeyê li mînaka xweya berê û karanîna 
. Fonksiyona meya polînomî ya nû 
, û xalên nû 
. Naha parêzvanên sereke dikarin careke din interpolasyona polînomîal bikar bînin da ku fonksiyona me ji nû ve ava bikin, tenê vê carê divê operasyonên zêdekirin û pirjimarkirinê bi kêmkirina modulê re werin 
(mînak 
).
Bi karanîna vê mînaka nû, em bihesibînin ku êrîşkar du ji van xalên nû fêr bûne, 
, û agahdariya gelemperî 
. Vê carê, êrîşkar, li ser bingeha hemî agahdariya ku wî heye, fonksiyonên jêrîn derdixe, li ku derê 
komek ji hemû hejmarên erênî ye, û 
rêjeya modulusê nîşan dide 
.
Niha êrîşkarê me dîsa dibîne 
, hesabkirin 
:
Piştre ew dîsa hewl dide 
, li şûna 
в 
:
Vê carê pirsgirêkek wî ya giran heye. Formula nirxên wenda 
, 
и 
. Ji ber ku hejmareke bêdawî ya berhevokên van guherbaran hene, ew nikare agahdariya zêde bi dest bixe.
Fikrên Ewlekariyê
Plana parvekirina veşartî ya Shamir pêşniyar dike ewlekarî ji nêrîna teoriya agahdariyê. Ev tê vê wateyê ku matematîk li hember êrîşkerek bi hêza hesabker a bêsînor jî berxwedêr e. Lêbelê, dor hê jî çend pirsgirêkên naskirî dihewîne.
Mînak şêla Şamîr naafirîne parçeyên ku bêne kontrol kirin, yanî mirov dikare bi serbestî perçeyên sexte pêşkêş bike û destwerdana vegerandina raza rast bike. Xwediyê parçeyek dijmin bi agahdariya têr dikaribû bi guheztinê perçeyek din jî çêbike 
li gor dilê xwe. Ev pirsgirêk bi kar tê çareser kirin nexşeyên parvekirina veşartî yên verastkirî, wek plana Feldman.
Pirsgirêkek din jî ev e ku dirêjahiya her perçeyek bi dirêjahiya raza têkildar re wekhev e, ji ber vê yekê dirêjahiya veşartî hêsan e ku were destnîşankirin. Ev pirsgirêk dikare bi kêmasî çareser bibe padding veşartî bi hejmarên keyfî heta bi dirêjahiya sabît.
Di dawiyê de, girîng e ku em bala xwe bidinê ku fikarên me yên ewlehiyê dibe ku ji sêwiranê wêdetir bibin. Ji bo serîlêdanên krîptografî yên cîhana rastîn, bi gelemperî xetera êrişên kanala alîgir heye ku êrîşkar hewl dide ku agahdariya kêrhatî ji dema pêkanîna serîlêdanê derxe, caching, têkçûn, hwd. Ger ev fikar be, divê di dema pêşkeftinê de bi baldarî li ser karanîna tedbîrên parastinê yên wekî fonksiyonan û lêgerînên dema domdar, nehiştina bîranînê li ser dîskê were hilanîn, û jimarek ramanên din ên ku li derveyî çarçoweya vê gotarê ne.
Demo
li ser Xwepêşandanek înteraktîf a plana parvekirina veşartî ya Shamir heye. Xwepêşandan li ser bingeha pirtûkxaneyê , ku bi xwe portek JavaScript ya bernameya populer e . Hişyar bikin ku nirxên mezin têne hesibandin 
, 
и 
dibe ku hinek dem bigire.
Source: www.habr.com
