Smaoinigh ar chás inar gá duit cruinneachán bainc a dhaingniú. Meastar go bhfuil sé dothuigthe gan eochair, a thugtar duit ar an gcéad lá oibre. Is é do sprioc an eochair a stóráil go sábháilte.

Ligean le rá go gcinnfidh tú an eochair a choinneáil leat i gcónaí, ag soláthar rochtain ar an stóráil de réir mar is gá. Ach tuigfidh tú go tapa nach ndéanann réiteach den sórt sin scála maith go praiticiúil, toisc go bhfuil gá le do láithreacht fhisiceach gach uair a osclaíonn tú an stóráil. Cad mar gheall ar na laethanta saoire a gealladh duit? Ina theannta sin, tá an cheist níos scanrúla fós: cad a tharlaíonn má chaill tú do eochair amháin?

Agus do laethanta saoire san áireamh, socraíonn tú cóip den eochair a dhéanamh agus é a chur ar iontaoibh fostaí eile. Mar sin féin, tuigeann tú nach bhfuil sé seo oiriúnach ach an oiread. Trí líon na n-eochracha a dhúbailt, déanann tú an seans go ngoidfear eochair a dhúbailt freisin.

In éadóchas, scriosann tú an dúblach agus socraíonn tú an eochair bhunaidh a roinnt ina dhá leath. Anois, shílfeá go gcaithfeadh beirt daoine iontaofa le blúirí tábhachtacha a bheith i láthair go fisiciúil chun an eochair a bhailiú agus an cruinneachán a oscailt. Ciallaíonn sé seo go gcaithfidh gadaí dhá phíosa a ghoid, atá dhá uair chomh deacair le heochair amháin a ghoid. Mar sin féin, tuigeann tú go luath nach bhfuil an scéim seo i bhfad níos fearr ná eochair amháin, mar má chailleann duine leath eochair, ní féidir an eochair iomlán a fháil ar ais.

Is féidir an fhadhb a réiteach le sraith eochracha agus glais bhreise, ach beidh an cur chuige seo ag teastáil go tapa много eochracha agus glais. Socraíonn tú gurb é an dearadh idéalach ná an eochair a roinnt ionas nach mbeidh an tslándáil ag brath go hiomlán ar dhuine amháin. Tá sé de thátal agat freisin go gcaithfidh tairseach éigin a bheith ann do líon na blúirí ionas go bhfanann an eochair iomlán feidhmiúil má chailltear blúire amháin (nó má théann duine ar saoire).

Conas a rún a roinnt

Rinne Adi Shamir machnamh ar an gcineál seo príomhscéim bhainistíochta i 1979 nuair a d’fhoilsigh sé a shaothar "Conas Rún a Roinn". Míníonn an t-alt go hachomair mar a thugtar air scéim tairsí chun luach rúnda (amhail eochair chripteagrafach) a roinnt go héifeachtach páirteanna. Ansin, cathain agus gan ach nuair ar a laghad de páirteanna atá le chéile, is féidir leat a chur ar ais go héasca ar an rún .

Ó thaobh na slándála de, ar mhaoin thábhachtach den scéim seo ná nár cheart go mbeadh a fhios ag an ionsaitheoir rud ar bith mura bhfuil ar a laghad aige. páirteanna. Fiú an láithreacht níor cheart go gcuirfeadh páirteanna aon fhaisnéis ar fáil. Tugaimid an mhaoin seo slándáil shéimeantach.

Idirshuíomh polynomial

Scéim tairsí Shamir tógtha timpeall ar an gcoincheap idirshuíomh iltéarmach. Mura bhfuil tú eolach ar an gcoincheap seo, tá sé simplí go leor. Déanta na fírinne, má tharraing tú pointí ar ghraf riamh agus má cheangail tú iad le línte nó cuair, d'úsáid tú cheana é!

Trí dhá phointe is féidir leat líon neamhtheoranta iltéarmaí de chéim 2 a tharraingt. Chun an t-aon cheann a roghnú uathu, beidh tríú pointe ag teastáil uait. Léiriú: Wikipedia

Smaoinigh ar polynomial le céim a haon, . Más mian leat an fheidhm seo a bhreacadh ar ghraf, cé mhéad pointe atá uait? Bhuel, tá a fhios againn gur feidhm líneach é seo a fhoirmíonn líne agus mar sin tá dhá phointe ar a laghad ag teastáil uaidh. Ansin, smaoinigh ar fheidhm iltéarmach le céim a dó, . Feidhm chearnach í seo, mar sin tá trí phointe ar a laghad ag teastáil chun an graf a bhreacadh. Cad mar gheall ar iltéarmach le céim a trí? Ar a laghad ceithre phointe. Agus mar sin de agus mar sin de.

Is é an rud fíor-fhionnuar faoin maoin seo ná, mar gheall ar mhéid na feidhme iltéarmaí agus ar a laghad pointí, is féidir linn pointí breise a dhíorthú don fheidhm iltéarmach seo. Glaoimid ar eachtarshuíomh na bpointí breise seo idirshuíomh iltéarmach.

Rún a dhéanamh suas

