페르마의 소정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 역사
- 3.1. 중국 가설
4. 증명
- 4.1. 합동식을 이용한 증명
- 4.2. 이항 정리를 이용한 증명
5. 일반화
6. 성질
7. 페르마 검사 (소수 판별)
- 7.1. 밀러-라빈 소수 판별법
8. 응용
참조

1. 개요

페르마의 소정리는 소수와 정수의 관계를 나타내는 중요한 정리로, 소수 p와 정수 a에 대해 a^p와 a가 법 p에서 합동이라는 것을 의미한다. 이 정리는 a가 p로 나누어 떨어지지 않을 경우 a^p-1 ≡ 1 (mod p)로 표현될 수 있으며, 소수의 필요조건이지만 충분조건은 아니다. 페르마의 소정리는 피에르 드 페르마에 의해 언급되었지만, 고트프리트 빌헬름 라이프니츠가 최초로 증명을 제시했다.

페르마의 소정리는 오일러 정리로 일반화되며, 이는 RSA 암호 시스템과 같은 공개 키 암호화 방식에 응용된다. 또한 카마이클 함수, 카마이클의 정리, 라그랑주 정리와도 연관되어 있으며, 유한군 이론으로 확장될 수 있다. 페르마의 소정리는 난수 생성에 사용될 수 있지만, 페르마 검사를 통해 소수 판별에 활용되기도 한다. 페르마 검사는 확률적 소수 판별 알고리즘으로, 밀러-라빈 소수성 검사와 같은 개선된 알고리즘의 기반이 된다.

더 읽어볼만한 페이지

소수에 관한 정리 - 산술의 기본 정리
산술의 기본 정리는 1보다 큰 모든 양의 정수를 소수의 곱으로 유일하게 표현할 수 있다는 정리이다.
소수에 관한 정리 - 소수 정리
소수 정리는 소수 계량 함수 π(x)와 함수 x / ln x의 비율이 x가 무한히 커질수록 1에 수렴한다는 것을 나타내는, 소수의 분포에 대한 점근적 법칙이다.
모듈러 산술 - 이산 로그
이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
모듈러 산술 - 중국인의 나머지 정리
중국인의 나머지 정리는 여러 개의 연립 합동식의 해 존재성과 유일성에 대한 정리이며, 정수론, 대수학, 암호학 등 다양한 분야에 응용된다.
사람 이름을 딴 낱말 - 뒤베르제의 법칙
뒤베르제의 법칙은 선거제도와 정당 수 사이의 관계를 설명하는 가설로, 단순 다수 대표제는 양당제를, 결선투표제와 비례대표제는 다당제를 낳는다는 내용을 제시한다.
사람 이름을 딴 낱말 - 옴의 법칙
옴의 법칙은 1827년 게오르크 옴이 발표한, 전압(V)은 전류(I)와 저항(R)의 곱(V=IR)으로 표현되는, 전압, 전류, 저항 간의 관계를 나타내는 기본 법칙이다.

페르마의 소정리
개요
분야	수론
명명자	피에르 드 페르마
설명	임의의 정수 a에 대해, p가 소수이면 a^p − a는 p로 나누어 떨어진다.
세부 정보
공식 명칭	페르마의 소정리
내용	임의의 정수 a에 대하여, p가 소수일 때, a^p − a는 p의 배수이다. 즉, a^p ≡ a (mod p)이다.
다른 표현	a가 p의 배수가 아니라면, a^(p-1) − 1은 p의 배수이다. 즉, a^(p-1) ≡ 1 (mod p)이다.
예시	a = 2, p = 7일 때, 2^7 − 2 = 126 = 7 × 18이므로 7은 2^7 − 2를 나눈다.
일반화	오일러 정리 카마이클 수

2. 정의

$p$ 가 소수이고, $a$ 가 정수일 때, '''페르마의 소정리'''에 따르면 다음이 성립한다.

: $a^p \equiv a \pmod p$

만약 $a$ 가 $p$ 로 나누어 떨어지지 않는다면, 즉 $a$ 와 $p$ 가 서로소라면, 위 식의 양변을 $a$ 로 나누어 다음과 같이 쓸 수 있다.

