이차잉여의 제곱근 알고리즘

이차 잉여 제곱근 구하기

이차 잉여 제곱근 알고리즘

/*   @ 이차잉여 x2 ≡  a (mod p)를 만족하는 제곱근을 구한다.   @ 초기값: 이차 비잉여 b   @ 초기값: 방정식 p - 1 = 2s * t  만족하는 s와 t 계산한다. (여기서 t 홀수)   @ 파라메터: ( a, p ) a:이차잉여, p: 소수   @ 반환값: x, p-x  */ function squareRootMod ( a, p) {     let inv_a, b, c, d, e, i, rx, s = 0, t = p - 1;     // 임의의 이차 비잉여(NQR)      do {                     b = Math.floor((Math.random()*p));                           if (b == 0) {             b++;         }     } while (isResidue(b, p));         // s와 t를 찾는다.     // ex) t=24 (11000), s=0; -> t=12, s=1 -> t=6, s=2 -> t=3, s=3(odd)       while (((t & 1) ==0)) {         s++; t >>>= 1;       }      // 초기화         inv_a = modInverse(a%p, p);     c = modExp(b, t, p);             rx = modExp(a, Math.floor((t+1)/2), p); // 업데이트 X값          for (i = 1; i < s; i++) {         e = modExp(2, s - i - 1, p);         d = modExp((rx * rx % p) * inv_a % p, e, p);         if (d == p - 1) rx = rx * c % p;   // 제곱근이 아니므로 비잉여 곱하여 업데이트         c = c * c % p;         }     return rx; }

.

예제 1. 소수 p = 17에 대한 이차잉여(QR)  a = 13,  제곱근 계산

 x² ≡ 13 ( mod 17 ) 

(1) a = 13이 이차 잉여 확인

(2) 이차 비잉여(NQR) b 계산 - (QR값이 b^(17-1)/2 ≡ 1 mod p)이기 때문에 1이 아닌 값이 NQR

      만약 b = 3,  3⁸ ≡ 1  mod 17 → QR

      만약 b = 5,  5⁸ ≡ 16  mod 17 → NQR

(3) p - 1 = 2^s * t  ( t는 홀수) 을 계산

     p - 1 = 16 = 2⁴ * 1 이므로 s = 4, t = 1

(4) 초기값: c = 5, rx = 13, 반복문의 알고리즘에 의해 rx = 9,

      나머지 x값은 p - rx = 8,

(5) 식 검증 9² ≡ 13 (mod 17) , 8² ≡ 13 (mod 17)