[Megoldva] Matek segítség (RSA kódolás, maradékos osztás)

subscribe

http://stackoverflow.com/questions/2847069/power-and-modulo-on-the-fly-for-big-numbers

bc
Erre tökéletes.

--
Debian - The "What?!" starts not!
http://nyizsa.uni.cc

Nem ide.

ha nem felejtem el, holnap reggel megtalálom az idevágó jegyzeteimet.

http://en.wikipedia.org/wiki/Modular_exponentiation

  function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent & 1) equals 1:
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

855 -nek megnezed a 3233-mal valo maradekat, aztan a 855^2-nek 855^3-nek stb., es egy ido utan loopos lesz (egyszeru dinamikus memoriafoglalas, "megnezemvotemar"), majd ahanyadik elemnel tart a loop (maradekos osztas), annyidik maradekot teszem be

pl. 5-os maradeka a 2^72-nek:
2
2*2=4
8->3
3*2=6->1
1*2->2

2 mar volt, minden 4.-re loopol

72%4=0 azaz 1 lesz az 5-os maradeka, mert 1->2 2->4 3->3 0->1

Mivel 2011 ≡ 11 (mod 200), így elég csak 11^36 -t számolnod.

855-öt szeretnéd hatványozni. Eközben bármikor veheted 3233-mal vett maradékát, ezt kell kihasználni.

855^1 mod 3233 számolása:

855^1 mod 3233

azaz 855

855^2 mod 3233 számolása:

855^2 mod 3233

azaz 367

855^4 mod 3233 számolása:

367^2 mod 3233

azaz 2136

855^8 mod 3233 számolása:

2136^2 mod 3233

azaz 733
...

855^2735 mod 3233=855^1 * 855^2 * 855^4 * 855^8 * 855^32 * 855^128 * 855^512 * 855^2048 mod 3233. A Sage szerint 2868 a válasz.

Annyiban lehetne még könnyíteni a dolgon, hogy a Euler phi(3233)-at bármennyiszer levonhatod a kitevőből, ám 3233=53*61, tehát phi(3233)=52*60=3120, ami nagyobb, mint a 2735.

Az ALAPLAP c. számítástechnikai folyóiratban volt _emlékzetem szerint_ 1994-ben az egyik hónap témája a titkosítás; itt elég jól elmagyarázták az algoritmust.

egyébként a Zimmerman féle PGP titkosítás forráskódját is érdemes átnézni.

CSZ

Sorozatban felbontható ebbe:
c = (ab) (mod m) = ( (a (mod m)) * (b (mod m)) ) (mod m)

C kód:

uint64_t modexp(uint64_t base, uint64_t exp, uint64_t mod)  
{  
    uint64_t c = 1;  
      
    while(exp > 0)  
    {  
        if(exp&1)  
            c = (c*base)%mod;  
        exp >>= 1;  
        base = (base*base)%mod;  
    }  
    return c;  
} 

A lényeg, hogy a nagyszám ad nagyszám nehezen ábrázolható, viszont a modulo felbontásával általában beférsz int32-be. A fentebbi C kód meg: http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binar…

A fent írt algoritmus (egyik) magyar neve ismételt négyzetre emelés. Jegyzet az egész témáról:

http://www.cs.bme.hu/~fleiner/jegyzet/BSz2.1.5.pdf (végén)