[정수론](14)[소수의 성질과 라빈-밀러 판정법]

 

소수의 성질

적당한 소수 p, 홀수 q에 대해
p - 1 = 2^k*q 꼴이라면 p∤a인 임의의 수 a에 대해 적어도 1개가 참이다.

• a^q ≡ 1 (mod p)
• a^q, a^2q, a^3q, ..., a^(2^(k-1)*q) 중 1개는 mod p에서 -1과 합동
• 증명
  페르마의 소정리에 의해 a^p-1 ≡ 1 (mod p)
  따라서 a^(2^k*q) ≡ 1 (mod p)
  • case 1: a^q ≡ 1 (mod p) 이라면?
    a^q(2^k) ≡ 1^(2^k) ≡ 1 (mod p)이므로 만족한다.
  • case 2: a^q !≡ 1 (mod p) 이라면?
    a^(2^k*q) ≡ 1 (mod p) 이므로
    a^q, a^2q, a^3q, ..., a^(2^(k-1)*q) 중 제일 마지막 수가 1과 합동이다.
    따라서 제곱하면 1과 합동이 되는 수 a^?q가 존재한다.
    이때 a^q !≡ 1 (mod p) 이므로 -1과 합동인 수가 존재한다.

 

라빈-밀러 합성수 판정법

소수의 성질의 대우.

홀수 n, q에 대해
n - 1 = 2^k*q 꼴에서 n∤a인 임의의 수 a에 대해 다음 두 명제가 참이면 n은 합성수다.

• a^q !≡ 1 (mod p)
• a^q, a^2q, a^3q, ..., a^(2^(k-1)*q) 중 mod p에서 -1과 합동이 없다.

라빈-밀러 증인: n이 합성수임을 확인해주는 a
    만약 n이 홀수인 합성수라면, 라빈-밀러 증인은 1~n-1에 75% 확률로 증인이다.
    즉 여러 a를 잡고 다 라빈-밀러 증인이 아니라면 n은 홀수일 확률이 매우 높다
예) 100개의 서로 다른 임의의 a를 고르고 증인이 아무도 안나왔다면,
    n이 합성수일 확률은 0.25^100, 약, 6*10^-1 보다 더 작다.