B'fhéidir gur thuig tú cheana féin gurb é seo an áit a dtagann scéim chliste Shamir i bhfeidhm. A ligean ar a rá ár rún - An bhfuil . Is féidir linn casadh go pointe ar an ngraf agus teacht suas le feidhm iltéarmach le céim , a shásaíonn an pointe seo. Cuirfimid é sin i gcuimhne duit Beidh ár dtairseach de blúirí riachtanacha, mar sin má leagaimid an tairseach go dtí trí blúirí, ní mór dúinn a roghnú feidhm iltéarmach le céim a dó.

Beidh an fhoirm ag ár polynomial I gcás ina и — slánuimhreacha dearfacha a roghnaítear go randamach. Nílimid ach ag tógáil iltéarmach le céim , áit a bhfuil an chomhéifeacht saor in aisce  - Is é seo ár rún , agus do gach ceann de na cinn ina dhiaidh sin téarmaí tá comhéifeacht dhearfach roghnaithe go randamach. Má fhilleann muid ar an sampla bunaidh agus glacadh leis go , ansin faigheann muid an fheidhm .

Ag an bpointe seo is féidir linn blúirí a ghiniúint trí nascadh slánuimhreacha uathúla i I gcás ina (toisc go bhfuil sé ar ár rún). Sa sampla seo, ba mhaith linn ceithre blúirí a dháileadh le tairseach trí, agus mar sin ginimid pointí go randamach agus pointe amháin a chur chuig gach ceann de na ceithre daoine iontaofa, caomhnóirí an eochair. Cuirimid é sin in iúl do dhaoine freisin , ós rud é go meastar gur faisnéis phoiblí é seo agus go bhfuil sé riachtanach chun é a ghnóthú .

An rún a aisghabháil

Tá coincheap an idirshuímh iltéarmaigh pléite againn cheana féin agus an chaoi a bhfuil sé mar bhunús le scéim tairsí Shamir . Nuair is mian le haon triúr den cheathrar iontaobhaithe a chur ar ais , ní gá dóibh ach idirshuí a dhéanamh lena pointí uathúla féin. Chun seo a dhéanamh, is féidir leo a gcuid pointí a chinneadh agus ríomh iltéarmach idirshuímh Lagrange ag baint úsáide as an bhfoirmle seo a leanas. Má tá an ríomhchlárú níos soiléire duit ná an mhatamaitic, is oibreoir é pi go bunúsach for, a iolraíonn na torthaí go léir, agus tá sigma for, a chuireann gach rud suas.

Ag is féidir linn é a réiteach mar seo agus ár mbunfheidhm iltéarmach a thabhairt ar ais:

Ós rud é go bhfuil a fhios againn go , aisghabháil déanta go simplí:

Ag baint úsáide as uimhríocht slánuimhir neamhshábháilte

Cé gur éirigh linn bunsmaoineamh Shamir a chur i bhfeidhm , táimid fágtha le fadhb ar thugamar neamhaird di go dtí seo. Úsáideann ár bhfeidhm iltéarmach uimhríocht slánuimhir neamhshábháilte. Tabhair faoi deara, le haghaidh gach pointe breise a fhaigheann ionsaitheoir ar ghraf ár bhfeidhme, go bhfuil níos lú féidearthachtaí ann do phointí eile. Is féidir é seo a fheiceáil le do shúile féin nuair a bhreacann tú líon méadaitheach pointí le haghaidh feidhm iltéarmach ag baint úsáide as uimhríocht slánuimhir. Tá sé seo friththáirgiúil dár sprioc slándála luaite, mar níor cheart go mbeadh a fhios ag an ionsaitheoir rud ar bith go dtí go mbeidh ar a laghad acu é blúirí.

Chun a léiriú cé chomh lag is atá an ciorcad uimhríochtúil slánuimhir, smaoinigh ar chás ina bhfuair ionsaitheoir dhá phointe agus tá a fhios aige faisnéis phoiblí go . Ón eolas seo is féidir leis a bhaint as , comhionann le dhá, agus cuir isteach na luachanna aitheanta isteach san fhoirmle и .

Is féidir leis an ionsaitheoir a fháil ansin , comhaireamh :

Ós rud é go bhfuil sainithe againn mar shlánuimhreacha dearfacha a roghnaíodh go randamach, tá líon teoranta féidearthachtaí ann . Ag baint úsáide as an eolas seo, is féidir ionsaitheoir a asbhaint , toisc go ndéanfaidh aon rud níos mó ná 5 diúltach. Tarlaíonn sé seo a bheith fíor ó chinneamar

Is féidir leis an ionsaitheoir na luachanna féideartha a ríomh ansin , ag cur in ionad в :

Le roghanna teoranta le haghaidh bíonn sé soiléir cé chomh héasca agus atá sé na luachanna a roghnú agus a sheiceáil . Níl ach cúig rogha anseo.

An fhadhb a réiteach le huimhríocht slánuimhir neamhshábháilte

Chun deireadh a chur leis an leochaileacht seo, molann Shamir úsáid a bhaint as uimhríocht modúlach, athsholáthar ar I gcás ina и — sraith na bpríomhuimhreacha go léir.

