제곱수의 합동 성질임의의 b에 대해b^2 ≡ (m-b)^2 (mod m)증명(m-b)^2 ≡ m^2 -2mb + b^2 ≡ 0 + 0 + b^2 (mod m)따라서 b^2 ≡ (m-b)^2 (mod m)즉, 제곱수의 합동을 계산하려면 대충 반절까지만 보면 된다.m = 홀수: 1~(p-1)/2 까지 보고 이후는 대칭m = 짝수: 1~p/2 까지 보고 p/2 기준으로 대칭 이차잉여이차잉여(QR): mod p에 대해 어떤 제곱수와 합동인 수 즉, 어떤 b가 존재하여 a ≡ b^2 (mod p)라면 a는 p의 이차잉여이다.이차비잉여(NR): mod p에 대해 어떤 제곱수와 합동이 아닌 수 즉, a ≡ b^2 (mod p)인 b가 존재하지 않는다면 a는 p의 이차비잉여이다.0은 QR도 NR도 아니다.예..