토넬리-상크스 알고리즘

Tonelli-Shanks 알고리즘(Shanks가 RESSOL 알고리즘으로 칭함)은 r에² 대해 r을 frime인 r ≡ n (mod p) 형식의 합치에서 해결하기 위해 모듈식 산술에 사용된다. 여기서 p는 prime: n modulo p의 제곱근을 찾기 위해 사용된다.

Tonelli-Shanks는 합성 모듈리에 사용할 수 없다: 제곱근 모듈로 합성수를 찾는 것은 정수 인자화에 해당하는 계산적 문제다.^[1]

이 알고리즘의 등가지만 약간 더 중복된 버전은 1891년 Alberto Tonelli에^[2]^[3] 의해 개발되었다.여기서 논의된 버전은 1973년 다니엘 샨크스가 독자적으로 개발한 것으로, 그는 다음과 같이 설명했다.

내가 이러한 역사적 참고 문헌을 늦게 알게 된 것은 내가 딕슨 역사 1권을 친구에게 빌려주었기 때문인데, 그것은 결코 돌려주지 않았다.^[4]

딕슨에 따르면,^[3] 토넬리의 알고리즘은 프라임과는 별개로^λ x모듈로 프라임 파워의 제곱근을 가질 수 있다.

핵심 아이디어

0이 아닌 $n$ $n$ 과 $n$ (와) 홀수 $p$ $p$ 을 $p$ 를) 볼 때 $n$ 의 기준은 다음과 같은 경우에만 제곱근(즉, $n$ $n$ 은 $($ 즉, 2차적 잔류물 $n$ )을 $n$ 갖는다는 것을 알 수 있다.

n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

-

n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

(

n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

p

n^{\frac {p-1}{2}}\equiv 1{\pmod {p}}

)

{\

1

{\pmod{p

이와 대조적으로 $숫자$ z {\ $displaystyle$ z $}$ 에 제곱근(비재시듀)이 $z$ 없는 경우 오일러의 기준은 다음을 알려준다.

z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

-

z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

-

z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

(

z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

p

z^{\frac {p-1}{2}}\equiv -1{\pmod {p}}

)

{\

$이러한$ z $displaystyle$ $z}$ 을(를 $)$ 찾는 것은 어렵지 않다 $z$ 1과 $p-1$ - $p-1$ 사이의 정수의 절반은 이 속성을 가지고 $p-1$ 있기 때문이다 $.$ 그래서 우리는 우리가 그러한 비재고체에 접근할 수 있다고 가정한다.

(보통) 2로 나누면 $p-1$ - 1 $p-1$ 을 Q $Q2^{S}$ $Q2^{S}$ ${\$ 로 $p-1$ 쓸 수 있는데 $Q2^{S}$ $Q$ 서 Q $Q$ 은 $Q$ 홀수다.주의할 점은 다음과 같다.

R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}

R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}

R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}

+

R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}

R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}

(

R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}

R\equiv n^{\frac {Q+1}{2}}{\pmod {p}}

)

