Posted By: medvidek (Nezapomen na radost) on 'CZscience' Title: Re: Modularni aritmetika Date: Thu Apr 20 15:58:19 2000 > Tak jsem mel referat na RSA a na jednu vec porad nemohu prijit: > a.b = 1 (mod n), _a_ a _n_ jsou zname, b mam spocitat. > > _a_ i _n_ jsou obrovska cisla, _a_ musi byt nesoudelne s n (proc? 1. otazka) To je jednoduche - aby to melo reseni. b je vlastne inverze k a ve zbytkove tride modulo n. A nejaka veta v algebre rika, ze inverze k a existuje prave kdyz a je nesoudelne s n. > neznam faktorizaci _n_ (jinak bych si dokazal vypomoci cinskou vetou o > zbytcich - je to tak? druha otazka:-)). Tak to nevim. Ted nemam skripta z kryptografie a z te vety si pamatuju jen jeji anglicky nazev - Chinese Reminder Theorem. Ale nechapu, k cemu si chces vypomahat - viz. dale > > Treti otazka: jak se to udela obecne? Pro obrovska cisla, o kterych nic > nevim? Co jak se udela? Overi, ze jsou nesoudelna nebo spocita primo to b? Ono je to v podstate jedno, protoze oboji lze udelat naraz. Prvni s logaritmickou casovou slozitosti, druhe v linearnim case. Prvni je obycejny eukliduv algoritmus na zjisteni nejvetsiho spolecneho delitele - viz. libovolnou literaturu o algoritmech nebo o algebre. Pokud vyjde jedna, pak pokracuji dal. Kazdopadne existuje neco jako Bezoutova veta (nebo se tomu rika rozsireny Eukliduv algoritmus), ktera rika asi toto: pokud nsd(a,b) = c, pak tuji cela cisla > snake Sorry, nejak mi blbne terminal. Tak to poslu a budu pokracovat v dalsim prispevku. medvidek .,. "Co kdybychom jednou na ukazku odhalili svoji tvar, /~ ( ) odlozili masku vedle na polstar. .*~ o ) Kolik by tu zbylo z nas vysusenych mumii?" o ) Slavek Janousek `* /