Computationally Intensive II Mystery Cache

[CZ] Ukol je (jako obvykle) velice jednoduchy: Najdete nejmensi prirozene cislo k, aby platila nasledujici rovnice (znak = ma mit 3 carecky):
5 ^k = 6361196924231058595008858273263807320 (mod 15860584089531798358308118294328202587)

Nalezene cislo (diskretni logaritmus) muze byt vyjadreno dekadickymi cislicemi
xxxxABCDEFGHxx...xx (tj. zajima vas 5. az 12. nejvyssi cifra)
a souradnice kese jsou
N 49° 1A.BCD E 016° 3E.FGH.

[EN] The task is very simple: Find the smallest natural number k such, that the following equation was valid:
5 ^k = 6361196924231058595008858273263807320 (mod 15860584089531798358308118294328202587)

The number found (discrete logarithm) is expressed by decimal digits
xxxxABCDEFGHxx...xx (i.e. you are interested in 5^th to 12^th most significant digits)
and the cache coordinates are
N 49° 1A.BCD E 016° 3E.FGH.
Anyway, being a foreign visitor, I believe you should rather look for traditional caches and not waste your time and computer battery on this trifle.

Diskretni logaritmus se faktorizaci (GC12NFZ) podoba v tom, ze je to funkce, ktera se dobre pocita jednim smerem, ale extra-blbe (vyzkousejte si) smerem druhym. Dosud se nezna algoritmus, ktery by tento problem dokazal resit v polynomialnim (tedy aspon trochu rozumnem) case. Takze pridat par cifer zadani znamena znekolikanasobit dobu reseni.

Exponencialni funkce (odvracena strana logaritmu) ma jeste tu peknou vlastnost, ze (g^a mod p)^b mod p = (g^b mod p)^a mod p. Totiz dobre se pomoci neho necha dohodnout soukromy klic pro sifrovani pres odposlouchavanou linku. Predstavte si Frantu a Janu, jak si chteji dohodnout klic pro sifrovani privatni komunikace (domlouvaji si rande):

1. Oba dohodnou (predem, klidne vystavi na webu) prvocislo p=23 a bazi g=5.
2. Jana nahodne zvoli tajne cislo a=6, posle Frantovi g^a mod p (tedy mocninu, ta se pocita lahodne)
   5⁶ mod 23 = 8.
3. Franta nahodne zvoli tajne cislo b=15, posle Jane g^b mod p
   5¹⁵ mod 23 = 19.
4. Jana spocte (g^b mod p)^a mod p
   19⁶ mod 23 = 2.
5. Franta spocte (g^a mod p)^b mod p
   8¹⁵ mod 23 = 2.

Oba tak maji spolecny klic (=2), kterym budou sifrovat svoji dalsi komunikaci. Sycak Tonda, ktery jejich komunikaci odposlouchava, musi hledat stejny program jako vy, resitele teto kese, a s jeho pomoci se ke klici snazit dobrat. Jana a Franta ale nejsou zadni mantaci, takze nepouzili uvedena cisla, ale nejakou stovku cifer prihodili. Oni vysledek maji ve vterinach, Tonda, chudak (ale dobre mu tak, smirakovi), ma o zabavu postarano na par tisic let a jeste dostane kartac od kolegu, ze po tu dobu vytezuje cely firemni cluster.

Kdyz matematik Pepa bude mit spatne spani a vymysli, jak diskretni logaritmus spocitat taky ve vterinach (nebo treba v minutach), vsechny Jany a Frantove ho budou spechat nakopat do hader a vsichni Tondove za nim budou spechat se zlatou cihlou (nebo baseballovou palkou - to spis, Tonda je prece sycak...). Prejte Pepovi dobre spani, protoze algoritmus dost podobny tomuto beztak pouzivate pri komunikaci se svym e-mailovym serverem a se svou bankou.

Kdyz se Jana a Franta domlouvaji, kolik pouzit cifer pro p, maji praci celkem snadnou: radsi vic nez min. Ja to mam o dost tezsi - kdyz jich zvolim malo, najdete kes za chvilicku a nebude zadna bzunda. Kdyz jich zvolim moc, prvni FTF bude za padesat let a nebude to tudiz FTF ale EZF (V te dobe bude prece spusten system Galileo a podle ocekavani budou cache na uzemi Evropy prevzaty do systemu Euroschlupspiele, ja, coby Euroschlupmacher teto Euroschlup v souladu s Forschriften prelozim listing do peti jazyku k vytvoreni Ofiziale Euroschlupkarte, a k dodrzeni Publizierenkultur ocisluju vzorce a doplnim uvod, zaver a prohlaseni o opatrenich pro zajisteni rovnosti genderu a minimalizaci dopadu na zivotni prostredi...). Doufam tedy, ze zvoleny pocet cifer je akurat a na chvili vas zamestna. Po nejakem case (mesic? dva? tri?) mozna publikuju nejaka kratsi cisla - detskou verzi zadani, resitelnou i pomoci webovych hracicek. No on stejne marekl nebo nekdo vygoogli utilitku, na kterou jsem nenarazil a se kterou to bude mit za osm vterin a ja budu opet za jahodu...

Za cestne reseni kese nebudiz povazovano zjisteni cisla k nebo primo souradnic od jineho kacera; ziskani programu pro louskani diskrentiho logaritmu od kohokoliv, nebo zadani problemu treti osobe, je zcela v poradku (ne vsichni jsou programatori a prelozi si program sami).

Do elektronickeho logu prosim napiste zazitky z vypoctu (jak dlouho to trvalo, co jste pouzili, o kolik vzrostla teplota v mistnosti atp).