[JS] 소수

1. 소수인지 판별

function isPrime(n) {
  if (n <= 1) return false;
  if (n % 2 === 0 || n % 3 === 0) return false;

  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }

  return true;
}

2. 제한 숫자까지 소수 전부 구하기

function getPrimes(max) {
  const primes = Array(max + 1).fill(true);

  for (let i = 2; i * i <= max; i += 1) {
    if (primes[i]) {
      for (let j = i; i * j <= max; j += 1) {
        primes[i * j] = false;
      }
    }
  }

  return primes;
}

3. Euler's phi

3.1. 페르마 소정리와 오릴러 파이 함수의 관계

페리소마 소정리 증명

페르마 소정리는 오일러 정리에서 n이 소수인 특수한 경우입니다. 여기서 φ(n) 은 오일러 파이 함수(Euler Phi Function)으로 불리는 함수로, 1부터 n 까지 n 과 서로소인 수들의 개수입니다. p가 소수라면 φ(p) = p − 1이 됩니다.

• 오일러 파이: a^φ(n) mod n = 1 mod n
• 페르마 소정리: a^p-1 mod p = 1 mod p

3.2. 기약잉여계로 오일러 함수 증명

기약잉여계는 n과 서로소 n 이하의 정수로 이루어진 집합 M을 기약잉예계라 합니다. 위 페르마 정리를 인용하여 정리하면 다음과 같습니다.

M = {1번째 p, 2번째 p, ... , φ(n)번째 p}
aM = {a(1번째 p), a(2번째 p), ... , a(φ(n)번째 p)}
M = aM mod n
M! mod n = (a^φ(n) * M!) mod n
5. a^φ(n) mod n = 1 mod n

3.3.오일러 파이 함수는 곱셈적 함수입니다.

오일러 파이 함수의 계산을 위한 가장 중요한 성질은 오일러 파이 함수가 곱셈적 함수 라는 성질입니다. 이는 다음을 의미합니다.

φ(m)φ(n) = φ(mn) (단, m,n은 서로소)

이 사실의 증명은 조금 더 복잡합니다. 먼저 다음과 같은 m × n 의 표를 보겠습니다.

r행: r, m + r, 2m + r, ... , (n - 1)m + r

• r과 m이 서로소가 아닌 경우: r행, 즉 km + r 꼴의 모든 수는 m과 서로소가 아닙니다.
• r과 m이 서로소인 경우: r행, 즉 km + r 꼴의 모든 수는 m과 서로소입니다.

r과 m이 서로소인 경우

두 번째 케이스에 집중합니다. 두 번쨰 케이스의 경우, r행의 n개의 수들은 법 n에 대해 서로 다릅니다. 이는 귀류법으로 보일 수 있습니다.

1. i !== j인데 (im + r) mod n = (jm + r) mod n인 i, j가 존재한다고 가정합니다.
2. im mod n = jm mod n이 되고, m과 n은 서로소이므로 양변을 m으로 나눌 수 있습니다.
3. i mod n = j mod n이 되는데, i,j < n인 조건에서 i = j이 되므로 1번 가정은 모순입니다.

오일러 파이 함수 증명

r이 m과 서로소일 떄, r행의 원소들은 법 n에 대해 서로 다릅니다. 그런데 r행의 원소가 n개 존재하므로, r 행은 다음 집합과 합동입니다.

{r, m + r, 2m + r, ... , (n - 1)m + r} mod n = {0, 1, 2, ..., n - 1} mod n

0 부터 n - 1까지 모든 수가 빠짐없이 있으므로, 여기에는 n과 서로수인 φ(n)개의 수들도 빠짐없이 있을 것입니다. 그런데 애초에 r행은 모두 m과 서로소이므로 r행의 수 중 n과 서로소인 수는 mn과 서로소입니다. 한편 이런 행은 φ(m)개 존재합니다. 따라서 φ(m)φ(n) = φ(mn)이 됩니다.

3.4. 오일러 파이 함수 계산

p가 소수라면 p^k와 서로소가 아닌 수들은 반드시 p를 인수로 가져야 합니다. 1부터 p^k까지의 수 중 이런 수들은 p^k / p = p^k-1개 있습니다. 따라서 φ(p^k) = p^k - p^k-1 이 결론으로부터 우리는 쉽게 오일러 파이 함수를 계산할 수 있습니다. 모든 수는 소수의 곱으로 나타낼 수 있으므로, 소인수분해를 한 뒤 오일러 파이 함수가 곱셈적 함수임을 이용해서 계산하면 됩니다.

φ(a)
= φ((p1^k1)(p2^k2)...(pn^kn)) // 소인수분해
= φ(p1^k1) φ(p2^k2)... φ(pn^kn) // 오일러 파이 함수
= (p1^k1 - p1^k1-1)(p2^k2 - p2^k2-2)...(pn^kn - pn^kn-1) // 서로소가 아닌 수 구하기
= p1^k1 * (1 - 1 / p1) * p2^k2 * (1 - 1 /p2)...pn^kn * (1 - 1 / pn)
= p1^k1 * p2^k2...pn^kn * (1 - 1 / p1) * (1 - 1 /p2)...(1 - 1 / pn)
= a(1 - 1 / p1)(1 - 1 /p2)...(1 - 1 / pn)

/**
 * @param {number} n
 */
function eulerPhi(n) {
  let remain = n;
  let res = n;

  const eulerPhiUtil = (p) => {
    if (remain % p !== 0) return; // p는 n의 소인수
    while (remain % p === 0) remain /= p;
    res -= res / p; // res * (1 - 1 / p)
  };

  eulerPhiUtil(2);
  eulerPhiUtil(3);

  for (let i = 5; i * i <= remain; i += 6) {
    eulerPhiUtil(i);
    eulerPhiUtil(i + 2);
  }

  if (remain > 1) eulerPhiUtil(remain);
  return res;
}

4. 출처

• 정수론 (6) - 오일러의 정리와 오일러 파이 함수 - DimenErno