
vann-vae function

computer sainslo, vann-vae function anedi prati inputpai lekkinchadam sulabham, conny yaadruchchika input yokka chitraanni batti vilomam cheyadam kashtam. ikkada, "sulabham" mariyu "kashtam" anevi ganana sanklishtata siddhaantam, mukhyamgaa bahupadi samaya samasyala siddhaantam anae ardhamlo ardham chesukovali. oka function nuu vann-vae anie pilavadaaniki okariki okaru kakapovadam saripodani bhaavistaaru (krinda saiddhaantika nirvachanam chudandi).
atuvanti yeka-maargam vidhula uniki ippatikee bahiranga ooha. vaati uniki sanklishtata taragatulu p mariyu np samanamga levani rujuvu chestundi, tadwara saiddhaantika computer sains yokka mottamodati parishkarinchani prasnanu parishkaristundi. dheeniki viruddhamgaa nijam anie teliyadu, i.ii. p ≤np anedi vann-vae functionla unikini neerugaa suuchimchadani rujuvu uniki.
anuvartita sandarbhaalalo, "sulabham" mariyu "kathinamainadi" anae padaalu saadhaaranamgaa konni nirdishta computing samsthalaku sambandhinchi ardham chesukobadatayi; saadhaaranamgaa "chattabaddhamaina viniyogadaarulaku taginanta choukainavi" mariyu "edainaa haanikaramaina agentlaku nishedhinchadagina khareedainavi". eee konamlo, yeka-maargam vidhulu, guudha lipi shaastram, vyaktigata gurtimpu, praamaaneekarana mariyu itara dayta bhadrata anuvartanaalaku praathamika sadhanalu. eee konamlo yeka-maargam vidhula uniki kooda bahiranga ooha ayinappatikee, dasaabdaala teevramaina pariseelananu tattukunna aneka mandhi abhyardhulunnaaru. vaatilo konni prapanchavyaaptamgaa chaalaa telecommunicationlu, ii-commers mariyu ii-banking vyavasthalaku avasaramaina amsaalu.
saiddhaantika nirvachanam.
f" anae function "f" nuu bahupadi samaya algorithm dwara lekkinchagaligite "f" anedi oka-maargam, conny "f" kosam suudoe-inversnu lekkinchadaaniki prayatninche edainaa bahupadi samaya yaadruchchika algorithm suutram _ 1 anedi athi takkuva sambhaavyatatoo vijayavantamavutundi. (* superscript antey enni punaraavruttulu ayina, clean starr chudandi.) antey, anni yaadruchchika algorithamla suutram _ 1 kosam, anni saanukuula puurnaamkaalu "c" mariyu anni taginanta pedda "n" = podavu ("x"),
ikkada sambhaavyata anedi {0,1} "n" paie vivikta ekareeti pampinhee nundi "x" empika kante ekkuvagaa untundi, mariyu suutram _ 1 yokka yaadruchchikata.
eee nirvachanam prakaram, function chettha-sandarbham ardhamlo kakunda, sagatu-sandarbham loe "tiragadam kashtam" gaa undaali. idhi chaalaa sanklishtata siddhaantaaniki bhinnamgaa untundi (udhaa.zii., enpi-kaatinyam), ikkada "haard" anae padaaniki chettha sandarbhamlo ardham. anduke vann-vae functionla (krinda vivarinchina) kosam kontamandi abhyardhulaku enpi-complete anie telisinappatikii, adhi vaari vann-venesnu suuchimchadu. taruvaati lakshanam samasyanu parishkarinchadaaniki telisina algorithamla lekapovadam meeda matrame aadharapadi untundi.
oka vidhamaina vidhini kaligi undataaniki "nashtakaramainadi" (okariki okaru kaadu) gaa marchadam saripodu. mukhyamgaa, "n" podavu gala edainaa input meeda "n" sunnaala stringnu avtput chese function "vann-vae function kaadu" endukante adhe avutputku daariteese inputto ravadam sulabham. marinta khachitamgaah kevalam sunnaala stringnu avtput chese atuvanti function kosam, input "f" ("x") paie "n" podavu gala edainaa stringnu avtput chese algorithm "f" avtput yokka saraina premagenu "kanugontundi", idhi avtput stringnu kanugonadaaniki modata upayoginchina input kakapoyina.
sambandhita bhavanalu.
vann-vae prastaarana anedi vann-vae function, idhi kooda oka prastaarana-antey, bijective ayina vann-vae function. yeka-maargam prastaaranalu oka mukhyamaina guudha lipi shaastram yokka aadimamainavi, mariyu vaati uniki yeka-maargam vidhula uniki dwara suuchimchabadutumdaa anedi teliyadu.
trapdoor vann-vae function ledhaa trapdoor prastaarana anedi oka pratyeka rakamaina vann-vae function. trapdoor" anie piluvabade konni rahasya samacharam teliyakapothe atuvanti functionnu tippadam kashtam.
gharshana-rahita haash function "f" anedi "gharshana-nirodhakata" kooda kaligina oka-maargam function; antey, yea yaadruchchika bahupadi samaya algorithm gharshananu kanugonalekapovacchu-"x", "y" anae vibhina viluvalu, antey "f" ("x") = "f" ("y")-takkuva sambhaavyata laeni sambhaavyatatoo.
yeka-maargam vidhula yokka saiddhaantika chikkulu.
f" anedi vann-vae function ayithe, appudu "f" yokka inversion anedi oka samasya avutundi, dheeni avutputnu lekkinchadam kashtam (nirvachanam prakaram) conny tanikhi cheyadam sulabham (daanipai "f" nuu ganinchadam dwara). anduvalla, vann-vae function uniki fp ≤ fnp anie suuchistumdi, idhi p ≤ np anie suuchistumdi. ayithe, p ≤ np anedi vann-vae functionla unikini suuchimchadu.
vann-vae function uniki aneka itara upayogakaramaina bhavanala unikini suuchistumdi, veetilo
vann-vae functionla kosam abhyardhula.
vann-vae functionlaku (april 2009 natiki) eee krindi aneka mandhi abhyardhulu unnaaru. spashtamgaa, adhi teliyadu
eee vidhulu nijaaniki yeka-maargam; conny vistrutamaina parisoedhana ippativaraku vaatilo dhenikee samarthavanthamaina inverting algorithamnu roopondinchadamlo viphalamaindi.
gunakaaram mariyu karakamu.
f" anae function binary sangnaamaanamlo rendu pradhana sankhyalu "p" mariyu "q" nii inputgaa teesukoni vaati gunakam tirigi istundi. eee functionnu "o" ("b" 2) samayamlo "sulabhamgaa" lekkinchavacchu, ikkada "b" anedi inputla mottam bits sankhya. eee functionnu vilomam cheyadaaniki icchina puurnaamkam "n" yokka kaarakaalanu kanugonadam avasaram. telisina uttama kaaraka algorithamlu suutram _ 5 timelo nadustaayi, ikkada b anedi "n" nii suuchimchadaaniki avasaramaina bitla sankhya.
p" mariyu "q" lanu tagina ardha praadhamika shrenilo vistarinchadaaniki anumatinchadam dwara eee functionnu saadhaaraneekarinchavachchu. yaadrucchikamgaa enchukunna puurnaamkaalaku "f" anedi oka-maargam kaadani gamaninchandi, endukante gunakam sambhaavyata 3/4 thoo karakamga 2nii kaligi untundi (endukante ekapakshamgaa "p" besigaa unde sambhaavyata 1/2, mariyu adevidhamgaa "q" kosam, kabatti avi swatantramgaa enchukunte, rendoo besigaa unde sambhaavyata 1/4; anduvalla p ledhaa q sarigaa unde sambhaavyata).
rabin function (modular squaring).
rabin function, ledhaa squaring maadyulo formula _ 6, ikkada mariyu avi praimlu vann-vae functionla sekaranagaa nammutaaru. memu vraastaamu
squaring maadyulooni suuchimchadaanikih rabin sekaranalo oka nirdishta sabhyudu. varga muulaalanu velikiteesetappudu, i anie chuupavachchu.ii. rabin functionnu vilomam cheyadam anedi gananaparamgaa kaarakamtho samanam (bahupadi-samaya taggimpu anae ardhamlo). anduvalla karakalu kathinamgaa untene rabin sekarana yeka-maargam anie niroopinchavacchu. idhi pratyeka kesuku kooda vartistundi, dheenilo mariyu adhe bitt podavu untundi. eee rabin function vann-vae anae oohapai rabin guudha lipi vyavastha aadharapadi untundi.
vivikta ghaataanka mariyu samvargamaanam.
modular ghaataankam bahupadi samayamlo cheyavachu. eee functionnu vilomam cheyadaaniki vivikta samvargamaanam ganana avasaram. prastutam aneka prasiddha samuuhaalu unnaayi, veeti kosam bahupadi samayamlo antarleena vivikta samvargamaanam lekkinchadaaniki yea algorithm teliyadu. eee samuuhaalannii parimita abelian samuuhaalu mariyu saadhaarana vivikta samvargamaanam samasyanu eee vidhamgaa vivarinchavacchu.
g" anedi cardinality "n" yokka parimita abelian samuuhamgaa undanivvandi. gunakaaram dwara daani samuuha kaaryaacharananu soochinchandi. oka aadima moolakam mariyu maroka muulakaanni pariganinchandi. vivikta samvargamaanam samasya emitante, saanukuula puurnaamkam "k" nuu kanugonadam, ikkada, ilaa untundih
sameekaranaanni parishkarinche puurnaamkam "k" nuu "β" yokka bays "α" kuu vivikta lagarithm antaaru. okaru raastunnaaru.
vivikta samvargamaanam guudha lipi saastramlo "g" samuuhaaniki prasiddha empikalu chakriya samuuhaalu (z "p") × (e.zii. elgamal encryption, defy-hellman kii exchange, mariyu digital signature algorithm) mariyu parimita kshetraalapai deerghavruttaakaara vakrarekhala chakriya upa samuuhaalu (deerghavruttaakaara vakra guudha lipi shaastram chudandi).
deerghavruttaakaara vakrarekha anedi santruptikaramaina kshetram yokka muulakaala jatala samiti. vakrarekhaloni muulakaalu "point addition" anae operation kinda oka samuuhaanni yerparustaayi (idhi feeled yokka addition operationku samanam kaadu). oka binduvu "p" yokka "kp" nii oka puurnaamkam "k" ("i") thoo guninchadam.ii.", puurnaamkaala sankalana samuuham yokka samuuha charya) anedi binduvu yokka punaraavruta jodimpugaa nirvachinchabadindi. k" mariyu "p" telisinatlayite, lekkinchadam sulabham, conny "r" mariyu "p" matrame telisinatlayite, "k" nuu lekkinchadam kashtamani bhaavistaaru.
guudha lipi saastraparamgaa surakshitamaina haash vidhulu.
shaa 256 vanti vaegamgaa ganinchagala aneka guudha lipi shaastra haash vidhulu unnaayi. konni saralamaina samskaranalu adhunaatana vislaeshanhaku gurayyayi, conny balamaina samskaranalu yeka-maargam ganana kosam vegavantamaina, aacharanaatmaka parishkaralanu andistuunee unnaayi. gatamlo vijayavantamaina daadulaloo konnintini addukovadaniki marinni paddhatulu eee vidhulaku saiddhaantika maddatugaa unnaayi.
itara abhyardhula.
vann-vae functionla kosam itara abhyardhulalo yaadruchchika sarala sankethaala decoding yokka kaatinyam, konni jaalaka samasyala kaatinyam mariyu upasamiti mottam samasya (nakache-stern napsack guudha lipi vyavastha) unnaayi.
saarvatrika yeka-maargam function.
vann-vae functionlu unte mariyu unte matrame vann-vae function anie niroopinchabadina oka spashtamaina function "f" undhi. maroe maatalo cheppalante, edainaa function vann-vae ayithe, appudu "f" kooda. eee function pradarsinchabadina modati combinatorial puurti vann-vae function kabatti, dheenini "universal vann-vae function" anie pilustaaru. yeka-maargam functionnu kanugone samasya atuvanti function undani bahusha nirmanatmakamga niroopinchadaaniki taggutundi.

