Tunnetaan a, b ja c. Miten löydetään pienin x, jolla (a^x-b)/c on kokonaisluku? Kokeilu ei ole vaihtoehto, tarvitsen toteutuskelpoisen yleisemmän algoritmin.
kokonaislukuoptimointia
kokeilua mielessä
5208
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 5
Vanhimmat
Karkasi ennen aikojaan. Tiedetään myös, että a, b ja c ovat (positiivisia) kokonaislukuja ja tuloksenkin on oltava positiivinen (joskin tästä kai voidaan joustaa). Tunnetaan myös, että c > b ja c > a, a:n ja b:n suhteista ei tiedetä mitään.
Valitaan x=ln(b c)/ln(a). Tällöin (a^x-b)/c=1.
Tuo otsikko tietysti viittaa siihen, että x:n on oltava myös kokonaisluku.
Et sitten paljoa vaadikaan! Haluat hyvän ratkaisun diskreetin logaritmin probleemalle.
Tuo on luultavasti ns. one-way-funktio eli helppo laskea mutta vaikea kääntää.
Ongelmasi on ratkaista kongruenssiyhtälö a^x=b (mod c).
Eli laskea diskreettilogaritmi luvulle b kun modulo on c ja kanta-luku a.
Tälle ei tunneta yleisessä tapauksessa (eikä usein yksinkertaisissakaan tapauksissa) tehokasta
algoritmia. Monet salaukset perustuvat tähän otaksumaan että sellaista ei voi edes olla olemassa.
Myyntimies ei sitten vissiin tuota tiennyt, kun lupasi toteutuksen asialle.
Eipä se mitään... pitää vissiin koittaa vain päästä firman tavoitteisiin ettei tuu monoa.
Kiitos tiedosta :/