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                         `*         /