[10 / 25] 수업

0 <= a <= 2^32 -1

0 <= b <= 2^32 -1

-(2^33) <= a-b <= 2^32 -1

 

 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

-----------------------------------------

   0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  0 0

 

이 경우일 때 len 을 정확히 표현을 해줘야한다. 

 

 

input 

0 <=a  b<= p

output 

a+b mod p

 

uadd(c ,a ,b);

if(compare_mpz(c, p) == 0)

           usub(r,c p);

 

0 <= C[i+j] <= 2^32 -1

0 <= A[i] , B[j] <= 2^32 -1

0 <= U <= 2^32 -1

 

0 <= C[i+j] + A[i]*B[j] + U <= (2^32 -1) + (2^32 -1)^2 + 2^32 -1 = 2^64 - 1 

 

 

a = a1 * 2^32 + a0

b = b1 * 2^32 + b0

 

a1b1 * 2^64 + (a1b0 + a0b1) * 2^32 + a0b0

 == a1b1 * 2^64 +{(a0 + a1)*(b0 + b1) - a0b0 * a1b1} * 2^32 + a0b0