Déanaimis cuimhneamh go tapa ar conas a oibríonn uimhríocht mhodúlach. Is coincheap eolach é clog leis na lámha. Úsáideann sí uaireadóir .i . Chomh luath agus a théann an lámh uair a dó dhéag, filleann sé ar cheann amháin. Airíonna spéisiúla den chóras seo ná go simplí trí bhreathnú ar an gclog, ní féidir linn a bhaint amach cé mhéad réabhlóidí a rinne an uair an chloig. Mar sin féin, má tá a fhios againn go bhfuil an lámh uair an chloig caite 12 ceithre huaire, is féidir linn a chinneadh go hiomlán ar líon na n-uaireanta a rith ag baint úsáide as foirmle simplí I gcás ina  is é ár rannóir (anseo ),  is é an chomhéifeacht (cé mhéad uair a théann an roinnteoir isteach sa bhunuimhir gan fuílleach, anseo ), agus  an chuid eile, a sheolann glao oibreora modúil ar ais de ghnáth (anseo ). Ós eol dúinn na luachanna seo go léir is féidir linn an chothromóid a réiteach le haghaidh , ach má chailleann muid an comhéifeacht, ní bheidh muid in ann a chur ar ais ar an luach bunaidh.

Is féidir linn a léiriú conas a fheabhsaíonn sé seo slándáil ár scéime tríd an scéim a chur i bhfeidhm ar ár sampla roimhe seo agus trí úsáid a bhaint as . Ár bhfeidhm iltéarmach nua , agus na pointí nua . Anois is féidir leis na príomhchoimeádaithe idirshuíomh iltéarmach a úsáid arís chun ár bhfeidhm a athchruthú, ach an uair seo ní mór laghdú modúil a bheith ag gabháil leis na hoibríochtaí suimithe agus iolraithe. (m.sh. ).

Agus an sampla nua seo á úsáid agat, glacaimis leis gur fhoghlaim an t-ionsaitheoir dhá cheann de na pointí nua seo, , agus faisnéis phoiblí . An uair seo, cuireann an t-ionsaitheoir, bunaithe ar an bhfaisnéis go léir atá aige, na feidhmeanna seo a leanas amach, áit  is é an tacar de gach slánuimhir dearfach, agus seasann sé don chomhéifeacht modulus .

Anois aimsíonn ár n-ionsaitheoir arís , ag ríomh :

Ansin déanann sé iarracht arís , ag cur in ionad в :

An uair seo tá fadhb thromchúiseach aige. Foirmle luachanna in easnamh , и . Ós rud é go bhfuil líon gan teorainn de na teaglaim de na hathróga seo, ní féidir leis a fháil ar aon fhaisnéis bhreise.

Cúrsaí Slándála

Molann scéim rúnda roinnte Shamir slándáil ó thaobh teoiric na faisnéise. Ciallaíonn sé seo go bhfuil an mhatamaitic resistant fiú i gcoinne ionsaitheoir le cumhacht ríomhaireachta gan teorainn. Mar sin féin, tá roinnt saincheisteanna aitheanta fós sa chiorcad.

Mar shampla, ní chruthaíonn scéim Shamir blúirí a sheiceáil, is é sin, is féidir le daoine blúirí falsa a chur i láthair faoi shaoirse agus cur isteach ar aisghabháil an rún ceart. D'fhéadfadh coimeádaí blúire naimhdeach le faisnéis leordhóthanach blúire eile a tháirgeadh fiú trí athrú a dhéanamh de do rogha féin. Tá an fhadhb a réiteach ag baint úsáide as scéimeanna comhroinnte rúnda infhíoraithe, mar shampla scéim Feldman.

Fadhb eile ná go bhfuil fad aon bhlúire comhionann le fad an rún comhfhreagrach, agus mar sin is furasta fad an rún a chinneadh. Is féidir an fhadhb seo a réiteach trí fhánach stuáil rún le huimhreacha treallach suas le fad seasta.

Ar deireadh, tá sé tábhachtach a thabhairt faoi deara go bhféadfadh ár n-imní slándála dul thar an dearadh féin. I gcás feidhmchláir chripteagrafacha sa saol fíor, is minic a bhíonn bagairt ar ionsaithe taobh-chainéil nuair a dhéanann ionsaitheoir iarracht faisnéis úsáideach a bhaint as am forghníomhaithe feidhmchlár, taisceadh, tuairteanna, etc. Más ábhar imní é seo, ba cheart breithniú cúramach a dhéanamh le linn na forbartha ar úsáid a bhaint as bearta cosanta amhail feidhmeanna agus cuardaigh ama seasta, chun cuimhne a chosc ó shábháil ar diosca, agus roinnt cúinsí eile atá lasmuigh de raon feidhme an ailt seo.

Taispeántas

Ar an leathanach seo Tá léiriú idirghníomhach ar scéim rúnda roinnte Shamir. Taispeántas bunaithe ar an leabharlann ssss-js, atá ina phort JavaScript féin den chlár tóir bbbb. Tabhair faoi deara go bhfuil luachanna móra á ríomh , и féadfaidh sé tamall a thógáil.

Foinse: will.com