: $a^{p-1} \equiv 1 \pmod p$

3. 역사

피에르 드 페르마의 이름이 붙었지만, 페르마는 이 정리를 언급만 했을 뿐 정확한 증명을 제시하지 않았다. 현재 기록상 남아 있는 증명 가운데 최초는 고트프리트 빌헬름 라이프니츠의 것이다.

페르마는 1640년 10월 18일 친구이자 신뢰하는 사이였던 프레니클 드 베시에게 보낸 편지에서 이 정리를 처음 언급했다. 그의 공식은 다음과 같다.^[3]

만약 p가 소수이고, a가 p로 나누어 떨어지지 않는 정수라면, a^p-1 - 1은 p로 나누어 떨어진다.

페르마의 원래 진술은 다음과 같았다.

Tout nombre premier mesure infailliblement une des puissances -1 de quelque progression que ce soit, et l'exposant de la dite puissance est sous-multiple du nombre premier donné -1; et, après qu'on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l'exposant de la première satisfont tout de même à la question.^프랑스어

이것은 더 쉬운 이해를 위해 설명과 수식을 괄호 안에 추가하여 번역할 수 있다.

모든 소수 [p]는 반드시 어떤 [기하] 수열 [a, a², a³, …]의 거듭제곱에서 1을 뺀 값 중 하나를 나눈다 [즉, t가 존재하여 p가 a^t - 1을 나눈다]. 그리고 이 거듭제곱의 지수 [t]는 주어진 소수에서 1을 뺀 값 [p-1]을 나눈다. 이 문제에 부합하는 첫 번째 거듭제곱 [t]을 찾은 후, 첫 번째 것의 지수의 배수인 모든 것들은 마찬가지로 문제에 부합한다 [즉, 첫 번째 t의 모든 배수는 동일한 속성을 갖는다].

페르마는 a가 p의 배수인 경우를 고려하지 않았고, 그의 주장을 증명하지도 않았으며, 다음과 같이 언급했을 뿐이다.^[4]

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.^프랑스어

> (그리고 이 명제는 모든 수열과 모든 소수에 대해 일반적으로 참이다. 너무 길어질까 두려워서 당신에게 증명을 보내지 않겠다.)^[5]

레온하르트 오일러는 1736년 상트페테르부르크 학술원 《강좌》에 "Theorematum Quorundam ad Numeros Primos Spectantium Demonstratio" (영어로 "소수에 관한 몇몇 정리의 증명")라는 논문에서 최초로 출판된 증명을 제공했지만,^[6]^[7] 라이프니츠는 1683년 이전의 미출판 원고에서 거의 동일한 증명을 제시했다.^[3]

"페르마의 소정리"라는 용어는 아마도 1913년 쿠르트 헨젤의 《Zahlentheorie》에서 처음 사용되었을 것이다.^[8]

Für jede endliche Gruppe besteht nun ein Fundamentalsatz, welcher der kleine Fermatsche Satz genannt zu werden pflegt, weil ein ganz spezieller Teil desselben zuerst von Fermat bewiesen worden ist.^de

> (이제 모든 유한군에서 페르마가 처음으로 증명한 매우 특별한 부분 때문에 보통 페르마의 소정리라고 불리는 기본 정리가 성립한다.)

영어에서 이 용어의 초기 사용은 A.A. 앨버트의 《Modern Higher Algebra》(1937)에서 나타나며, 206페이지에서 "소위 '작은' 페르마 정리"를 언급하고 있다.^[9]

3. 1. 중국 가설

일부 수학자들은 2^p ≡ 2 (mod p)이면 p가 소수라는 가설을 제시하였는데, 이는 '만약' 부분은 참이며 페르마의 소정리의 특수한 경우이다. 그러나 '오직 만약' 부분은 거짓이다. 예를 들어, 2³⁴¹ ≡ 2 (mod 341)이지만, 341 = 11 × 31은 밑이 2인 거짓 소수이다.

4. 증명