{\

then $R^{2}\equiv n^{Q+1}=(n)(n^{Q}){\pmod {p}}$ . If $t\equiv n^{Q}\equiv 1{\pmod {p}}$ , then $R$ is a square root of $n$ . Otherwise, for $M=S$ $M=S$ , 다음과 $t$ $같은$ R {\ $displaystyle$ R $R$ } $및$ t {\ $displaystyle t}$ 을(를) 만족시키십시오.

$R^{2}\equiv nt{\pmod {p}}$ $R^{2}\equiv nt{\pmod {p}}$ $R^{2}\equiv nt{\pmod {p}}$ $R^{2}\equiv nt{\pmod {p}}$ ( $R^{2}\equiv nt{\pmod {p}}$ $R^{2}\equiv nt{\pmod {p}}$ ) ${\$ ; 및
$t$ is a $2^{M-1}$ -th root of 1 (because $t^{2^{M-1}}=t^{2^{S-1}}\equiv n^{Q2^{S-1}}=n^{\frac {p-1}{2}}$ ).

위의 내용을 만족하는 $M$ $특정$ M ${\displaystyle$ $R$ $}$ 에 $t$ 대해 R {\displaystyle $R$ $}$ 및 $R$ t ${\$ $displaystyle$ $t$ $}$ 을(를) 선택할 경우(여기서 $R$ $n$ 의 제곱근은 $n$ ) M $M-1$ - $M-1$ 에 $M-1$ 대해 $다른$ $t$ R ${\displaystystyle R}$ 및t $R$ $}$ 을 쉽게 계산할 수 있다. $n$ 위의 관계가 유지되도록 $M-1$ $Playstyle M-1}$ 을(를) 반복하면 $t$ ${\displaystyle$ $t$ $}$ 이(가) $2^{0}$ 의 $2^{0}$ 0 $(\$ 2 $^{0})$ -1번째 $2^{0}$ 루트가 될 때까지 $t$ , 즉 t $t=1$ = $({\displaystystyt=$ $1$ $t=1$ 그 점에서 $R$ ${\displaystystystyle$ n}은 n $}$ 의 제곱근이다 $R$ $n$

$M-2$ $t$ 을 $t$ (를) $2^{M-2}$ $M-2$ - $2^{M-2}$ $M-2$ ${\$ $2$ $^{M-2$ $}}$ - 1의 세 번째 $2^{M-2}$ 루트인지 확인하고 1인지 확인할 $M-2$ $M-2$ 수 $있다$ .만약 그렇다면, 우리는 아무것도 할 필요가 없다. $같은$ R $R$ 과 $R$ t $t$ 의 선택이 통한다 $t$ .그러나 그렇지 않다면 $t^{2^{M-2}}$ $t^{2^{M-2}}$ - 2 ${\$ 은 -1이어야 한다 $t^{2^{M-2}}$ (스퀴링하면 1을 주고, 1모듈로 $p$ $p$ 의 제곱근 1과 -1만 있을 수 있기 때문이다). $p$

$새로운$ $R$ $R$ 및 $R$ $t$ $t$ 쌍을 찾으려면 R ${\displaystyle$ R $}$ 에 요인 $R$ b ${\displaystyle b$ 을 곱하여 결정하면 된다.Then $t$ must be multiplied by a factor $b^{2}$ to keep $R^{2}\equiv nt{\pmod {p}}$ . So we need to find a factor $b^{2}$ so that $tb^{2}$ is a ${\displaystyle 2^{M-$ ${{}{{{$ $M-2$ }}}의 -1번째 $2^{M-2}$ 루트 또는 $b^{2}$ 하게 $b^{2}$ ${\$ $b$ $^{{{$ $M-2$ $}}}}$ 는 $b^{2}$ -1의 $2^{M-2}$ - $2^{M-2}$ 루트다 $2^{M-2}$ .

여기서 비결은 알려진 비 residue인 $z$ $z$ 을(를) 이용하는 것이다.위에 나타낸 $z$ $z$ $z$ 에 적용된 오일러의 기준은 $z^{Q}$ $z^{Q}$ ${\$ 가 -1의 $2^{S-1}$ $2^{S-1}$ - $2^{S-1}$ ${\$ -throot라고 $2^{S-1}$ 되어 $z^{Q}$ 있다.그래서 $z^{Q}$ $z^{Q}$ ${\$ z $^{Q}$ 를 $z^{Q}$ 반복적으로 제곱함으로써 -1의 2 $2^{i}$ ${\$ -throot에 $2^{i}$ 접근할 수 있다. $b$ 는 b{\ $displaystyle b}$ 의 역할을 할 적절한 것을 선택할 수 있다 $b$ 약간의 가변적 유지와 사소한 사례 압축으로 아래 알고리즘이 자연스럽게 등장한다.

알고리즘

정수 modulo p $\mathbb {Z} /p\mathbb {Z}$ / p $\mathbb {Z} /p\mathbb {Z}$ {\ $displaystyle \mathb {Z} /p\mathb {Z}}$ 의 곱셈 그룹의 원소에 대한 연산 및 비교는 $\mathbb {Z} /p\mathbb {Z}$ 암시적으로 p이다.

입력:

p, prime
n $\mathbb {Z} /p\mathbb {Z}$ 합치 r² = n에 대한 솔루션이 존재하도록 $\mathbb {Z} /p\mathbb {Z}$ $\mathbb {Z} /p\mathbb {Z}$ / $\mathbb {Z} /p\mathbb {Z}$ $\mathbb {Z} /p\mathbb {Z}$ ${\$ }의 요소, 이 경우 n은 2차 잔류물 모드 p라고 한다.

출력:

$\mathbb {Z} /p\mathbb {Z}$ in Z $\mathbb {Z} /p\mathbb {Z}$ / $\mathbb {Z} /p\mathbb {Z}$ $\mathbb {Z} /p\mathbb {Z}$ ${\$ 이런 ${\mathbb {Z}}/p{\mathbb {Z}}$ ² r = n

알고리즘:

2의 힘을 감안하여 $p-1=Q2^{S}$ - 1 $p-1=Q2^{S}$ = $p-1=Q2^{S}$ $p-1=Q2^{S}$ $p-1=Q2^{S}$ ${\$ 와 $p-1=Q2^{S}$ 같은 Q와 S를 찾으십시오.
$\mathbb {Z} /p\mathbb {Z}$ / $\mathbb {Z} /p\mathbb {Z}$ $\mathbb {Z} /p\mathbb {Z}$ ${\$ 에서 ${\mathbb {Z}}/p{\mathbb {Z}}$ 2차 비residue인 z 검색
- 세트에 있는 원소의 절반은 2차 비재배율이다.
- 응시자는 오일러의 기준이나 자코비 기호를 찾아 테스트할 수 있다.
내버려두다
${\reasoned}M&\왼쪽 화살표 S\\c&\왼쪽 화살표 z^{Q}\\t&\\왼쪽 화살표 n^{Q}\\R&\왼쪽 화살표 n^{\frac {Q+1}{2}}\끝{정렬}}}}}$
루프:
- t = 0이면 r = 0 반환
- t = 1이면 r = R을 반환하십시오.
- 그렇지 않으면 $t^{2^{i}}=1$ 스퀴링을 사용하여 최소 i, 0 < i < M, t $t^{2^{i}}=1$ i = $t^{2^{i}}=1$ $t^{2^{i}=1$ 와 같은 값을 찾으십시오.
- $b\leftarrow c^{2^{M-i-1}}$ $b\leftarrow c^{2^{M-i-1}}$ $b\leftarrow c^{2^{M-i-1}}$ 2 $b\leftarrow c^{2^{M-i-1}}$ - $b\leftarrow c^{2^{M-i-1}}$ - 1 ${\$ 을 $b\leftarrow c^{2^{M-i-1}}$ 를) 설정하고 설정한다.
  ${\reasoned}M&\좌화살표 i\\\c&\좌화살표 b^{2}\\t&\좌화살표 tb^{2}\\R&\좌화살표 Rb\end{arged}}}$

$-r{\pmod {p}}$ 의 합치를 해결한 후에는 - $-r{\pmod {p}}$ r $-r{\pmod {p}}$ ( $-r{\pmod {p}}$ $){\$ t $t^{2^{i}}=1$ $t^{2^{i}}=1$ = 1 $t^{2^{i}=1$ 가 M이면 $t^{2^{i}}=1$ 합성에 대한 해법이 존재하지 않으며, 즉 n은 2차 잔류물이 아니다.

이것은 p ≡ 1 (mod 4)일 때 가장 유용하다.

p ≡ 3 (mod 4)과 같은 프리타임의 경우, 이 문제는 가능한 $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$ r $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$ = $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$ ± $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$ $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$ + 1 $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$ ( $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$ p $r=\pm n^{\frac {p+1}{4}}{\pmod {p}}$ ) ${\$ n $^{\frac {p+1}{4$ . $}}}{\pmod{p$ $r^{2}\equiv n{\pmod {p}}$ 2 $r^{2}\equiv n{\pmod {p}}$ $r^{2}\equiv n{\pmod {p}}$ p $){\$ n ${\pmod{p}}}}}$ 을(를) 만족한다면 그것만이 해결책이다 $r^{2}\equiv n{\pmod {p}}$ 그렇지 않다면 $r^{2}\equiv -n{\pmod {p}}$ $r^{2}\equiv -n{\pmod {p}}$ $r^{2}\equiv -n{\pmod {p}}$ - n $r^{2}\equiv -n{\pmod {p}}$ $r^{2}\equiv -n{\pmod {p}}$ ) ${\$ n은 2차 비재시듀이며 해결책은 없다.

증명

우리는 루프의 각 반복이 시작될 때 다음과 같은 루프 불변성이 다음을 지탱한다는 것을 보여줄 수 있다.

$c^{2^{M-1}=-1$
$t^{2^{M-1}=1$
$R^{2}=tn$

초기:

$c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ - $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ = z $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ 2 $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ - 1 $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ = $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ - $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ = $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ - $c^{2^{M-1}}=z^{Q2^{S-1}}=z^{\frac {p-1}{2}}=-1$ ${\displaystyle c^{2^{M-1}=z^{Q2^{S-1}=z^{\p-1$ }}=z $^{p-1}}{2}}=-1}($ z는 오일러의 기준에 따라 2차 비잔치 비잔치 비잔치이기 때문에)
$t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ - 1 $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ = n $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ - 1 $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ = n $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ - 1 = $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ - $t^{2^{M-1}}=n^{Q2^{S-1}}=n^{\frac {p-1}{2}}=1$ 1 = 1 ${\displaystyle$ t^{2 $^{M-1}=n^{Q-1}={$ S-1}=1 $}=n^{$ n^{\p-1}=n $^{p-1}{2}}=1}($ n은 2차 잔류물이기 때문에)
$R^{2}=n^{Q+1}=tn$

각각의 반복에서, M' , c' , t' , R'으로 M, c, t, R:를 대체하는 새로운 값을 사용한다.

$c'^{2^{M'-1}=(b^{2})^{2^{i-1}=c^{2^{M-i}2}}^{i-1}=c^{2^{M-1}=-1$
$t^{2^{M'-1}=(tb^{2})^{2^{i-1}^{2^{i-1}b^{2^{2^}}=-1\cdot -1=1$ $t'^{2^{M'-1}}=(tb^{2})^{2^{i-1}}=t^{2^{i-1}}b^{2^{i}}=-1\cdot -1=1$
- $t^{2^{i-1}}=-1$ since we have that $t^{2^{i}}=1$ but $t^{2^{i-1}}\neq 1$ (i is the least value such that $t^{2^{i}}=1$ )
- $b^{2^{i}=c^{2^{M-i-1}2}}^{i}=c^{2^{M-1}=-1$
$R'^{2}=R^{2}b^{2}=tnb^{2}=tn$

$t^{2^{M-1}}=1$ $t^{2^{M-1}}=1$ $t^{2^{M-1}}=1$ - $t^{2^{M-1}}=1$ = $t^{2^{M-1}}=1$ ${\displaystyle$ t $^{2^{M-1}=1$ } 및 루프 $t^{2^{M-1}}=1$ 시작 시 t = 1 t = $t^{2^{i}}=1$ ${\displaystyle$ t $^{2^{i}=1}.$ M은 각 반복 시 엄격히 작아져 알고리즘이 중지됨을 보증한다.조건 t = 1에 도달하고 정지하면 마지막² 루프 불변성은 R = n을 암시한다.

t순서

우리는 요소들의 순서를 이용하여 루프 불변성을 교대로 표현할 수 있다.

$\operatorname {ord}(c)=2^{M}$
$\operatorname {ord}(t) 2^{M-1$
$R^{2}=tn$ $R^{2}=tn$ = 이전과 같이 $R^{2}=tn$ $R^{2}=tn$ $R^{2}=tn$ ${\displaystyle$ R $^{2}=tn}$

알고리즘의 각 단계는 t의 정확한 순서를 측정하고 동일한 순서의 요소를 곱하여 t를 더 작은 하위 그룹으로 이동시킨다.

예

r2이 일치를 해결하려면 ≡ 5(41mod). 필요할 때 41총리는 41≡ 1(모드 4)오일러의 기준에 의해.5는 평방 잉여:541− 12=520=1{5^\displaystyle{\frac{41-1}{2}}=5^{20}=1}}은 암시적으로 mo.×{\displaystyle(\mathbb{Z}/41\mathbb{Z})^{\times}(전처럼,에서 작전(Z/41Z)d41).

$p-1=40=5\cdot 2^{3}$ - $p-1=40=5\cdot 2^{3}$ = $p-1=40=5\cdot 2^{3}$ = $p-1=40=5\cdot 2^{3}$ $p-1=40=5\cdot 2^{3}$ $p-1=40=5\cdot 2^{3}$ 3 ${\$ $Q\leftarrow 5$ Q $Q\leftarrow 5$ 5 ${\displaystyle$ Q $\leftarrow 5$ $S\leftarrow 3$ $S\leftarrow 3$ $S\leftarrow 3$ ${\displaysty s\leftarrow 3}$
z 값 찾기:
- $2^{\frac {41-1}{2}}=1$ $2^{\frac {41-1}{2}}=1$ - $2^{\frac {41-1}{2}}=1$ $2^{\frac {41-1}{2}}=1$ = 1 ${\displaystyle 2^{\frac {41-1}{2}}=1$ 따라서 2는 오일러의 기준으로 볼 때 2차 잔류물이다.
- $3^{\frac {41-1}{2}}=40=-1$ $3^{\frac {41-1}{2}}=40=-1$ - $3^{\frac {41-1}{2}}=40=-1$ $3^{\frac {41-1}{2}}=40=-1$ = $3^{\frac {41-1}{2}}=40=-1$ = $3^{\frac {41-1}{2}}=40=-1$ = $3^{\frac {41-1}{2}}=40=-1$ - 1 ${\displaystyle$ 3 $^{\frac {41-1}{2}}=40=-1$ 따라서 3은 2차 비잔상: z $z\leftarrow 3$ 3 ${\displaystyle$ z $\왼쪽$ 화살표 $3}$
세트
- $M\왼쪽 화살표 S=3}$
- $c\leftarrow z^{Q}=3^{5}=38$
- $t\leftarrow n^{Q}=5^{5}=9$
- $R\leftarrow n^{\frac {Q+1}{2}}}}}=5^{\frac {5+1}{2}}=2}$
루프:
- 첫 번째 반복:
  - $t\neq 1$ $t\neq 1$ $t\neq 1$ $[\displaystyle t\neq$ 1 $t\neq 1$ $그래서$ 아직 끝나지 않았다.
  - $t^{2^{1}}=40$ $i\leftarrow 2$ $t^{2^{1}}=40$ $t^{2^{1}}=40$ = $t^{2^{1}}=40$ ${\displaystyle$ t $^{2^{1}=40$ $t^{2^{2}}=1$ $t^{2^{2}}=1$ $t^{2^{2}}=1$ = 1 ${\displaystyle t^{2^{2}}=$ 1} 따라서 $i$ $i\leftarrow 2$ $i\leftarrow 2$ $i\leftarrow 2$
  - $b\leftarrow c^{2^{M-i-1}=38^{2^{3-2-1}=38$
  - $M\왼쪽 화살표 i=2$
  - $c\왼쪽 화살표 b^{2}=38^{2}=9$
  - $t\왼쪽 화살표 tb^{2}=9\cdot 9=40$
  - $Rb=2\cdot 38=35}$
- 두 번째 반복:
  - $t\neq 1$ $t\neq 1$ $t\neq 1$ ${\displaystyle t\neq 1$ 그래서 아직 끝나지 않았다.
  - $t^{2^{1}}=1$ $t^{2^{1}}=1$ $t^{2^{1}}=1$ = $t^{2^{1}}=1$ $t^{2^{1}=1$ 따라서 $t^{2^{1}}=1$ $i\leftarrow 1$ $i\leftarrow 1$ $i\leftarrow 1$ ${\displaystyle$ i $\왼쪽 화살표 1}$
  - $b\leftarrow c^{2^{M-i-1}=9^{2-1}=9$
  - $M\왼쪽 화살표 i=1$
  - $c\왼쪽 화살표 b^{2}=9^{2}=40$
  - $t\왼쪽 화살표 tb^{2}=40\cdot 40=1$
  - $Rb=35\cdot 9=28}$
- 세 번째 반복:
  - $t=1$ = $t=1$ ${\displaystyle t=1$ 완료. return $r=R=28$ = R $r=R=28$ = $r=R=28$ $r=R=28$

실제로 28 28² 5 (모드 41)와 (-28)≡² 13²≡ 5 (모드 41)이다.그래서 알고리즘은 두 가지 해결책을 우리의 일치에 제시한다.

알고리즘의 속도

Tonelli-Shanks 알고리즘은 (모든 가능한 입력에 대해 평균적으로 (2차 잔류물과 2차 비잔류)를 요구한다.

2m+2k+{\frac {S-1}{4}{4}+{\frac {1}{2^{S-1}-9

모듈식 곱셈, 여기서 $m$ $m$ 은 $m$ p $p$ 의 이진 표현에 있는 자릿수, $k$ $k$ 은 $k$ p $p$ 의 이진 표현에 있는 자릿수 $p$ 필요한 2차 비 residue $z$ ${\displaystyty z}$ 을 확인하여 찾을 $z$ 경우임의로 추출한 $숫자$ y $y$ 이 $y$ (가) $2차$ 비residue인 경우, 범례 기호의 (평균적으로 $)$ 2 {\ $displaystyle$ 2} $계산$ 이 필요하다 $2$ .^[5]The average of two computations of the Legendre symbol are explained as follows: $y$ is a quadratic residue with chance ${\tfrac {\tfrac {p+1}{2}}{p}}={\tfrac {1+{\tfrac {1}{p}}}{2}}$ , which is smaller than $1$ but $\geq {\tfrac {1}{2}}$ ${\displaystyle \geq {\tfrac {1}{2$ $따라서$ 평균적으로 y ${\displaystyle$ y $}$ 이(가) 2차 잔류물인지 확인해야 $y$ 한다.

이는 본질적으로 Tonelli-Shanks 알고리즘이 계수 $p$ $p$ 이(가) 무작위일 $p$ 경우, $즉$ S $S$ 이 $S$ (가) $p$ ${\displaystyp p}$ 의 이진 표현 숫자와 관련하여 특별히 크지 않을 경우, Tonelli-Shanks 알고리즘이 매우 잘 작동한다는 것을 보여준다 $p$ 위에서 설명한 바와 같이 Cipola 알고리즘은 Ton보다 잘 작동한다. $S(S-1)>8m+20$ (S - $S(S-1)>8m+20$ 1 $S(S-1)>8m+20$ ) > $S(S-1)>8m+20$ + $(\displaystyle S(S-1$ > $8m+20}$ 인 경우(및 if에만 해당 $S(S-1)>8m+20$ However, if one instead uses Sutherland's algorithm to perform the discrete logarithm computation in the 2-Sylow subgroup of $\mathbb {F} _{p}$ , one may replace $S(S-1)$ with an expression that is asymptotically bounded by ${\displaystyle O(S\l$ 옥 S/\log \log S)}가 ce≡ nQ{\displaystyle c^{e}\equiv n^{Q}.[6]을 분명하게, 한{\displaystyle e}}e를 계산한 다음 R≡ c− e/2n(Q+1)/2{\displaystyle R\equiv c^{-e/2}n^{(Q+1)/2}}R2≡ n(n}(에는 e{\displaystyle e}를 만족시킨다. 는 $n$ $n$ 이 $n$ (가) 2차 잔류물이기 때문에 2의 배수.

그 알고리즘은 이차nonresidue z{z\displaystyle}을 찾기 위해 이와 같은 a가 z{z\displaystyle}을 찾는 다항 시간 안에 머물러 알려진 바가 결정론적 알고리즘은이다. 만약 이 일반화 리만 가설은 사실이다 하지만, 이차nonresidue z<>존재하는;2ln 2⁡ p{\displaystyle z<, 2\l이 필요하다.n^{2} ${p$ ^[7] 해당 한계까지 $z$ $모든$ z $z$ 을(를) 확인할 수 있도록 하고 다항식 시간 내에 $z$ $z$ 한 z $z$ 을(를) 찾을 수 있도록 한다.그러나 이는 최악의 시나리오라는 점을 명심하십시오. 일반적으로 위에 언급된 바와 같이 $평균$ 2번의 시행에서 z $z$ 이(가) 발견된다 $z$ .

사용하다

Tonelli-Shanks 알고리즘은 제곱근 modulo a prime이 필요한 모든 프로세스에 (자연적으로) 사용될 수 있다.예를 들어 타원곡선에서 점을 찾는 데 사용할 수 있다.그것은 또한 라빈 암호체계와 2차 체의 체의 단계에서의 계산에도 유용하다.

일반화

$(\mathbb {Z} /p\mathbb {Z} )^{\times }$ (Z/ $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ Z $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ ) $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ ${\$ $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ 의 주기 그룹과 임의 정수 k번째 루트로 일반화할 수 있으며, 특히 유한장 원소의 k번째 루트를 취한다 $(\mathbb {Z} /p\mathbb {Z} )^{\times }$ ^[8]

동일한 순환 그룹에서 많은 제곱근을 해야 하고 S가 너무 크지 않으면 미리 2-전력 순서 요소의 제곱근 표를 준비할 수 있고 알고리즘은 다음과 같이 단순화 및 속도를 높일 수 있다.

Q와 S를 다음과 같이 정의하면서 p - 1에서 2의 힘을 빼십시오 $p-1=Q2^{S}$ : p $p-1=Q2^{S}$ - $p-1=Q2^{S}$ = Q $p-1=Q2^{S}$ S ${\$
$R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ Q $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ + $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ , $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ $R\leftarrow n^{\frac {Q+1}{2}},t\leftarrow n^{Q}\equiv R^{2}/n$ / n ${\displaystyle R\leftarrow n^{\q+$ 1}{ $2}}, t\leftarrow n^{Q}\equiv$ R $^{2}/n}$ 를 두십시오.
$b^{2}\equiv t$ 에서 b $b$ 2 $b^{2}\equiv t$ t {\ $displaystyle b^{2$ }\ $equiv$ t $}$ 과(와) 같은 $b$ $b$ 을(를) 찾고 $b^{2}\equiv t$ $R\equiv R/b$ $R\equiv R/b$ $R\equiv R/b$ / b $R\equiv R/b$ 을(를) 설정하십시오.
R을 반환하다.

토넬리의 알고리즘은 mod p^k에서 작동할 것이다.

딕슨의 "숫자의 이론"^[3]에 따르면

A. 토넬리는^[9] x $x^{2}=c({\bmod {p^{\lambda }}})$ = $x^{2}=c({\bmod {p^{\lambda }}})$ ( $x^{2}=c({\bmod {p^{\lambda }}})$ $x^{2}=c({\bmod {p^{\lambda }}})$ $){\displaystyle$ x $^{2}=c({\bmod {p^{\lambda }}}}}}$ 의 뿌리에 대해 명시적인 공식을 주었다.

딕슨 참조는 x 2 $x^{2}{\bmod {p^{\lambda }}}$ p ${\$ 의 제곱근에 대한 다음 공식을 보여준다 $x^{2}{\bmod {p^{\lambda }}}$

p=4*7+1

=

p=4*7+1

p=4*7+1

7

p=4*7+1

+ 1

{\displaystyle p=4*7+1

}

p=4*7+1

s=2

s=2

= 2

{\displaystyle s=2

이 방정식의 경우 반드시 2여야 함) 및

A=7

=

A=7

A=7

29 =

29=2^{2}*7+1

29=2^{2}*7+1

29=2^{2}*7+1

+

29=2^{2}*7+1

{\displaystystyle 29=2^{2}*7+

1}인 경우

A=7

x^{2}{\bmod {p^{\lambda }}}\equiv c

x^{2}{\bmod {p^{\lambda }}}\equiv c

x^{2}{\bmod {p^{\lambda }}}\equiv c

x^{2}{\bmod {p^{\lambda }}}\equiv c

c

{\displaystyle x^{2}{\bmod {p^{\p

^da

}}\equiv

c

}

의 경우

x{\bmod {p^{\lambda }}}\equiv \pm (c^{A}+3)^{\beta }*c^{(\beta +1)/2}

where

\beta \equiv a*p^{\lambda -1}

$23^{2}{\bmod {29^{3}}}\equiv 529$ $23^{2}{\bmod {29^{3}}}\equiv 529$ $23^{2}{\bmod {29^{3}}}\equiv 529$ $23^{2}{\bmod {29^{3}}}\equiv 529$ $23^{2}{\bmod {29^{3}}}\equiv 529$ $23^{2}{\bmod {29^{3}}}\equiv 529$ $23^{2}{\bmod {29^{3}}\equiv 529$ 을(를) 주목한 $23^{2}{\bmod {29^{3}}}\equiv 529$ 후 $\beta =7*29^{2}$ = 7 $\beta =7*29^{2}$ 29 $\beta =7*29^{2}$ 2 {\ $displaystyle \beta = 7*29$ ^{2}을 $\beta =7*29^{2}$ $($ 를)에 주목한 후

(529^{7}+3)^{7*29^{2}}*529^{(7*29^{2}+1)/2}{\bmod {29^{3}}\equiv 24366\equiv -23

다른 $2333^{2}{\bmod {29^{3}}}\equiv 4142$ 예시: $2333^{2}{\bmod {29^{3}}}\equiv 4142$ 2 $2333^{2}{\bmod {29^{3}}}\equiv 4142$ $2333^{2}{\bmod {29^{3}}}\equiv 4142$ $2333^{2}{\bmod {29^{3}}}\equiv 4142$ $2333^{2}{\bmod {29^{3}}}\equiv 4142$ $2333^{2}{\bmod {29^{3}}}\equiv 4142$ $2333^{2}{\bmod {29^{3}}\equiv 4142$ 및

(4142^{7}+3)^{7*29^{2}}*4142^{(7*29^{2}+1)/{\bmod {29^{3}}\equiv 2333

딕슨은 또한 다음과 같은 방정식을 토넬리에게 돌렸다.

X{\bmod {p^{\lambda }}}\equiv x^{p^{\lambda -1}}*c^{(p^{\lambda }-2p^{\lambda -1}+1)/2}

where

X^{2}{\bmod {p^{\lambda }}}\equiv c

and

{\displaystyle x^{2}{\bmod {

p}\equiv c}

;

$p=23$ = $p=23$ $p=23$ 을 $p=23$ (를) 사용하고 $p^{3}$ $p^{3}$ ${\$ 의 계수를 사용하면 산술은 다음과 $p^{3}$ 같다.

1115^{2}{\bmod {23^{3}}=2191

먼저 일반 Tonelli 알고리즘으로 수행할 수 있는 $p$ 모듈식 제곱근 $mod$ p $p$ 을(를) 찾으십시오.

1115^{2}{\bmod {23}}\equiv 6

1115^{2}{\bmod {23}}\equiv 6

1115^{2}{\bmod {23}}\equiv 6

1115^{2}{\bmod {23}}\equiv 6

1115^{2}{\bmod {23}}\equiv 6

1115^{2}{\bmod{23}\equiv 6

따라서

1115^{2}{\bmod {23}}\equiv 6

{\sqrt {6}}{\bmod {23}}\equiv 11

{\sqrt {6}}{\bmod {23}}\equiv 11

{\sqrt {6}}{\bmod {23}}\equiv 11

{\sqrt {6}}{\bmod {23}}\equiv 11

{\displaystyle{\sqrt{6}{\bmod {23}\equiv 11}

그리고 Tonelli의 방정식을 적용한다(위 참조).

11^{23^{2}}*2191^{23^{3}-2*23^{2}+1)/{\bmod{23^{3}}\equiv 1115

딕슨의 참고문헌은^[3] 토넬리의 알고리즘이 $p^{\lambda }$ ${\$ 의 moduli에서 작동한다는 것을 분명히 보여준다 $p^{\lambda }$

메모들

^ Oedded Goldreich, Computing complexity: 개념적 관점, Cambridge University Press, 2008, 페이지 588.
^ Volker Diekert; Manfred Kufleitner; Gerhard Rosenberger; Ulrich Hertrampf (24 May 2016). Discrete Algebraic Methods: Arithmetic, Cryptography, Automata and Groups. De Gruyter. pp. 163–165. ISBN 978-3-11-041632-9.
^ ^a ^b ^c ^d ^e Leonard Eugene Dickson (1919). History of the Theory of Numbers. Vol. 1. Washington, Carnegie Institution of Washington. pp. 215–216.
^ 대니얼 샨크스다섯 개의 숫자-이론 알고리즘.제2차 수치 수학 매니토바 회의의 진행.1973년 페이지 51-70.
^ 곤살로 토르나리아 - 제곱근 모둘로 p, 2페이지 https://doi.org/10.1007%2F3-540-45995-2_38
^ Sutherland, Andrew V. (2011), "Structure computation and discrete logarithms in finite abelian p-groups", Mathematics of Computation, 80 (273): 477–500, arXiv:0809.3413, doi:10.1090/s0025-5718-10-02356-2, S2CID 13940949
^ Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55 (191): 355–380, doi:10.2307/2008811, JSTOR 2008811
^ 애들먼, L. M., K. 맨더스, G. 밀러: 1977, '유한 분야에 뿌리를 내리고 있다'인: 제18회 IEEE 컴퓨터 과학 기초 심포지엄. 페이지 175-177
^ "로마, 나치오날레 데이 린시 아카다비아.렌디콘티(5), 1, 1892, 116-120."

참조

Ivan Niven; Herbert S. Zuckerman; Hugh L. Montgomery (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley. pp. 110–115. ISBN 0-471-62546-9.
대니얼 샨크스다섯 개의 숫자 이론 알고리즘.제2차 수치 수학 매니토바 회의의 진행.1973년 페이지 51-70.
알베르토 토넬리, 베메르콩 über die Auflösung 4ratischer Congruenzen.나흐리히텐 폰 데르 쾨니글리첸 게셀리첸 샤프트 데르 위센샤프텐과 데르 게오르크 아우구스트 주 쾨팅겐페이지 344–346. 1891.[1]
가간 타라난다 - 수학 115:RESSOL 알고리즘 [2]
곤살로 토르나리아[3]

[1] Oedded Goldreich, Computing complexity: 개념적 관점, Cambridge University Press, 2008, 페이지 588.

[DiekertKufleitner2016-2] Volker Diekert; Manfred Kufleitner; Gerhard Rosenberger; Ulrich Hertrampf (24 May 2016). Discrete Algebraic Methods: Arithmetic, Cryptography, Automata and Groups. De Gruyter. pp. 163–165. ISBN 978-3-11-041632-9.

[dickson-3] Leonard Eugene Dickson (1919). History of the Theory of Numbers. Vol. 1. Washington, Carnegie Institution of Washington. pp. 215–216.

[4] 대니얼 샨크스다섯 개의 숫자-이론 알고리즘.제2차 수치 수학 매니토바 회의의 진행.1973년 페이지 51-70.

[5] 곤살로 토르나리아 - 제곱근 모둘로 p, 2페이지 https://doi.org/10.1007%2F3-540-45995-2_38

[6] Sutherland, Andrew V. (2011), "Structure computation and discrete logarithms in finite abelian p-groups", Mathematics of Computation, 80 (273): 477–500, arXiv:0809.3413, doi:10.1090/s0025-5718-10-02356-2, S2CID 13940949

[7] Bach, Eric (1990), "Explicit bounds for primality testing and related problems", Mathematics of Computation, 55 (191): 355–380, doi:10.2307/2008811, JSTOR 2008811

[8] 애들먼, L. M., K. 맨더스, G. 밀러: 1977, '유한 분야에 뿌리를 내리고 있다'인: 제18회 IEEE 컴퓨터 과학 기초 심포지엄. 페이지 175-177

[9] "로마, 나치오날레 데이 린시 아카다비아.렌디콘티(5), 1, 1892, 116-120."

[1]

[2]

[3]

[4]

[5]

[7]

[8]

[9]

v t 수이론적 알고리즘
원시성 검정	AKS APR 바일리-PSW 타원곡선 포클링턴 페르마 루카스 루카스-레머 루카스-레머-리젤 프로트의 정리 페핀스 이차적 프로베니우스 솔로베이-스트라센 밀러-라빈
프라임 생성	앳킨의 체 에라토스테네스의 체 순다람의 체 휠 인자화
정수 인자화	지속분수(CFRAC) 딕슨스 Lenstra 타원 곡선(ECM) 오일러즈 폴라드 호 p − 1 p + 1 2차 체(QS) 일반수 필드 체(GNFS) 특수수 필드 체(SNFS) 이성 체 페르마츠 샨크스의 사각형 재판분할 쇼르스
곱하기	고대 이집트인 긴 카라츠바 툼-쿡 sch나게-스트라센 총통의
유클리드 주 나누기	이진수 청킹 푸리에 골드슈미트 뉴턴-래프슨 긴 짧다 SRT
이산 로그	베이비 스텝 거인 스텝 폴라드 로 폴라드 캥거루 포흘리그-헬먼 지수 미적분학 기능장 체
최대공통점	이진수 유클리드 주 확장유클리드 르메르스
모듈형 제곱근	시폴라 포클링턴스 토넬리-상크스 베를레캄프 쿠네르스
기타 알고리즘	차크라발라 코르나키아 제곱에 의한 지수화 정수 제곱근 정수 관계(LL; KZ) 모듈형 지수 몽고메리 환원 슈프
이탤릭체는 알고리즘이 특수형태의 숫자에 대한 것임을 나타낸다.

Search