
ack tarfa kaary

computer vigyaan mein, ack tarfa kaary ack aisaa kaary haye jisaki ganana pratyek input parr karna aasaan haye, lekin yaadrichhik input kii chhavi koo dekhate hue ise ulatana kathin haye. yahaan, "aasaan" aur "kathin" koo computational jatilata siddhant key arth mein samajha jaanaa haye, vishesh roop seey bahupad samay samasyaon key siddhant koo. ack-seey-ack naa honah ack-tarfa kahal jaane vaale kaary key liye paryaapt naheen maanaa jaataa haye (neeche saiddhaantik paribhasha dekhein).
iss tarah key ektarafa karyon kaa astitva abhee bhee ack khula anuman haye. unakaa astitva yeh saabit karega kii jatilata varg pee aur np samaan naheen hain, iss prakaar saiddhaantik computer vigyaan key sabse ansuljhe prashn kaa samadhan hoga. isake vipareet satya key roop mein gyaat naheen haye, i.ee. ack pramaan kaa astitva kii p ≤np seedhe ektarafa karyon key astitva kaa sanket naheen dega.
lagu sandarbhon mein, "aasaan" aur "kathin" shabdon kii vyakhya aamtaur parr kuchh vishisht computing ikai key saapeksh kii jaati haye; aamtaur parr "vaidh upayogkartaon key liye paryaapt sastaa" aur "kissy bhee durbhavanapurna agent key liye nishiddh roop seey mahanga". iss arth mein, ack tarfa kaary, gupt lipi, vyaktigat pehchaan, pramanikaran aur anya detta suraksha anuprayogon key liye maulik upkaran hain. jabaki iss arth mein ektarafa karyon kaa astitva bhee ack khula anuman haye, aise kaee ummidwar hain jinhone dashakon kii gahan jaanch kaa saamana kiya haye. unamen seey kuchh duniya bhar mein adhikansh dursanchar, ee-commers aur ee-banking pranaliyon key aavashyak tatva hain.
saiddhaantik paribhasha.
ack falan "f": {0,1} * * ack tarfa haye yadi "f" kii ganana ack bahupad samay algorithm dwara kii jaa sakati haye, lekin koee bhee bahupad samay yaadrichhik algorithm sootra _ 1 joe "f" key liye ack chhadm-vyutkram kii ganana karane kaa prayaas kartaa haye, vaha nagany sambhavana key saath safal hotaa haye. (* superscript kaa arth haye punaraavrittiyon kii koee bhee sankhya, "clean starr" dekhein.) arthaat, sabhi yaadrichhik algorithm sootra _ 1 key liye, sabhi sakaratmak purnank "c" aur sabhi paryaapt roop seey badey "n" = lambai ("x"),
jahan sambhavana "x" key vikalp parr haye, joe kii "n" parr asatat samaan vitaran seey haye, aur sootra _ 1 kii yaadrichhikta.
dhyaan dein kii, iss paribhasha key anusaar, kaary koo sabse kharaab-mamle key arth mein naheen, balki ausat-mamle mein "ulatane key liye kathin" honah chaahiye. yeh jatilata siddhant seey alag haye (ee.jee., aine. pee.-kathorta), jahan shabd "kathor" kaa arth sabse kharaab sthiti mein hotaa haye. yahee kaaran haye kii bhale hii kuchh ummidwar ektarafa karyon (neeche varnit) key liye aine. pee.-poorna key roop mein jaane jaate hain, yeh unaki ektarfaataa kaa sanket naheen detaa haye. baad vaalaa guna kewal samasya koo hull karane key liye gyaat algorithm kii kamee parr adharit haye.
ack tarfa kaary key liye ack kaary koo "haani" (ack-seey-ack naheen) banaane key liye yeh paryaapt naheen haye. vishesh roop seey, vaha kaary joe lambai "n" key kissy bhee input parr "n" shoonya kii string koo output kartaa haye, vaha "ack tarfa kaary" naheen haye kyonki ack input key saath aanaa aasaan haye jiska parinam samaan output mein hoga. adhik sateek roop seh aise kaary key liye joe kewal shoonya kii ack string kaa output detaa haye, ack algorithm "f" joe kewal input "f" ("x") parr "n" lambai kii kissy bhee string kaa output detaa haye, output kaa ack uchit premage "paayega, bhale hii yeh input naa hoe joe mool roop seey output string khojane key liye upayog kiya gayaa thaa.
sambandhit avadhaaranaaen.
ack tarfa kramparivartan ack tarfa falan haye joe ack kramparivartan bhee haye-yaani ack tarfa falan joe dwi-uddeshya haye. ack tarfa kramparivartan ack mahatvapurna gupt lipigat adim haye, aur yeh gyaat naheen haye kii unakaa astitva ack tarfa karyon key astitva seey nihit haye yaa naheen.
trapdoor vann-way function yaa trapdoor kramparivartan ack vishesh prakaar kaa vann-way function haye. iss tarah key kaary koo taba taka ulatana mushkil haye jaba taka kii kuchh gupt jaankaari, jise "trapdoor" kahaa jaataa haye, gyaat naa hoe.
ack takraav-mukt haish function "f" ack ektarafa function haye joe "takraav-pratirodhi" bhee haye; yaani, koee yaadrichhik bahupad samay algorithm ack takraav koo paa naheen sakata haye-alag maan "x", "y" jaise kii "f" ("x") = "f" ("y")-gair-nagany sambhavana key saath.
ektarafa karyon key saiddhaantik nihitarth.
yadi "f" ack tarfa falan haye, tou "f" kaa vyutkram ack aisee samasya hogi jiska output ganana karna kathin haye (paribhasha key anusaar) lekin jaanch karna aasaan haye (kewal usa parr "f" kii ganana karke). iss prakaar, ack tarfa falan key astitva kaa tatparya haye kii fp ≤ fnp, joe badale mein p ≤ np kaa tatparya haye. haalaanki, p ≤np ack tarfa karyon key astitva kaa sanket naheen detaa haye.
ack tarfa kaary key astitva kaa tatparya kaee anya upayogi avadhaaranaon key astitva seey haye, jinamen shamil hainh
ektarafa karyon key liye ummidwar.
nimnalikhit kaee ummidwar ektarafa karyon key liye hain (aprail 2009 taka). spasht roop seey, yeh gyaat naheen haye kii kyaa
yeye kaary vaastav mein ektarafa hain; lekin vyaapak shodh abb taka unamen seey kissy key liye ack kushal inverting algorithm kaa utpaadan karane mein whiffle rhaa haye.
gunan aur kaarak.
falan "f" dwiaadhaari sanketan mein dou abhaajya sankhyaaen "p" aur "q" koo input key roop mein letaa haye aur apane utpaad koo lautaata haye. iss falan kii ganana "oh" ("bee" 2) samay mein "aasaani seey" kii jaa sakati haye, jahan "bee" input key bits kii kull sankhya haye. iss falan koo ulatane key liye diye gaye purnank "aine" key karakon koo khojane kii aavashyakta hoti haye. sootra _ 5 samay mein gyaat sabse achchha kaarak algorithm, jahan b "n" kaa pratinidhitva karane key liye aavashyak bits kii sankhya haye.
iss falan koo "pee" aur "kyu" koo upayukt ardh-prime key sett parr seema kii anumati dekar saamaanyikrit kiya jaa sakata haye. dhyaan dein kii yaadrichhik roop seey chayanit purnankon key liye "f" ack tarfa naheen haye, kyonki utpaad mein sambhavana 3/4 key saath ack kaarak key roop mein 2 honge (kyonki ack manmana "p" visham honey kii sambhavana 1/2 haye, aur isi tarah "q" key liye bhee, isaliye yadi way swatantra roop seey chune jaate hain, tou sambhavana haye kii donon visham hain isaliye 1/4 haye; isaliye sambhavana haye kii p yaa q summ haye, haye).
rabin falan (modular varg).
rabin falan, yaa vargakar modulo sootra _ 6, jahan aur abhaajya hain, koo ektarafa karyon kaa sangrah maanaa jaataa haye. humm likhate hain
vargakar modulo koo niroopit karane key liyeh rabin sangrah kaa ack vishisht sadasya. yeh dikhaaya jaa sakata haye kii vargamool nikaalate hue, i.ee. rabin falan koo ulatana, computational roop seey kaarak key barabar haye (bahupad-samay mein kamee key arth mein). isaliye yeh saabit kiya jaa sakata haye kii rabin sangrah ektarafa haye yadi aur kewal tabhi jaba kaarak kathin hoe. yeh vishesh mamle key liye bhee lagu hotaa haye jisamen aur samaan bitt lambai key hotey hain. rabin gupt pranali iss dhaarana parr adharit haye kii yeh rabin kaary ektarafa haye.
asatat ghaatiya aur laghuganak.
modular ghatank bahupad samay mein kiya jaa sakata haye. iss kaary koo ulatane key liye asatat laghuganak kii ganana karane kii aavashyakta hoti haye. vartamaan mein kaee lokpriya samooh hain jinake liye bahupad samay mein antarnihit asatat laghuganak kii ganana karane key liye koee algorithm gyaat naheen haye. yeye samooh sabhi parimit abelian samooh hain aur samanya asatat laghuganak samasya koo iss prakaar varnit kiya jaa sakata haye.
g" koo cardinality "n" kaa ack seemit abelian samooh honey dein. gunan dwara isake samooh sanchaalan koo darshaata haye. ack adim tatva aur ack anya tatva parr vichaar karein. asatat laghuganak samasya sakaratmak purnank "k" koo khojane key liye haye, jahan, aisaa kih
sameekaran koo hull karane vaale purnank "k" koo aadhar "α" key liye "β" kaa asatat laghuganak kahaa jaataa haye. ack likhate hain.
asatat laghuganak guptalekhan mein samooh "jee" key liye lokpriya vikalp chakreeya samooh (jaid "pee") × (ee.jee. algamal encryption, diffy-hellman kii exchange, aur digital signature algorithm) aur parimit kshetron parr andakar vakron key chakreeya upsamooh ("dekhein" andakar vakr guptalekhan).
ack andakar vakr ack kshetra key tatvon key jode kaa ack samooh haye joe santusht kartaa haye. vakr key tatva "bindu jodd" naamak ack operation key tahat ack samooh banaate hain (joe kshetra key jodd operation key samaan naheen haye). ack purnank "key" ("i") dwara ack bindu "pee" kaa gunan.ee.", purnankon key yogaatmak samooh kii ack samooh kriya) koo bindu key baar-baar judane key roop mein paribhaashit kiya jaataa haye. yadi "k" aur "p" gyaat hain, tou ganana karna aasaan haye, lekin yadi kewal "r" aur "p" gyaat hain, tou "k" kii ganana karna kathin maanaa jaataa haye.
gupt lipi key roop mein surakshit haish kaary.
kaee cryptographic haish kaary hain joe ganana karane mein teji seey hain, jaise kii shaa 256. kuchh saral sanskaran parishkrit vishleshan mein gir gaye hain, lekin sabse majboot sanskaran ack tarfa ganana key liye tej, vyaavhaarik samadhan pradaan karna jaari rakhate hain. karyon key liye adhikansh saiddhaantik samarthan pahale key kuchh safal hamalon koo whiffle karane key liye adhik takneeken hain.
anya ummidwar.
ack tarfa karyon key liye anya ummidvaaron mein yaadrichhik raikhik code kii decoding kii kathorta, kuchh jaali samasyaon kii kathorta, aur subset summ samasya (naike-stern napsack cryptosystem) shamil hain.
saarvbhaumik ack tarfa kaary.
ack spasht falan "f" haye joe ektarafa saabit huaa haye, yadi aur kewal tabhi jaba ektarafa falan maujood houn. dusare shabdon mein, yadi koee kaary ektarafa haye, tou "f" bhee haye. choonki yeh kaary pradarshit kiya jaane vaalaa pahala poorna ack tarfa sanyojan thaa, isaliye ise "saarvbhaumik ack tarfa kaary" key roop mein jaanaa jaataa haye. iss prakaar ack tarfa kaary khojane kii samasya cumm hoe jaati haye aur yeh saabit hoe jaataa haye kii aisaa ack kaary maujood haye.