RSA`da hem şifreleme hem de deşifreleme, tamsayıların tamsayı kuvvetlerini almayı ve mod alma işlemlerini gerektirir. Eğer ilk önce tamsayıların üslerini alıp, daha sonra mod n ile indirgersek, ara değerler devasa büyüklükte sayılar olurlar. Neyse ki bu sorunu bir nebze azaltmak için modüler aritmetiğin şu özelliğinden yararlanabiliriz:
Bu sayede, ara değerleri modül n`e göre indirgeyebiliriz. Bu da hesaplamayı pratik hale getirir.
Diğer bir husus, üssün verimidir. Çünkü, RSA ile, potansiyel olarak büyük üsler ile işlem yaparız. Verimin nekadar artabiliceğini görmek için, `yı hesaplamak istediğimizi varsayalım. Dürüst bir yöntem 15 çarpım gerektirir:
Bununla birlikte, aynı sonuca, her bir kısmi sonucun karesini alarak
olacak şekilde dört adımda da ulaşabiliriz.
Daha genel olarak varsayalım ki biz  değerini hesaplamak istiyoruz ve biliyoruz ki a ve m birer pozitif tam sayı. Eğer biz m`i gibi ikilik sayı gibi ifade edecek olursak:
Böylece,
olur.
Bu sonuç sayesinde,  işlemini hesaplamak üzere aşağıdaki algoritmayı geliştirebiliriz. Ve algoritmanın altındaki tablo da algoritmanın çalışmasını örneklemektedir.c değerinin aslında gerekli olmadığını düşünebilirsiniz; gerçekten de algoritma içerisinde direk bir fonksiyonu yoktur. Fakat son değeri üssün değerine eşit olacağından dolayı açıklayıcı bir niteliktedir.
c<--0; d<--
for i<--k downto 0
do c<--2 x c
d<--(d x d)mod n
if bi=1
then c<--c+1
d<--(d x a)mod n
return d
aldım biyerden...
adaniak
|
Del.icio.us
Digg
Facebook
Furl
Google
Blink
Simpy
Spurl
Y! MyWeb