페르마의 소정리는 여러 가지 방법으로 증명될 수 있다.

피에르 드 페르마는 1640년 10월 18일 프레니클 드 베시에게 보낸 편지에서 이 정리를 처음 언급했다.^[3] 페르마는 증명을 제시하지 않고 다음과 같이 언급했다.^[4]

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.^프랑스어

> (그리고 이 명제는 모든 수열 [''sic'']과 모든 소수에 대해 일반적으로 참이다; 너무 길어질까 두려워서 당신에게 증명을 보내지 않겠다.)^[5]

레온하르트 오일러는 1736년에 최초로 출판된 증명을 제공했지만,^[6]^[7] 고트프리트 빌헬름 라이프니츠는 1683년 이전의 미출판 원고에서 거의 동일한 증명을 제시했다.^[3]

"페르마의 소정리"라는 용어는 1913년 쿠르트 헨젤의 저서에서 처음 사용되었을 것으로 추정된다.^[8] 영어에서는 1937년 에이브러햄 에이드리언 앨버트의 저서에서 이 용어가 나타난다.^[9]

이 정리는 오일러 정리의 따름정리로 증명될 수 있다.

4. 1. 합동식을 이용한 증명

a

와 서로소인 소수

p

에 대해

p-1

개의 수

a, 2a, 3a, \cdots, (p-1)a

를 살펴보자. 이 수들을

p

로 나눴을 때 나오는 나머지는 모두 다르다.

증명: 귀류법으로, 두 수 $ia$ 와 $ja$ 가 존재해서 그 나머지가 같다고 가정한다 ( $0 < i < j < p$ 인 정수). 그렇다면 그 두 수의 차 $(j-i)a$ 는 $p$ 로 나누어질 것이다. 그러나 $0 < j-i < p$ 이므로 $j-i$ 는 $p$ 의 배수가 아니며, $a$ 는 $p$ 와 서로소이므로 모순이다. 따라서 같은 나머지를 가지는 수는 없다.

$0 < i < p$ 인 $i$ 에 대해 $ia$ 역시 $p$ 의 배수가 아니다.

이제 집합

A = \{x | x = ia, \; i \in B\}

를 정의한다. 여기서 집합

B = \{1, 2, \cdots, p-1\}

인데,

A

와

B

의 크기는 같다.

따라서,

:

a \times 2a \times 3a \times \cdots \times (p-1)a \equiv 1 \times 2 \times \cdots \times (p-1) \not\equiv 0 \pmod p

이다. 양변을

(p-1)!

로 나누면,

:

a^{p-1} \equiv 1 \pmod p

을 얻는다.

집합

\{1, 2, 3, \ldots, p-1\}

은 법

p

에 대해

\{a, 2a, 3a, \ldots, (p-1)a\}

와 합동이다. 만약 후자의 집합 내에

:

ia \equiv ja \pmod p

가 되는

i, j

(단,

i \neq j

)가 존재한다고 하면,

a

와

p

가 서로소이므로

i \equiv j \pmod p

가 되고,

0 < i, j < p

이므로

i = j

가 되어 모순이다. 따라서 두 집합은 전체적으로 합동임을 알 수 있다.

각 집합의 모든 요소를 곱하면,

:

(p-1)! \equiv (p-1)! a^{p-1} \pmod p

가 된다.

p

가 소수이므로

p

와

(p-1)!

은 서로소이므로,

:

a^{p-1} \equiv 1 \pmod p

가 성립한다.

4. 2. 이항 정리를 이용한 증명

이항 정리를 이용하여 수학적 귀납법으로 증명하는 방법은 다음과 같다.

보조정리: "(m+1)^p를 p로 나눈 나머지는 m^p+1을 p로 나눈 나머지와 같다."

(보조정리의 증명)

:(m + 1)^p = m^p + _pC₁ m^p-1 + _pC₂ m^p-2 + ... + _pC_p-1 m + 1 (이항 정리)

우변의 양 끝을 제외한 이항 계수 _pC_k는 모두 p의 배수이다. 왜냐하면,

:_pC_k = p(p-1) ... (p-k+1) / k(k-1) ... 1

