Jos meillä on permutaatio f:A->A, siten, että
{f^n(x0) (n=0,...,|A|-1)}=f(A), kun x0 in A.
Jos nyt g on yksisuuntainen permutaatio (onko sellaisia), niin voidaanko laskea polynomisessa ajassa
f^n(x0), kun tunnetaan g(f^k(x0)) (k=0,..,n-1)
g^(-1) on siis ainoastaan eksponentiaalisesti laskettavissa.
{f^n(x0) (n=0,...,|A|-1)}=f(A), kun x0 in A.
Jos nyt g on yksisuuntainen permutaatio (onko sellaisia), niin voidaanko laskea polynomisessa ajassa
f^n(x0), kun tunnetaan g(f^k(x0)) (k=0,..,n-1)
g^(-1) on siis ainoastaan eksponentiaalisesti laskettavissa.
Vastaukset 11
Vanhimmat
Jos pystyt laskemaan mitä on g(f^k(x0)), pystyt kyllä laskemaan mitä on g^(-1). Permutaatioiden g ja g^(-1) laskeminen kuuluu samaan kertaluokkaan.
Miksi käänteispermutaatio olisi aikavaatimukseltaan samaa kertaluokkaa kuin alkuperäinen permutaatio.
Esim. Jos meillä on järjestetty taulukko (koko n), niin pystymme "sotkemaan" taulukon n. askeleella (permutointia), kun taas taulukon järjestäminen vie aikaa n*log n askelta (permutointia tämäkin).
Pakko myöntää: muistin väärin permutaatioiden laskusäännöt. Tehtävä ei menekään kuten alun perin arvelin. Enpäs tiedäkään mikä olisi tehokkain tapa ongelman ratkaisemiseksi.
f on siis tavallinen syklinen permutaatio?
Voisitko selkeyttää, että mitä tarkalleen ottaen saamme olettaa tiedettävän g:stä ja f:stä?
Mikä on alkuperäislähde?
f ja g ovat polynomisessa ajassa laskettavissa olevia funktioita. f^(-1) voi olla polynomisessa ajassa laskettavissa. g^(-1) ei siis ole polynomisessa ajassa laskettavissa vaan se on eksponentiaalinen. Tosin eihän vielä tiedetä voiko tällaisia funktioita g olla edes olemassa, mutta jos olisi.
Tarkoitin lähinnä, että minkä muuttujien arvot tiedetään/ ei tiedetä: jos f on laskettavissa polynomisessa ajassa, onhan silloin myös f^n(x0), ellei f ole tuntematon?
Jos puolestaan vain tunnetaan g(f^k(x0)), 0
Kun tunnetaan kuvat g(f^k(x0)), niin f^n(x0) laskea kaavalla f(g^(-1)(g(f^(n-1)(x0))) ongelmana on se, että g^(-1) ei ole polynomisesti laskettavissa, se mitä nimim.matikaatti ilmeisesti haluaa kysyä on: voidaanko informaatiota f^k(x0) kuvista käyttää jotenkin hyödyksi, jotta g^(-1)(x) ei tarvitse käyttää.
Itse en osaa vastasta kysymykseen.
Tarkoitin nimenomaan, että jos tietoa g^(-1):sta tai f:sta ei ole käytettävissä, tehtävä näyttäisi mahdottomalta.
Siis algoritmit funktion f ja g laskemiseksi tunnetaan ja algoritmit ovart polynomisessa ajassa laskettavissa. Myös f^(-1) tunnetaan ja se on polynomisessa ajassa laskettavissa. g^(-1) tunnetaan mutta se EI ole polynomisessa ajassa laskettavissa vaan aikaa kuluu eksponentiaalisesti. A:n jäsentä x0 ei tunneta, se on valittu satunnaisesti.
Kysysmys on siitä, että jos tiedämme miten alkuperäinen "viesti" on muodostettu (funktiolla f), niin saammeko viestistä tietoa kun tiedämme salaustulokset (funktiolla g).
Se x0:n tuntemattomuus/satunnaisuus oli aika oleellinen tieto -- nyt tässä alkaa olla jotain tolkkua. :)
Eli käytännössä tässä kysytään mahdollisen salausmetodin luotettavuutta... Jos se ei ole luotettava, sen voinee todistaa, mutta on paljon vaikeampaa todistaa päinvastainen.
Mutta mietin asiaa, ja palaan siihen myöhemmin.
Riippuen kontekstista, jos A:n jäsenten esiintymisfrekvenssit ovat tiedossa, niin voimme suorittaa frekvenssianalyysin salatulle tekstille ja verrata alkuperäiseen.
Voimme toistaa saman analyysin kahden tai useamman A:n jäsenen mittaisille pätkille.
Jos tiedämme jotakin A:sta, voisimme myös kokeilla (eli arvata) eri x0:n mahdollisia arvoja, ja kullekin arvolle laskea polynomiajassa sen generoiman joukon ja tarkistaa jos joukko täyttää tietämämme kriteerit A:sta.
Sanoisin, että salaus ei ole kovin luotettava, koska jos salatussa viestissä on mitään säännönmukaisuuksia, ne säilyvät permutoidessa.
Mutta jos tätä salaustapaa käyttää yhdessä toisen, tehokkaamman salausmetodin kanssa, se on ihan käyttökelpoinen.
En osaa ensihätään antaa tämän järkevämpää tai tarkempaa vastausta.