맨위로가기

르장드르 기호

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

1. 개요

르장드르 기호는 홀수 소수 p와 정수 a에 대해 정의되는 기호로, a가 p에 대한 제곱 잉여인지, 제곱 비잉여인지 또는 p의 배수인지에 따라 1, -1 또는 0의 값을 갖는다. 르장드르 기호는 오일러 기준을 통해 정의되거나, 르장드르의 원래 정의와 같이 명시적인 공식을 사용하여 정의될 수 있으며, 이차 상호 법칙과 같은 성질을 통해 효율적으로 계산할 수 있다. 야코비 기호, 크로네커 기호, 멱잉여 기호는 르장드르 기호를 일반화한 개념이다.

더 읽어볼만한 페이지

  • 모듈러 산술 - 이산 로그
    이산 로그는 유한군에서 이산 거듭제곱의 지수를 찾는 역함수로, 소수 p를 법으로 하는 정수 모듈러 곱셈 그룹에서 계산적으로 풀기 어려운 문제이며, 현대 암호 시스템의 안전성 기반이지만 양자 알고리즘으로 효율적 해결이 가능하여 양자 내성 암호 연구가 필요하다.
  • 모듈러 산술 - 중국인의 나머지 정리
    중국인의 나머지 정리는 여러 개의 연립 합동식의 해 존재성과 유일성에 대한 정리이며, 정수론, 대수학, 암호학 등 다양한 분야에 응용된다.
  • 수론 - 타원곡선
    타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
  • 수론 - 최소공배수
    최소공배수는 둘 이상의 정수들의 공배수 중 가장 작은 양의 정수로서, 소인수분해나 최대공약수와의 관계를 이용하여 구할 수 있으며, 분수 통분이나 기어 회전 수 계산 등 여러 분야에 응용된다.
르장드르 기호
개요
분야수론
정의
















명명 유래아드리앵마리 르장드르
도입1798년
참고힐베르트 기호(추정적으로 일반화)

2. 정의

홀수 소수 p와 정수 a에 대하여 르장드르 기호는 a가 p에 대한 제곱 잉여인지, 제곱 비잉여인지, 또는 p의 배수인지에 따라 각각 1, -1, 0의 값을 갖는다. 르장드르 기호는 \left(\frac ap\right)와 같이 표기하며, 분수와 유사한 형태를 가지지만 분수 계산과는 관련이 없다.

가우스는 ''a''가 ''p''를 법으로 하는 잔여인지 비잔여인지에 따라 ''a''R''p'', ''a''N''p'' 표기법을 사용한 반면, 르장드르 기호는 (''a'' | ''p'') 또는 (''a''/''p'')로 표기하여 인쇄상의 편의를 도모했다.

고정된 ''p''에 대해, 수열 \left(\tfrac{0}{p}\right),\left(\tfrac{1}{p}\right),\left(\tfrac{2}{p}\right),\ldots는 주기 ''p''를 갖는 주기 수열이며, '''르장드르 수열'''이라고도 불린다.

2. 1. 르장드르의 정의

홀수 소수 p와 정수 a에 대하여, 르장드르 기호는 다음과 같이 정의된다.

:\left(\frac ap\right)=\begin{cases}

1 & p\nmid a\land\exists x\in\mathbb Z\colon x^2\equiv a\pmod p \\

  • 1 & p\nmid a\land\not\exists x\in\mathbb Z\colon x^2\equiv a\pmod p \\

0 & p\mid a

\end{cases}

즉, a가 p에 대한 제곱 잉여일 때 1을, a가 p에 대한 제곱 비잉여일 때 -1을, a가 p의 배수일 때 0을 값으로 한다. 르장드르 기호는 분수처럼 생겼지만, 분수의 계산과는 관련이 없다.

르장드르의 원래 정의는 다음과 같은 명시적 공식을 사용하였다.[2]

: \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p \quad \text{ and } \quad\left(\frac{a}{p}\right) \in \{-1,0,1\}.