이고, p는 소수이며 k
따라서, (m+1)^p를 p로 나눈 나머지는, 양 끝의 항 m^p+1을 p로 나눈 나머지와 같다. (보조정리 증명 끝)

명제 " a^p≡ a (mod p) "를 a에 대한 수학적 귀납법으로 증명한다.

보조정리에 m=1을 대입하면, 2^p=(1+1)^p를 p로 나눈 나머지는 1^p+1=2가 되어, a=2일 때 성립한다.

명제가 a=k일 때 성립한다고 가정한다.

보조정리로부터, (k+1)^p를 p로 나눈 나머지는 k^p+1을 p로 나눈 나머지와 같다. 귀납법의 가정에 의해 k^p를 p로 나눈 나머지는 k를 p로 나눈 나머지와 같으므로, (k+1)^p를 p로 나눈 나머지는 k+1을 p로 나눈 나머지와 같다.

따라서, 명제는 a=k+1일 때도 성립한다.

수학적 귀납법에 의해, 명제는 a≥2에 대해 성립한다. 또한, a=0, 1일 때는, 대입해보면 명백히 성립하므로, 명제는 a≥0에 대해 성립한다.

(증명 끝)

5. 일반화

오일러 정리는 페르마의 소정리를 일반화한 것이다. 오일러 정리에 따르면, 임의의 법 n과 n과 서로소인 정수 a에 대해 다음이 성립한다.

: $a^{\varphi(n)} \equiv 1 \pmod n$

여기서 φ(n)는 오일러 피 함수로, 1부터 n까지의 정수 중에서 n과 서로소인 정수의 개수를 나타낸다. 페르마의 소정리는 n이 소수일 때 φ(n) = n - 1이 되므로 오일러 정리의 특수한 경우이다.

오일러 정리의 따름 정리는 다음과 같다. 모든 양의 정수 n에 대해, 정수 a가 n과 서로소이면,

: $x \equiv y \pmod{\varphi(n)} \quad \text{implies} \quad a^x \equiv a^y \pmod n$

이 식은 임의의 정수 x와 y에 대해 성립한다. n이 소수이면, 이것은 페르마의 소정리의 또 다른 따름 정리가 된다. 이는 모듈러 산술에서 큰 지수를 가진 모듈러 지수 연산을 n보다 작은 지수로 줄일 수 있기 때문에 널리 사용된다.

오일러 정리는 n이 소수가 아닌 경우 RSA 암호 시스템과 같은 공개 키 암호화 방식에서 사용된다.^[10] 만약

: $y = x^e \pmod n$

에서 y, e 및 n의 값을 알고 있다면 x를 구하는 것은 φ(n)를 알면 쉽다.^[11]

페르마의 소정리는 카마이클 함수 및 카마이클의 정리, 군론의 라그랑주 정리와도 관련이 있다. 또한, 페르마의 소정리 및 오일러의 정리는 일반적인 유한군의 정리로 확장될 수 있다. G를 위수 m인 유한군이라고 하면, G의 임의의 원소 g에 대해 g^m는 항등원과 일치한다. 오일러의 정리는 G가 곱셈군 $\left( \mathbb{Z} / n\mathbb{Z} \right)^{\times}$ 인 경우이며, 페르마의 소정리는 나아가 n이 소수인 경우이다.

5. 1. 오일러 정리

레온하르트 오일러가 피에르 드 페르마의 소정리를 확장하여 일반화한 정리이다. 오일러 정리에 따르면, 자연수 n과 n과 서로소인 자연수 a에 대해 다음 식이 성립한다.

:

a^{\varphi(n)}\equiv 1\pmod{n}

여기서

\varphi(n)

는 오일러 피 함수로, 1부터 n까지의 정수 중 n과 서로소인 정수의 개수를 나타낸다.

페르마의 소정리는 n이 소수일 때

\varphi(n) = n - 1

이 되므로 오일러 정리의 특수한 경우이다.

5. 2. 유한체론

유한체 이론에서 다항식의 나눗셈에 관련된 결과를 통해 페르마의 소정리를 일반화할 수 있다.^[15]

