<

## Computationally Intensive II

A cache by potàfleurs adopted by mareczech Message this owner
Hidden : 02/18/2008
Difficulty:
Terrain:

Size:  (small)

#### Watch

How Geocaching Works

Please note Use of geocaching.com services is subject to the terms and conditions in our disclaimer.

### Geocache Description:

[CZ] Dalsi vypocet pouzivany v kryptografii. Tento problem neni tak proflakly jako faktorizace (GC12NFZ).
[EN] Another simple equation to solve (see gray text for short english version)

[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)

xxxxABCDEFGHxx...xx (tj. zajima vas 5. az 12. nejvyssi cifra)
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 5th to 12th 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 (ga mod p)b mod p = (gb 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 ga mod p (tedy mocninu, ta se pocita lahodne)
56 mod 23 = 8.
3. Franta nahodne zvoli tajne cislo b=15, posle Jane gb mod p
515 mod 23 = 19.
4. Jana spocte (gb mod p)a mod p
196 mod 23 = 2.
5. Franta spocte (ga mod p)b mod p
815 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).

cbq oýinyýz iryvxáarz
haqre na byq ureb

Decryption Key

A|B|C|D|E|F|G|H|I|J|K|L|M
-------------------------
N|O|P|Q|R|S|T|U|V|W|X|Y|Z

(letter above equals below, and vice versa)

Find...

### 505 Logged Visits

454      3      27      1      4      4      1      5      4      2

**Warning! Spoilers may be included in the descriptions or links.