오일러의 기준에 따르면, 이 두 정의는 동치이다. 르장드르의 기여는 ''a'' mod ''p''의 제곱 잔여를 기록하는 편리한 ''표기법''을 도입한 데에 있다.

2. 2. 오일러 기준

오일러 기준에 따르면, 르장드르 기호는 다음과 같은 명시적 공식으로 정의되며, 이는 르장드르의 원래 정의와 동치이다.[2][9]

: \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p \quad \text{ and } \quad\left(\frac{a}{p}\right) \in \{-1,0,1\}.

3. 성질

르장드르 기호는 제곱 잉여의 성질에 대응하는 다음과 같은 항등식들을 만족한다.

:\left(\frac ap\right)\equiv a^{p(p-1)/2}\pmod p

:\left(\frac ap\right)=\left(\frac{p+a}p\right)

:\left(\frac{ab}p\right)=\left(\frac ap\right)\left(\frac bp\right)

:\left(\frac{a^2}p\right)=\begin{cases}

1 & p\nmid a \\

0 & p\mid a

\end{cases}

예를 들어, 세 번째 항등식에 따라, 두 제곱 잉여의 곱은 제곱 잉여가 된다.

만약 2,p\nmid a라면, 다음이 성립한다.

:\left(\frac ap\right)=(-1)^{\sum_{k=1}^{(p-1)/2}\lfloor ak/p\rfloor}

또한, 르장드르 기호는 이차 상호 법칙과 함께 사용하여 르장드르 기호를 효율적으로 계산할 수 있도록 하는 유용한 속성들을 가지고 있다.


  • 생성자 g \in \mathbb{F}_p^*가 주어지면, x = g^r일 때, x는 r이 짝수일 때만 이차 잉여이다. 이는 \mathbb{F}_p^*의 요소 중 절반이 이차 잉여임을 보여준다.
  • ''a''의 함수로 볼 때, 르장드르 기호 \left(\frac{a}{p}\right) 는 법 ''p''에 대한 고유한 이차(또는 2차) 디리클레 문자이다.[3]
  • 피보나치 수와 관련된 공식은 소수 판별법에 사용될 수 있다.[3]

3. 1. 기본 성질

르장드르 기호는 다음과 같은 기본 성질들을 갖는다.

  • 합동 산술에 대한 주기성을 가진다. 즉, ''a'' ≡ ''b'' (mod ''p'')이면,
  • : \left(\frac{a}{p}\right) = \left(\frac{b}{p}\right) 이다.

  • 완전 곱셈 함수이다. 즉,
  • : \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) 이다.

  • 특히, 법 ''p''에 대해 모두 제곱 잉여이거나 모두 제곱 비잉여인 두 수의 곱은 잉여이고, 잉여와 비잉여의 곱은 비잉여이다.

  • 제곱수의 르장드르 기호는 다음과 같다.
  • : \left(\frac{x^2}{p}\right) = \begin{cases} 1 & \mbox{if }p\nmid x\\ 0 & \mbox{if }p\mid x. \end{cases}

  • ''a''의 함수로 볼 때, 르장드르 기호 \left(\frac{a}{p}\right)는 법 ''p''에 대한 고유한 이차(또는 2차) 디리클레 문자이다.[3]

  • p \equiv 3 \text{ mod } 4이면, a = x^{(p+1)/4}는 이차 잉여 x의 제곱근이다. (∵ \frac{p+1}{4} + \frac{p+1}{4} = \frac{p+1}2 = \frac{(p-1)+2}{2} = \frac{p-1}2 + 1)

  • 이차 상호 법칙의 첫 번째 보조 정리에 따르면,
  • : \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} =

\begin{cases}

1 & \mbox{ if }p \equiv 1\pmod{4} \\

  • 1 & \mbox{ if }p \equiv 3\pmod{4}.

\end{cases}

  • 이차 상호 법칙의 두 번째 보조 정리에 따르면,
  • : \left(\frac{2}{p}\right) = (-1)^\tfrac{p^2-1}{8} =

\begin{cases}