표수가

p

인 유한체

\mathbb F_{p^r}

에 대하여, 다음 두 명제가 성립한다.

# 기약 다항식

g\in \mathbb F_{p^r}[x]

에 대하여,

g\mid x^{p^n} - x

라면

\deg g\mid n

이다.

#

k \mid n

인 두 양의 정수

k,n\in\mathbb Z^+

에 대하여,

C(p,k)

를

g\mid x^{p^n} - x

인 k차 기약 다항식

g\in\mathbb F_{p^r}[x]

들의 수라고 하자. 그렇다면

::

\sum_{j\mid k} jC(p, j) = p^k

::이다.

여기서, 뫼비우스 반전 공식에 따라 C(p, k)를 얻는 일반적인 공식을 구하면 다음과 같다.

:

C(p, k) = \frac1k \sum_{j \mid k} \mu(j)p^{k/j}

여기서

\mu(j)

는 뫼비우스 함수이다.

5. 3. 카마이클의 정리

오일러 정리를 더 정교하게 다듬은 정리로, 법 ''n''에 대해 a^m ≡ 1 (mod n)을 만족하는 최소의 m을 제공한다. 여기서 m은 카마이클 함수(λ(n))를 이용하여 정의한다.

카마이클 함수 λ(''n'')은 다음과 같이 재귀적으로 정의된다.

n = 2^e 이면,

:

\lambda (2^e )=\begin{cases}    1 &(e=1)\\    2 &(e=2)\\    2^{e-2} &(e \ge 3)    \end{cases}

n이 홀수 소수 p를 사용하여 n = p^e 로 표현될 수 있다면,

:

\lambda(p^e) = p^{e-1}(p-1)

n이 p₁^e₁…p_k^e_k 로 소인수분해될 수 있다면,

:

\lambda(p_1^{e_1} \dotsb p_k^{e_k}) = \operatorname{lcm} \{ \lambda(p_1^{e_1}), \dotsc, \lambda(p_k^{e_k}) \}

여기서

\operatorname{lcm}

은 최소공배수이다.

카마이클의 정리는, ''a''와 ''n''이 서로소일 때,

:

a^{\lambda \left( n\right)}\equiv 1\pmod{n}

이 성립한다는 정리이다.

\lambda \left( n\right)

이 ''n''-1의 약수일 때, ''n''은 카마이클 수라고 불리며, 자신과 서로소인 모든 밑에 대해 페르마 검사를 통과하는 절대 유사 소수가 된다.

예를 들어, ''n''=10000일 때, 카마이클의 정리에 따르면 ''n''과 서로소인 모든 ''a''에 대해 a^m ≡ 1 (mod n)을 만족하는 최소의 ''m''은 500이지만, 특정 a=7에 대해서는 7¹⁰⁰ ≡ 1 (mod n)이 성립한다. 즉,

\varphi(n)

은 이 성질을 만족하는 m의 최소값이라고는 할 수 없다.

6. 성질

$p$ 가 소수이고 $a$ 가 정수이면,

: $a^{p} \equiv a \pmod p$

가 성립한다. 또한, $p$ 가 소수이고 $a$ 가 $p$ 의 배수가 아닌 정수( $a$ 와 $p$ 는 서로소)이면,

: $a^{p-1} \equiv 1 \pmod p$

가 성립한다. 즉, $a$ 의 $p-1$ 제곱을 $p$ 로 나눈 나머지는 $1$ 이다.

페르마의 소정리는 난수 생성에 사용될 수 있지만, 주의가 필요하다. 모든 ( $p$ 와 서로소인) $a$ 에 대해,

: $b = a^n \pmod p$

가, $n= 1 \cdots p-1$ 에 따라

: $1 \leq b < p$

의 모든 요소를 순차적으로 순회하는 것을 보장하는 것은 아니다.

$p=3$ 인 경우:

rowspan="2" colspan="2"\|	$n$
$1$	$2$
$a$	$1$	$1$	$1$
$a$	$2$	$2$	$1$

