[수업] 11/01

x - > x ^ e (mod n)

 

 

for i = n-1 to 0 

     R < - R * R (mod n)

     if (ei = 1) R <- R * x (mod n)

return R

 

=> 비트 스캔 => x* y mod n 을 구현할 줄 알아야함 

 

 

큰 정수 나머지 구현 

=> void udiv(mpz * a , mpz *b mpz *g , mpz *r)

 

1) 자리수 맞추기 => 각각의 워드에 자리수를 맞추어줘야 계산이 가능하다. 

2) 추정몫 q` 계산

3) 추정몫에 대한 보정 수행 

  - 과정 2)에서 추정된 몫이 과하게 계산 될시 다시 시행 

 

2번과정 -> 두개의 크기를 비교해야하기 때문에 bit shift 연산을 해서 계산을 해준다. 그래서 shift 연산한 yb의 값이 더 작을 시에는 몫을 늘려가면서 계속 크기 비교를 한다. 그러나 최악의 경우(나누는 값이 1이고 나눠지는 값이 0xffff ffff이경우) for문에 2^32 - 1 만큼 돌아갈 수 있기 때문에 추후 보정작업이 필요하다. 따라서 최상위 워드의 비트의 최상위 비트를 1로 세팅을 해야한다. 따라서 y의 최상위 비트를 스캔을 하고 최상위 비트가 1로 바뀌게 하면된다.  

 

x = q *y + r

x * 2^k = q*y * 2^k + r *2^k

x * 2^k = q*(y * 2^k) + (r *2^k)

X = Q * Y + R (q = Q , R >> k = r)

 

 

그리고 추후에 다음 값을 계산하게 되면 q는 기존의 계산과 동일하고 r* 2^k 만 문제인데 이때 r값을 k만큼 bit shift를 하면 된다. 

 

다시 말해서 나누는 수의 최상위 워드의 최상위 비트는 무조건 1이어야 한다. 이때 k의 값은 y의 최상위 비트가 1이 되게 되는 shift가 된다. 이 shift 된 수가 여기서 알고리즘 1의 입력으로 들어가게 된다! (입력값을 normalization을 하는 과정이라고 한다.)

 

 

---

 

normalization(a ,b); => a<< k , b<<k 이때 k는 b의 최상위 워드에서 최상위 비트를 1로 만들기 위한 비트 

 

return q , r, >> k

 

a = q*b +r

(a << k) = q * (b<<k) + (r<<k)

 

---

bit shift big integer 

r->dat[a -> len -1] = (a->dat[a->len] << shift) || (a->dat[a->len -2] >> 32-shift)

 

어렵다; 

 

 

---

 

n + 1 = x->len

n = x->len - 1

t = y->len -1

 

 

3.3과 3.4구현