Skip to Content

<

Computationally Intensive II

A cache by potàfleurs adopted by mareczech Send Message to Owner Message this owner
Hidden : 2/18/2008
Difficulty:
5 out of 5
Terrain:
2 out of 5

Size: Size: small (small)

Join now to view geocache location details. It's free!

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)

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

Additional Hints (Decrypt)

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...

488 Logged Visits

Found it 437     Didn't find it 3     Write note 27     Needs Archived 1     Temporarily Disable Listing 4     Enable Listing 4     Publish Listing 1     Needs Maintenance 5     Owner Maintenance 4     Post Reviewer Note 2     

View Logbook | View the Image Gallery of 21 images

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

Current Time:
Last Updated:
Rendered From:Unknown
Coordinates are in the WGS84 datum

Return to the Top of the Page

Reviewer notes

Use this space to describe your geocache location, container, and how it's hidden to your reviewer. If you've made changes, tell the reviewer what changes you made. The more they know, the easier it is for them to publish your geocache. This note will not be visible to the public when your geocache is published.