$p=5$ 인 경우:

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$
$a$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$3$	$1$
	$3$	$3$	$4$	$2$	$1$
	$4$	$4$	$1$	$4$	$1$

$p=7$ 인 경우:

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$	$5$	$6$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$1$	$2$	$4$	$1$
	$3$	$3$	$2$	$6$	$4$	$5$	$1$
	$4$	$4$	$2$	$1$	$4$	$2$	$1$
	$5$	$5$	$4$	$6$	$2$	$3$	$1$
	$6$	$6$	$1$	$6$	$1$	$6$	$1$

$p=11$ 인 경우:

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$8$	$5$	$10$	$9$	$7$	$3$	$6$	$1$
	$3$	$3$	$9$	$5$	$4$	$1$	$3$	$9$	$5$	$4$	$1$
	$4$	$4$	$5$	$9$	$3$	$1$	$4$	$5$	$9$	$3$	$1$
	$5$	$5$	$3$	$4$	$9$	$1$	$5$	$3$	$4$	$9$	$1$
	$6$	$6$	$3$	$7$	$9$	$10$	$5$	$8$	$4$	$2$	$1$
	$7$	$7$	$5$	$2$	$3$	$10$	$4$	$6$	$9$	$8$	$1$
	$8$	$8$	$9$	$6$	$4$	$10$	$3$	$2$	$5$	$7$	$1$
	$9$	$9$	$4$	$3$	$5$	$1$	$9$	$4$	$3$	$5$	$1$
	$10$	$10$	$1$	$10$	$1$	$10$	$1$	$10$	$1$	$10$	$1$

$p=13$ 인 경우:

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$	$12$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$8$	$3$	$6$	$12$	$11$	$9$	$5$	$10$	$7$	$1$
	$3$	$3$	$9$	$1$	$3$	$9$	$1$	$3$	$9$	$1$	$3$	$9$	$1$
	$4$	$4$	$3$	$12$	$9$	$10$	$1$	$4$	$3$	$12$	$9$	$10$	$1$
	$5$	$5$	$12$	$8$	$1$	$5$	$12$	$8$	$1$	$5$	$12$	$8$	$1$
	$6$	$6$	$10$	$8$	$9$	$2$	$12$	$7$	$3$	$5$	$4$	$11$	$1$
	$7$	$7$	$10$	$5$	$9$	$11$	$12$	$6$	$3$	$8$	$4$	$2$	$1$
	$8$	$8$	$12$	$5$	$1$	$8$	$12$	$5$	$1$	$8$	$12$	$5$	$1$
	$9$	$9$	$3$	$1$	$9$	$3$	$1$	$9$	$3$	$1$	$9$	$3$	$1$
	$10$	$10$	$9$	$12$	$3$	$4$	$1$	$10$	$9$	$12$	$3$	$4$	$1$
	$11$	$11$	$4$	$5$	$3$	$7$	$12$	$2$	$9$	$8$	$10$	$6$	$1$
	$12$	$12$	$1$	$12$	$1$	$12$	$1$	$12$	$1$	$12$	$1$	$12$	$1$

7. 페르마 검사 (소수 판별)

페르마 검사는 페르마의 소정리의 대우를 사용하여 확률적 소수 판별을 수행하는 알고리즘이다.

페르마 소정리의 대우는 다음과 같이, 자연수 ''n''이 합성수이기 위한 충분 조건을 제공한다.

: $n$ 과 서로소인 정수 $a$ 가

:: $a^{n-1} \not\equiv 1\pmod{n}$

:을 만족하면, $n$ 은 합성수이다.

이 충분 조건을 사용하여, 다음과 같이 자연수 $n$ 의 소수 판별을 수행한다.

1. 매개변수로서, $2$ 이상 $n$ 미만의 자연수 $a$ 를 1개 정한다.

2. $a$ 와 $n$ 이 서로소가 아니면 " $n$ 은 합성수"라고 출력하고 종료한다.

3. $a^{n-1} \not\equiv 1\pmod{n}$ 이면 " $n$ 은 합성수"라고 출력하고 종료한다. 그렇지 않으면 " $n$ 은 확률적 소수"라고 출력하고 종료한다.

