<

## Computationally Intensive I

A cache by potàfleurs adopted by mareczech Message this owner
Hidden : 5/5/2007
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] Kes, ktera proveri vas pocitac. Pokud pocitac nemate, sezente si moc dobrou tuzku, more papiru a dovolenou v delce mnoha milionu let.
[EN] A cache that will exercise your computer.

Ukol je velice jednoduchy. Rozlozte cislo 1641479785730055578984265073209012064804226913053264286391250859095632683623 na faktory (dve prvocisla, ktera kdyz vynasobite, dostanete prave tohle cislo), ty oznacte p, q, kde p > q. Faktory se skladaji z cislic:
p = xxxxABCDxx...xx
q = xxxxEFGHxx...xx,
kde x je neurcita cislice a xx...xx je neurcity pocet neurcitych cislic. Proste z tech faktoru vas zajimaji cislice 5.-8. zleva.
Souradnice kese jsou pak: N 49° 1A.BCD E 016° 3E.FGH

[EN] The puzzle is very simple. Split the number 1641479785730055578984265073209012064804226913053264286391250859095632683623 into factors (two prime numbers, which mutually multiplied produce the given number), call those p, q, where p > q. The factors are then composed of digits:
p = xxxxABCDxx...xx
q = xxxxEFGHxx...xx,
where x is an unknown digit and xx...xx is an unknown number of unknown digits. Simply, what you need are 5th-8th most significant digits.
The cache coordinates are then: N 49° 1A.BCD E 016° 3E.FGH

Jak se muzete dozvedet treba pri hledani Projektu Enigma (mimochodem vyborna serie!), soucin prvocisel se pouziva v kryptografii, protoze cislo faktorizovat se zatim neumi o moc lip nez prostym prohledanim moznosti: zkousite jedno prvocislo po druhem, az jednim jde to zadane cislo delit - pak jdete domu a mate vydelano.

Tato keska spoleha na faktory cca 125bitove, takze vas to snad na chvili zamestna. Snad. Mimochodem, slozitost algoritmu je exponencialni, coz znamena, ze s kazdym bitem faktoru navic reseni problemu trva dvakrat dele. Proto nikdo ani nezkousi tzv. lamat 1024 bitove klice, dnes bezne pouzivane kdejakym Lojzou. Mimochodem, puvodne byly faktory 37bitove, a kombinaci smuly a liknavosti jsem to povazoval za dostatecne. Resici kaceri pripravili pocitace na dlouhy beh a pak za zlomek vteriny dostali vysledek. Tim se nic nemeni na exponencialni slozitosti algoritmu. Je to potvrzeni omseleho moudra, ze (asymptoticka) slozitost problemu popisuje, jak se veci komplikuji se zvetsovanim zadani, ale opravdu nebrani tomu, aby jeden algoritmus byl milionkrat rychlejsi nez druhy.

Pokud se citite, ze prece mate stesti a s kalkulackou v ruce faktory uhodnete, nic proti tomu. Vase stesti by ale bylo takove, jako kdybyste vsadili hodnekrat po sobe sportku a pokazde vyhrali jackpot. V takovem pripade prosim nemrhejte takovym darem na tuhle kes, tu sportku nekolikrat vsadte, jeden jackpot mi poslete a ja vam za to sdelim souradnice finalky, ok?

Pokud prijdete na metodu, jak tento problem vyresit rychle, tj. rekneme v par minutach, v zadnem pripade to neventilujte do logu. Privolali byste na sebe a svou rodinu pozornost tajnych sluzeb nejruznejsich mocnosti a rezimu. A nebo jsem prehlid jeste neco dalsiho a faktory maji byt 300bitove

Program na reseni tohoto problemu vam doporucovat nebudu, protoze nachazite daleko lepsi softwary nez ja.

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

zrxverx qbc

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

### 767 Logged Visits

716      1      39      2      1      1      4      3

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