1 & \mbox{ if }p \equiv 1\mbox{ or }7 \pmod{8} \\

  • 1 & \mbox{ if }p \equiv 3\mbox{ or }5 \pmod{8}.

\end{cases}

  • ''a''의 작은 값에 대한 르장드르 기호 \left(\frac{a}{p}\right) 에 대한 특수 공식은 다음과 같다.
  • 홀수 소수 ''p'' ≠ 3에 대해,
  • : \left(\frac{3}{p}\right) = (-1)^{\big\lfloor \frac{p+1}{6}\big\rfloor} =

\begin{cases}

1 & \mbox{ if }p \equiv 1\mbox{ or }11 \pmod{12} \\

  • 1 & \mbox{ if }p \equiv 5\mbox{ or }7 \pmod{12}.

\end{cases}

  • 홀수 소수 ''p'' ≠ 5에 대해,
  • : \left(\frac{5}{p}\right) =(-1)^{\big\lfloor \frac{2p+2}{5}\big \rfloor} =

\begin{cases}

1 & \mbox{ if }p \equiv 1\mbox{ or }4 \pmod5 \\

  • 1 & \mbox{ if }p \equiv 2\mbox{ or }3 \pmod5.

\end{cases}

  • 피보나치 수 ''F''''n''에 대해, ''p''가 소수이면,
  • : F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p, \qquad F_{p} \equiv \left(\frac{p}{5}\right) \pmod p
  • : 이 결과는 소수 판별법에 사용되는 뤼카 수열의 이론에 기초한다.[11]

3. 2. 이차 상호 법칙

홀수 소수 p,q에 대해 p\ne q이면, 이차 상호 법칙은 다음과 같이 표현된다.

:\left(\frac pq\right)={(-1)^{(p-1)(q-1)/4}\left(\frac qp\right)}

이는 p와 q가 p\equiv q\equiv 3\pmod 4인 경우를 제외하면 서로에 대한 제곱 잉여이거나, 서로에 대한 제곱 비잉여임을 의미한다.

르장드르 기호는 이차 상호 법칙과 함께 사용하여 효율적으로 계산할 수 있다. 예를 들어:

  • 생성자 g \in \mathbb{F}_p^*가 주어지면, x = g^r일 때 x는 r이 짝수일 때만 이차 잉여이다. 이는 \mathbb{F}_p^*의 요소 중 절반이 이차 잉여임을 보여준다.
  • p \equiv 3 \text{ mod } 4이면, a = x^{(p+1)/4}는 이차 잉여 x의 제곱근이다.
  • 르장드르 기호는 상위 인수에 대한 완전 곱셈 함수이다. 즉,
  • :\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).
  • ''a''의 함수로 볼 때, 르장드르 기호 \left(\frac{a}{p}\right) 는 법 ''p''에 대한 고유한 이차 디리클레 문자이다.
  • ''a''의 작은 값에 대한 르장드르 기호 \left(\frac{a}{p}\right) 에 대한 특수 공식은 다음과 같다.
  • 홀수 소수 ''p'' ≠ 3에 대해,
  • : \left(\frac{3}{p}\right) = (-1)^{\big\lfloor \frac{p+1}{6}\big\rfloor} =

\begin{cases}

1 & \mbox{ if }p \equiv 1\mbox{ or }11 \pmod{12} \\

  • 1 & \mbox{ if }p \equiv 5\mbox{ or }7 \pmod{12}.

\end{cases}

  • 홀수 소수 ''p'' ≠ 5에 대해,
  • : \left(\frac{5}{p}\right) =(-1)^{\big\lfloor \frac{2p+2}{5}\big \rfloor} =

\begin{cases}

1 & \mbox{ if }p \equiv 1\mbox{ or }4 \pmod5 \\

  • 1 & \mbox{ if }p \equiv 2\mbox{ or }3 \pmod5.

\end{cases}

  • 피보나치 수 ''F''''n''+1 ''Fn'' + ''F''''n''−1.}}에 의해 정의된다. ''p''가 소수이면,
  • : F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p, \qquad F_{p} \equiv \left(\frac{p}{5}\right) \pmod p.


서로 다른 홀수 소수 ''p''와 ''q''에 대해, 르장드르 기호를 사용하면 이차 상호 법칙을 다음과 같이 간결하게 표현할 수 있다.

:\left(\frac{q}{p}\right)\left(\frac{p}{q}\right) = (-1)^{\tfrac{p-1}{2}\cdot\tfrac{q-1}{2}}.

많은 이차 상호 법칙의 증명은 오일러 기준에 기반한다.

:\left(\frac{a}{p}\right) \equiv a^{\tfrac{p-1}{2}} \pmod p.

이차 상호 법칙의 다양한 증명을 위해 르장드르 기호에 대한 몇 가지 대안적인 표현이 고안되었다.

  • 가우스 합을 이용한 가우스의 증명:


::\sum_{k=0}^{p-1}\zeta^{ak^2}=\left(\frac{a}{p}\right)\sum_{k=0}^{p-1}\zeta^{k^2},\qquad \zeta = e^{\frac{2\pi i}{p}}

::\left(\frac{p}{q}\right) =\sgn\left(\prod_{i=1}^{\frac{q-1}{2}}\prod_{k=1}^{\frac{p-1}{2}}\left(\frac{k}{p}-\frac{i}{q}\right)\right).

  • 아인슈타인의 증명[7]:


::\left(\frac{q}{p}\right) =\prod_{n=1}^{\frac{p-1}{2}} \frac{\sin\left(\frac{2\pi qn}{p}\right)}{\sin\left(\frac{2\pi n}{p}\right)}.

3. 2. 1. 제1 보충 법칙


  • 1에 대한 르장드르 기호는 다음과 같이 주어진다.[3]


:\left(\frac{-1}p\right) = (-1)^{(p-1)/2} = \begin{cases} 1 & \mbox{ if } p \equiv 1 \pmod 4 \\ -1 & \mbox{ if } p \equiv 3 \pmod 4 \end{cases}

이는 홀수 소수 ''p''를 4로 나눈 나머지가 1이면 -1은 법 ''p''에 대한 이차 잉여이고, 나머지가 3이면 이차 비잉여임을 의미한다. 예를 들어, 5는 4로 나누어 나머지가 1이므로 -1은 법 5에 대한 이차 잉여이다. 반면 7은 4로 나누어 나머지가 3이므로 -1은 법 7에 대한 이차 비잉여이다.

이 법칙은 이차 상호 법칙의 첫 번째 보충 법칙이다.[3]

3. 2. 2. 제2 보충 법칙

르장드르 기호의 제2 보충 법칙은 2에 대한 르장드르 기호의 값을 설명한다. 홀수 소수 p에 대해 다음과 같이 표현된다.[3]

:\left(\frac{2}{p}\right) = (-1)^\tfrac{p^2-1}{8} = \begin{cases} 1 & \mbox{ if }p \equiv 1\mbox{ or }7 \pmod{8} \\ -1 & \mbox{ if }p \equiv 3\mbox{ or }5 \pmod{8}. \end{cases}

즉, 홀수 소수 p를 8로 나눈 나머지가 1 또는 7이면 2는 p에 대한 제곱 잉여이고, 나머지가 3 또는 5이면 이차 비잉여이다.

3. 3. 작은 정수에 대한 르장드르 기호

홀수 소수 p에 대한 작은 정수의 르장드르 기호는 다음과 같이 나타낼 수 있다.

  • \left(\frac 1p\right)=1
  • \left(\frac{-1}p\right)=(-1)^{(p-1)/2}
  • \left(\frac 2p\right)=(-1)^{(p^2-1)/8}


이러한 표현은 이차 상호 법칙과 함께 르장드르 기호를 효율적으로 계산하는 데 사용된다.

작은 값의 정수 ''a''에 대한 르장드르 기호 \left(\frac{a}{p}\right) 의 특수 공식은 다음과 같다.

  • 홀수 소수 ''p'' ≠ 3에 대해,

: \left(\frac{3}{p}\right) = (-1)^{\big\lfloor \frac{p+1}{6}\big\rfloor} =

\begin{cases}

1 & \mbox{ if }p \equiv 1\mbox{ or }11 \pmod{12} \\

  • 1 & \mbox{ if }p \equiv 5\mbox{ or }7 \pmod{12}.

\end{cases}

  • 홀수 소수 ''p'' ≠ 5에 대해,

: \left(\frac{5}{p}\right) =(-1)^{\big\lfloor \frac{2p+2}{5}\big \rfloor} =

\begin{cases}

1 & \mbox{ if }p \equiv 1\mbox{ or }4 \pmod5 \\

  • 1 & \mbox{ if }p \equiv 2\mbox{ or }3 \pmod5.

\end{cases}

3. 4. 피보나치 수와의 관계

피보나치 수 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...는 ''F''1 = ''F''2 = 1, ''F''''n''+1 = ''Fn'' + ''F''''n''−1. 와 같이 정의된다. ''p''가 소수이면, 다음이 성립한다.

:: F_{p-\left(\frac{p}{5}\right)} \equiv 0 \pmod p, \qquad F_{p} \equiv \left(\frac{p}{5}\right) \pmod p.

:예를 들어,

::\begin{align}

\left(\tfrac{2}{5}\right) &= -1, & F_3 &= 2, & F_2 &= 1, \\

\left(\tfrac{3}{5}\right) &= -1, & F_4 &= 3, & F_3 &= 2, \\

\left(\tfrac{5}{5}\right) &= 0, & F_5 &= 5, & & \\

\left(\tfrac{7}{5}\right) &= -1, & F_8 &= 21, & F_7 &= 13, \\

\left(\tfrac{11}{5}\right) &= 1, & F_{10} &= 55, & F_{11} &= 89.

\end{align}

이 결과는 소수 판별법에 사용되는 뤼카 수열의 이론에 기초한다.[3]

4. 값의 표

다음은 ''p'' ≤ 127, ''a'' ≤ 30 범위에서 홀수 소수 ''p''에 대한 르장드르 기호 \left(\frac{a}{p}\right)의 값을 나타낸 표이다.

123456789101112131415161718192021222324252627282930
3-1-10-1-101-101-101-10-1-101-101-10-1-101-10
51-1-1101-1-1101-1-1101-1-1101-1-1101-1-110
711-11-1-1011-11-1-1011-11-1-1011-11-1-1011
111-1111-1-1-11-101-1111-1-1-11-101-1111-1-1-1
131-111-1-1-1-111-1101-111-1-1-1-111-1101-111
1711-11-1-1-111-1-1-11-111011-11-1-1-111-1-1-11
191-1-11111-11-11-1-1-1-111-101-1-11111-11-11
231111-11-111-1-111-1-11-11-1-1-1-101111-11-1
291-1-11111-11-1-1-11-1-11-1-1-11-11111-1-1101
3111-111-11111-1-1-11-11-1111-1-1-1-11-1-11-1-1
371-111-1-11-11111-1-1-11-1-1-1-11-1-1-11111-11
4111-111-1-1111-1-1-1-1-11-11-111-11-11-1-1-1-1-1
431-1-11-11-1-1111-111111-1-1-11-1111-1-1-1-1-1
471111-11111-1-11-11-1111-1-11-1-111-111-1-1
531-1-11-111-1111-11-1111-1-1-1-1-1-111-1-111-1
591-1111-11-11-1-11-1-1111-11111-1-111111-1
611-1111-1-1-11-1-111111-1-111-11-1-11-11-1-1-1
671-1-11-11-1-111-1-1-11111-11-1111111-1-11-1
71111111-1111-11-1-111-1111-1-1-111-11-111
731111-11-111-1-11-1-1-11-111-1-1-1111-11-1-1-1
7911-111-1-11111-11-1-11-1111111-111-1-1-1-1
831-111-1-11-11111-1-1-111-1-1-11-11-11-1-1-1-1-1


5. 일반화

야코비 기호는 르장드르 기호를 확장한 것이고, 크로네커 기호는 야코비 기호를 더 확장한 것이다. 멱잉여 기호는 르장드르 기호를 더 높은 거듭제곱으로 일반화한 것이다.[1]

5. 1. 야코비 기호

야코비 기호는 르장드르 기호를 소수에서 임의의 홀수까지 확장한 것이다. 크로네커 기호는 이를 임의의 짝수에까지 확장한다.[1]

야코비 기호는 합성된 두 번째(아래쪽) 인자 ''n''을 허용하는 르장드르 기호의 일반화이며, 이때 ''n''은 여전히 홀수이고 양수여야 한다. 이러한 일반화는 인수 분해를 수행하지 않고 모든 르장드르 기호를 효율적으로 계산하는 방법을 제공한다.[1]

5. 2. 크로네커 기호

야코비 기호는 르장드르 기호를 소수에서 임의의 홀수까지 확장하며, 크로네커 기호는 이를 임의의 짝수 및 정수까지 확장한다.

5. 3. 멱잉여 기호

멱잉여 기호는 르장드르 기호를 더 높은 거듭제곱 ''n''으로 일반화한다. 르장드르 기호는 ''n'' = 2인 경우의 멱잉여 기호를 나타낸다.[1]

6. 역사

프랑스의 수학자 아드리앵마리 르장드르가 도입하였다.

7. 계산 예시

Legendre symbol영어의 값을 계산하는 방법에는 이차 상호 법칙을 이용하는 방법, 보다 효율적인 계산을 사용하는 방법, 모듈러 지수승을 이용하는 방법 등이 있다. Legendre symbol영어 계산에는 효율적인 모듈러 지수승 알고리즘이 존재한다.

7. 1. 이차 상호 법칙을 이용한 계산

홀수 소수 p,q에 대해 p\ne q일 때, 이차 상호 법칙에 따라 다음이 성립한다.

:\left(\frac pq\right)={(-1)^{(p-1)(q-1)/4}\left(\frac qp\right)}

즉, p와 q가

:p\equiv q\equiv 3\pmod 4

인 경우를 제외하면 서로에 대한 제곱 잉여이거나, 서로에 대한 제곱 비잉여이다.

이러한 성질들을 이용하여 르장드르 기호의 값을 계산할 수 있다. 예를 들어, \left ( \frac{12345}{331}\right )를 계산하면 다음과 같다.

:\begin{align}

\left ( \frac{12345}{331}\right )&=\left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{823}{331}\right ) \\

&= \left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{161}{331}\right ) \\

&= \left ( \frac{3}{331}\right ) \left ( \frac{5}{331}\right ) \left ( \frac{7}{331}\right ) \left ( \frac{23}{331}\right ) \\

&= (-1)\left (\frac{331}{3}\right) \left(\frac{331}{5}\right) (-1) \left(\frac{331}{7}\right) (-1)\left (\frac{331}{23}\right ) \\

&= -\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{9}{23}\right )\\

&= -\left ( \frac{1}{3}\right ) \left ( \frac{1}{5}\right ) \left ( \frac{2}{7}\right ) \left ( \frac{3^2}{23}\right )\\

&= -(1) (1) (1) (1) \\

&= -1.

\end{align}

보다 효율적인 계산 방법은 다음과 같다.

:\left ( \frac{12345}{331}\right )=\left ( \frac{98}{331}\right )=\left ( \frac{2 \cdot 7^2}{331}\right )=\left ( \frac{2}{331}\right )=(-1)^\tfrac{331^2-1}{8}=-1.

야코비 기호 문서에 르장드르 기호 계산 예시가 더 있다.

효율적인 정수 인수분해 알고리즘은 알려져 있지 않지만, 효율적인 모듈러 지수승 알고리즘은 존재하므로, 르장드르의 원래 정의를 사용하는 것이 더 효율적일 수 있다. 예를 들어,

:\begin{align}

\left(\frac{98}{331}\right) &\equiv 98^{\frac{331-1}{2}} &\pmod{331} \\

&\equiv 98^{165} &\pmod{331} \\

&\equiv 98 \cdot (98^2)^{82} &\pmod{331} \\

&\equiv 98 \cdot 5^{82} &\pmod{331} \\

&\equiv 98 \cdot 25^{41} &\pmod{331} \\

&\equiv 133 \cdot 25^{40} &\pmod{331} \\

&\equiv 133 \cdot 294^{20} &\pmod{331} \\

&\equiv 133 \cdot 45^{10} &\pmod{331} \\

&\equiv 133 \cdot 39^5 &\pmod{331} \\

&\equiv 222 \cdot 39^4 &\pmod{331} \\

&\equiv 222 \cdot 197^2 &\pmod{331} \\

&\equiv 222 \cdot 82 &\pmod{331} \\

&\equiv -1 &\pmod{331}

\end{align}

제곱 거듭제곱을 사용하여, 각 연산 후에 모듈러스를 취하여 큰 정수를 계산하는 것을 피할 수 있다.

7. 2. 모듈러 지수승을 이용한 계산

효율적인 정수 인수분해 알고리즘은 알려져 있지 않지만, 효율적인 모듈러 지수승 알고리즘은 존재한다. 따라서 일반적으로 르장드르의 원래 정의를 사용하는 것이 더 효율적이다. 예를 들면 다음과 같다.

:\begin{align}

\left(\frac{98}{331}\right) &\equiv 98^{\frac{331-1}{2}} &\pmod{331} \\

&\equiv 98^{165} &\pmod{331} \\

&\equiv 98 \cdot (98^2)^{82} &\pmod{331} \\

&\equiv 98 \cdot 5^{82} &\pmod{331} \\

&\equiv 98 \cdot 25^{41} &\pmod{331} \\

&\equiv 133 \cdot 25^{40} &\pmod{331} \\

&\equiv 133 \cdot 294^{20} &\pmod{331} \\

&\equiv 133 \cdot 45^{10} &\pmod{331} \\

&\equiv 133 \cdot 39^5 &\pmod{331} \\

&\equiv 222 \cdot 39^4 &\pmod{331} \\

&\equiv 222 \cdot 197^2 &\pmod{331} \\

&\equiv 222 \cdot 82 &\pmod{331} \\

&\equiv -1 &\pmod{331}

\end{align}

제곱 거듭제곱을 사용하여 각 연산 후에 모듈러 연산을 통해 모든 값을 줄임으로써 큰 정수를 사용한 계산을 피할 수 있다.

참조

[1] 서적 Essai sur la théorie des nombres https://archive.org/[...]
[2] 문서 Hardy & Wright, Thm. 83.
[3] 문서 Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74.
[4] 문서 Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in ''Untersuchungen ...'' pp. 463–495
[5] 문서 Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reprinted in ''Untersuchungen ...'' pp. 501–505
[6] 문서 Lemmermeyer, ex. p. 31, 1.34
[7] 문서 Lemmermeyer, pp. 236 ff.
[8] 서적 Essai sur la théorie des nombres https://archive.org/[...] 1798
[9] 문서 Hardy & Wright, Thm. 83.
[10] 논문 Trace Representation of Legendre Sequences 2001
[11] 문서 Ribenboim, p. 64; Lemmermeyer, ex. 2.25–2.28, pp. 73–74.
[12] 문서 Gauss, "Summierung gewisser Reihen von besonderer Art" (1811), reprinted in ''Untersuchungen ...'' pp. 463–495
[13] 문서 Gauss, "Neue Beweise und Erweiterungen des Fundamentalsatzes in der Lehre von den quadratischen Resten" (1818) reprinted in ''Untersuchungen ...'' pp. 501–505
[14] 문서 Lemmermeyer, ex. p. 31, 1.34
[15] 문서 Lemmermeyer, pp. 236 ff.


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

문의하기 : help@durumis.com