페르마 검사가 "합성수"라고 출력했을 때, 위의 페르마 소정리의 대우에 의해 $n$ 은 실제로 합성수이다. 그러나 이 대우는 충분 조건만을 제공하고 필요 조건을 제공하는 것은 아니므로, "확률적 소수"라고 출력된 경우에도 $n$ 이 실제로 소수라고는 할 수 없다. 소수가 아님에도 "확률적 소수"로 판정되는 합성수는 '''거짓 소수'''라고 불린다.

"확률적 소수"라고 출력된 경우에는 또 다른 $a$ 를 사용하여 다시 검사를 수행한다. 충분한 횟수만큼 $a$ 를 바꿔가며 반복하면, 페르마 검사가 "확률적 소수"라고 판정한 수는 실제로 소수일 가능성이 높다.

그러나 카마이클 수 (절대 거짓 소수)는 합성수임에도 불구하고, 거의 어떤 $a$ 를 사용해도 "확률적 소수"로 판정되어 버리므로 페르마 검사는 완전한 소수 판별법은 아니다. 페르마 검사를 개선하는 알고리즘으로는 AKS 소수 판별법이 있다.

7. 1. 밀러-라빈 소수 판별법

밀러-라빈 소수 판별법은 페르마의 소정리를 확장하여 사용한다.^[14]

만약 $p$가 홀수 소수이고, $p-1 = 2^s d$ ($s>0$, $d$는 홀수)이면, $p$와 서로소인 모든 $a$에 대해, $a^d \equiv 1 \pmod p$ 이거나, $0 \le r < s$ 인 $r$에 대해 $a^{2^r d} \equiv -1 \pmod p$ 이다.

이는 페르마의 소정리에서 유도할 수 있다. $p$가 홀수 소수라면, $p$를 모듈로 하는 정수들은 유한체를 형성하고, 여기서 1 모듈로 $p$는 정확히 두 개의 제곱근, 즉 1과 -1 모듈로 $p$를 갖기 때문이다.

$a^d \equiv 1 \pmod p$는 $a \equiv 1 \pmod p$에 대해 자명하게 성립한다. 합동 관계는 지수와 호환되기 때문이다. 또한 $a^{2^0 d} \equiv -1 \pmod p$는 $d$가 홀수이므로, $a \equiv -1 \pmod p$에 대해서도 자명하게 성립한다. 따라서 보통 $1 < a < p-1$ 범위에서 무작위로 $a$를 선택한다.

밀러-라빈 검사는 이 성질을 다음과 같이 활용한다. 소수인지 판별할 홀수 $p$가 주어지면, $p-1 = 2^s d$ ($s>0$, $d$는 홀수)로 표현하고, $1 < a < p-1$인 $a$를 무작위로 선택한 뒤, $b = a^d \pmod p$를 계산한다. $b$가 1도 -1도 아니라면, -1이 나올 때까지, 또는 $s-1$번 제곱할 때까지 $p$를 모듈로 하여 제곱한다. 만약 $b \ne 1$이고 -1이 나오지 않았다면, $p$는 합성수이고 $a$는 $p$의 합성성에 대한 증인이다. 그렇지 않으면 $p$는 'base a에 대한 강한 확률적 소수'이며, 소수일 수도 있고 아닐 수도 있다.

$p$가 합성수일 때 검사가 강한 확률적 소수라고 판단할 확률은 최대 $\frac{1}{4}$이다. 이 때 $p$는 *강 의사소수*, $a$는 *강한 거짓말쟁이*라고 한다. 따라서 $k$번의 무작위 검사 후 $p$가 합성수일 확률은 최대 $4^{-k}$이며, $k$를 늘려 원하는 만큼 낮출 수 있다.

요약하면, 밀러-라빈 검사는 숫자가 합성수임을 증명하거나, 원하는 만큼 낮은 오차 확률로 소수임을 주장할 수 있다. 구현이 간단하고 알려진 모든 결정적 검사보다 계산적으로 효율적이어서, 소수성 증명을 시작하기 전에 일반적으로 사용된다.

