[수업] 11/8

x.len = n + 1

y.len = t + 1

 

큰정수 *  한워드 곱 

 

 

a  = q * b + r 

normbits 

x = a << nb

y = b << nb

 

a * 2^nb = q * b ^nb + r *2^nb

x = q * y +  r * 2 ^nb

 

---

지수승 연산 ver1

m ^ e mod n

 

m^755 mod n

r <- m

for i = 1 to 754

    r <- r * m (mod n)

 

e = (101101) = 2^6 + 2^3 + 2^2 + 1

 

m^(2^6 + 2^3 + 2^2 + 1) = ((((m^2)^ 2) * m)^2 * m) ^ 2  * m

 

input = m e n

output = m^e mod n

r <- m 

for i = n -2  to 0

     r<- r* r mod n

    if(ei == 1)

           r<- r * m mod n

return r

 

---

지수승 연산 v2

m^(2^6 + 2^3 + 2^2 + 1)

 

for i = 0 to n -1 

    if(ei  == 1)

        r <- r * x

    x <- x^2 (mod n)

return r