8. 응용

페르마의 소정리는 RSA 암호 시스템과 같은 공개 키 암호화 방식의 기반이 된다.^[10] 큰 지수를 가진 모듈러 지수 연산을 보다 작은 지수로 줄일 수 있어 효율적인 계산이 가능하다.

만약

$y=x^e\pmod n,$

이고, 및 의 값을 알고 있다면, 오일러 피 함수를 알면 를 쉽게 구할 수 있다.^[11] 확장 유클리드 알고리즘을 사용하여 를 법으로 하는 의 모듈러 역원 를 계산할 수 있는데, 이는 다음을 의미한다.

$ef\equiv 1\pmod{\varphi(n)}.$

이에 따라 다음이 성립한다.

$x\equiv x^{ef}\equiv (x^e)^f \equiv y^f \pmod n.$

이 서로 다른 두 소수의 곱이면, 이다. 이 경우, 과 에서 를 찾는 것은 를 계산하는 것만큼 어렵다. 만 알고 있다면, 의 계산은 의 인수분해와 본질적으로 같은 난이도를 갖는다.

RSA 암호 시스템은 이러한 원리를 이용한다. 메시지 를 로 암호화하여 공개된 과 값을 사용하면, 현재 지식으로는 의 비밀 인자 와 를 찾지 않고는 해독하기 어렵다.

참조

_[1] 서적
_[2] 서적
_[3] 서적
_[4] 간행물 Oeuvres de Fermat. Tome 2: Correspondance https://archive.org/[...] Gauthier-Villars
_[5] 서적
_[6] 논문 Theorematum quorundam ad numeros primos spectantium demonstratio https://www.biodiver[...] 1736
_[7] 서적
_[8] 서적 Zahlentheorie https://books.google[...] G. J. Göschen 1913
_[9] 서적
_[10] 간행물 Introduction to Cryptography with Coding Theory Prentice-Hall
_[11] 문서
_[12] 웹사이트 Remainder upon division of 2^''n''−1−1 by ''n''. A128311
_[13] 논문 Démonstration de la fausseté du théorème énoncé á la page 320 du IXe volume de ce recueil http://www.numdam.or[...] 1819–1820
_[14] 서적 Primality Testing for Beginners American Mathematical Soc. 2013-12-11
_[15] 서적 Contemporary Abstract Algebra Houghton Mifflin Company(Boston, New York)

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$
$a$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$3$	$1$
	$3$	$3$	$4$	$2$	$1$
	$4$	$4$	$1$	$4$	$1$

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$	$5$	$6$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$1$	$2$	$4$	$1$
	$3$	$3$	$2$	$6$	$4$	$5$	$1$
	$4$	$4$	$2$	$1$	$4$	$2$	$1$
	$5$	$5$	$4$	$6$	$2$	$3$	$1$
	$6$	$6$	$1$	$6$	$1$	$6$	$1$

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$
$a$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$3$	$1$
	$3$	$3$	$4$	$2$	$1$
	$4$	$4$	$1$	$4$	$1$

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$	$5$	$6$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$1$	$2$	$4$	$1$
	$3$	$3$	$2$	$6$	$4$	$5$	$1$
	$4$	$4$	$2$	$1$	$4$	$2$	$1$
	$5$	$5$	$4$	$6$	$2$	$3$	$1$
	$6$	$6$	$1$	$6$	$1$	$6$	$1$

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$
$a$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$3$	$1$
	$3$	$3$	$4$	$2$	$1$
	$4$	$4$	$1$	$4$	$1$

rowspan="2" colspan="2"\|	$n$
$1$	$2$	$3$	$4$	$5$	$6$
$a$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
	$2$	$2$	$4$	$1$	$2$	$4$	$1$
	$3$	$3$	$2$	$6$	$4$	$5$	$1$
	$4$	$4$	$2$	$1$	$4$	$2$	$1$
	$5$	$5$	$4$	$6$	$2$	$3$	$1$
	$6$	$6$	$1$	$6$	$1$	$6$	$1$