베를캄프-라빈 알고리즘

수 이론에서 베를캄프-라빈 알고리즘이라고도 하는 베를캄프의 뿌리 찾기 알고리즘은 필드 $Z{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$를 통해 다항식의 뿌리를 찾는 확률론적 방법이다.이 방법은 Elwyn Berlekamp에 의해 유한 분야에 대한 다항식 인자화 알고리즘의 보조로서 1970년에^[1] 발견되었다.이 알고리즘은 1979년 라빈에 의해 임의의 유한 분야에 대해 수정되었다.^[2]이 방법은 베를캄프 이전에 다른 연구자들에 의해 독자적으로 발견되기도 했다.^[3]

역사

이 방법은 Elwyn Berlekamp가 1970년 그의 유한 분야에 대한 다항식 인자화에 관한 연구에서^[1] 제안한 것이다.그의 원작은 형식적인 정확성 증명이^[2] 결여되어 있었고 후에 마이클 라빈에 의해 임의의 유한 분야를 위해 다듬어지고 수정되었다.^[2]1986년 레네 페랄타는 Z ${\displaystyle {}_{}}$ ${\$} $_{p}}$에서 제곱근을 찾기 위한 유사한^[4] 알고리즘을 제안했고$,$^[5] 2000년 페랄타의 방법은 입방정식에 대해 일반화되었다.^[6]

문제명세서

$p{\displaystyle }$ ${\displaystyle p}$을(를) 홀수 소수 정수로 두십시오.다항식 $f($ $x$)$$= ${0\mathrm{}}_{}$+ ${}_{}$ ${x\mathrm{}}_{}$ +$\cdots$+ $n_{}$ $x^{}$ n ${\$을 고려하십시오.$}x+\cdots +a_{n}x^{n$}}} 필드 위에$$}$x$ ${$n$}$ remainders $modulo{\displaystyle }$ p ${\displaystyle$ p$\}\{$$p}.$알고리즘은 Z ${\displaystyle {}_{}}$ ${\$에서 모든 ${\displaystyle$ $\$$lambda }$을(를) $\mathrm{찾아야}$ 하며, 이러한$$ $f(\lambda )$= 0 ${\textstyle$ f$(\lambda )=0}$은 Z p ${\dmathb$ {Z}$_{p$^[2][7]

알고리즘.

무작위화

렛 $f$( $x$)$$=$$( x$$- ${}_{}$ ${1\mathrm{}}_{}$) ($x$- ${}_{}$ $2_{}{}_{}$) $\cdots$( $x$- ${}_{}$ n${}_{}$) ${\textstyle f(x)=(x-\lambda _{1})(x-$\lambda $_{2})\cdots(x-$\lambda$_{n$})$$. 이 다항식의 모든 루트를 선형 인자로 찾는 것과 같다.그러한 인자를 찾으려면 다항식을 두 개의 비삼항 분자로 분할하고 재귀적으로 인자를 지정하는 것으로 충분하다.To do this, consider the polynomial ${\textstyle f_{z}(x)=f(x-z)=(x-\lambda _{1}-z)(x-\lambda _{2}-z)\cdots (x-\lambda _{n}-z)}$ where ${\displaystyle z}$ is some any element of ${\displaystyle \mathbb {Z} _{p}}$. If one can represent this polynomial as the product ${\displaystyle f_{z}(x)=p_{0}(x)p_{1}(x)}$ then in terms of the initial polynomial it means that ${\displaystyle f(x)=p_{0}(x+z)p_{1}(x+z)}$, which provides needed factorization of ${\displaystyl$$e f(x)}$^[1][7].

$Z{\displaystyle {\mathbb{}}_{}}$ ${\displaystyle {}_{}}$ ${\$ 요소의$$ 분류

오일러의 기준으로 볼 때, 모든 모노믹$({\displaystyle x}$ -${\displaystyle )}$ ) ${\displaystyle(x-\lambda$)}에 대해 다음 속성 중 하나가$$ 정확히 유지된다.^[1]

1. ${\displaystyle \mathrm{\lambda }}$= 0 ${\displaystyle \lambda =0$인 경우 $단수{\displaystyle }$ 값은 x ${\displaystyle x}$과 같다.
2. $\lambda {\displaystyle }$ ${\displaystyle \lambda$}이$$(가) 2차적 잔류물 $모듈$로$$p {\$displaystyle$p}인$$ 경우 단수형은 ${g\mathrm{}}_{}$ $0{}_{}(x^{}-$ $1^{}$)${}^{}$=$$($x$)=(x$^{(p-1)/2-1)-1)}}}}}}$을 나눈다$.$
3. ▼ ${\displaystyle \lambda }$이$($가) 2차 비잔상 $모듈$로 p ${\displaystyle p}$인 경우$$, 단수형은 g $($ $x$ ${(p}^{}$-$1$)${}^{}$=${2\mathrm{}}^{}$ + $1$($2$+ $1$)로 나눈다$.$

Thus if ${\displaystyle f_{z}(x)}$ is not divisible by ${\displaystyle x}$, which may be checked separately, then ${\displaystyle f_{z}(x)}$ is equal to the product of greatest common divisors ${\displaystyle \gcd(f_{z}(x);g_{0}(x))}$ and ${\displaystyle gcd(f_z(}$${\displaystyle x}$)${\displaystyle }$; ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ (${\displaystyle {}_{}x}$)${\displaystyle \gcd(f_{z}(x);g_{1}(x)}$^[7].

베를레캄프의 방법

위의 속성은 다음과 같은 알고리즘으로 이어진다.^[1]

1. $f{\displaystyle {}_{}}$ ${\displaystyle z_{}}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle f(}$ ${\displaystyle x}$- ${\displaystyle z}$) ${\displaystyle f_{z}(x)=f(x-z$
2. Calculate remainders of ${\textstyle x,x^{2},x^{2^{2}},x^{2^{3}},x^{2^{4}},\ldots ,x^{2^{\lfloor \log _{2}p\rfloor }}}$ modulo ${\displaystyle f_{z}(x)}$ by squaring the current polynomial and taking remainder modulo ${\displaystyle f_z}$${\displaystyle (}$ x${\displaystyle }$) ${\displaystyle f_{z}(x$
3. 이전 단계에서 계산된 제곱 및 다항식을 통한 지수를 ${사용}^{}$하여 $x{}^{}$( $p^{}$- $1^{}$)${}^{}$/ 2 ${\$ x$^{(p-1)/2}}$ modulo$$ $f{}_{}$ $z_{}$( $x$) ${\textstyle f_{z}(x)}$의 나머지를 계산하십시오$.$
4. If ${\textstyle x^{(p-1)/2}\not \equiv \pm 1{\pmod {f_{z}(x)}}}$ then ${\displaystyle \gcd }$ mentioned above provide a non-trivial factorization of ${\displaystyle f_{z}(x)}$,
5. 그렇지 않으면 f${\displaystyle {}_{}{z}_{}}$ ( ${\displaystyle x}$)$${\$displaystyle f_{z}(x)}$의 모든 루트가 동시에 잔여물 또는 비재료가 되며$$, $다른{\displaystyle }$ z ${\displaystyle$ z$}$를 선택해야 한다$.$

If ${\displaystyle f(x)}$ is divisible by some non-linear primitive polynomial ${\displaystyle g(x)}$ over ${\displaystyle \mathbb {Z} _{p}}$ then when calculating ${\displaystyle \gcd }$ with ${\displaystyle g_{0}(x)}$ and ${\displaystyle g_{1}(x)}$ one w$f{\displaystyle {}_{}}$ ${\displaystyle z_{}}$( ${\displaystyle x}$)${\displaystyle }$/ ${\displaystyle g{}_{}}$ z${\displaystyle {}_{}}$( ${\displaystyle x}$)의 비경쟁 인자화(non-trivial factorization$){\displaystyle f_{z}(x)/g_{z}(x)}$의 모든 루트를 Z $p{\displaystyle {\mathbb{}}_{}}$ ${\$ {$Z} _{p}$에서 찾을 수 있도록 알고리즘이 허용된다$.$

모듈형 제곱근

$\beta {\displaystyle }$ ${\displaystyle$ \$beta }$${\displaystyle }$및$$ - ${\displaystyle \beta }$ ${\displaystyle \beta }$ 요소를 루트로$$ 하는 방정식$$ x ${2\mathrm{}}^{}$≡$a$ $(\mathrm{mod}$ $p$) ${\$ x$^{2}\pmod{p}}}}$을(를$)$로 간주한다.Solution of this equation is equivalent to factorization of polynomial ${\textstyle f(x)=x^{2}-a=(x-\beta )(x+\beta )}$ over ${\displaystyle \mathbb {Z} _{p}}$. In this particular case problem it is sufficient to calculate only ${\displayst$$yle \gcd(f_{z}(x);g_{0}(x$ 이 다항식에는 다음 속성 중 하나가 정확히 들어 있다.

1. GCD는 $1{\displaystyle \mathrm{}}$ ${\displaystyle 1}$과(와) 같으며, 이는$$ $z{\displaystyle }$+ ${\displaystyle \beta }$ ${\displaystyle z+\beta }$과(와) $z{\displaystyle }$- ${\displaystyle \beta }$ ${\displaystyle z-\beta }$이(가) 모두$$ 2차 비재임을 의미한다.
2. GCD는 ${\displaystyle f_{}}$ z${\displaystyle {}_{}}$( ${\displaystyle x}$) ${\displaystyle f_{z}(x)}$과 동일하며, 이는$$ 두 숫자가 2차 잔류물임을 의미한다.
3. GCD는${\displaystyle }$(${\displaystyle x}$- ${\displaystyle t}$) ${\displaystyle (x-t)}$과 동일하며, 이는$$ 이들 숫자 중 정확히 하나가 2차 잔류물임을 의미한다.

In the third case GCD is equal to either ${\displaystyle (x-z-\beta )}$ or ${\displaystyle (x-z+\beta )}$. It allows to write the solution as ${\textstyle \beta =(t-z){\pmod {p}}}$.^[1]

예

Assume we need to solve the equation ${\textstyle x^{2}\equiv 5{\pmod {11}}}$. For this we need to factorize ${\displaystyle f(x)=x^{2}-5=(x-\beta )(x+\beta )}$. Consider some possible values of ${\displaystyle z}$:

1. Let ${\displaystyle z=3}$. Then ${\displaystyle f_{z}(x)=(x-3)^{2}-5=x^{2}-6x+4}$, thus ${\displaystyle \gcd(x^{2}-6x+4;x^{5}-1)=1}$. Both numbers ${\displaystyle 3\pm \beta }$ are quadratic non-residues, so we need 다른 $z{\displaystyle }$ ${\displaystyle z}$을(를) 가져오십시오$.$

1. $z{\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle z=2$}을$($를) 두십시오$.$Then ${\displaystyle f_{z}(x)=(x-2)^{2}-5=x^{2}-4x-1}$, thus ${\textstyle \gcd(x^{2}-4x-1;x^{5}-1)\equiv x-9{\pmod {11}}}$. From this follows ${\textstyle x-9=x-2-\beta }$, so ${\displaystyle \beta \equiv 7(\mathrm{mod}}$${\displaystyle 11}$) ${\$ 및$$$$- $\beta$ $\equiv$- $7$ $\equiv$ 4$$($\mathrm{모드}$ $11$) ${\$

수동 점검 결과 실제로 $7{\mathrm{}}^{}$ ${2\mathrm{}}^{}$ ${}^{}$ $49$ $\equiv$ 5 $(\mathrm{모드}$ $11$ )${\$ 7$^{2}\equiv 49\$equiv $49\equiv$ 5${\pmod{11}}$ 및$$ $4{\mathrm{}}^{}$ ${2\mathrm{}}^{}$ ${}^{}$ $16$ $\equiv$ $5$($\mathrm{모드}$ $11$) ${\$ 4$^{2}\equiv 16\equiv 5{\pmod{11$이 나타난다.

정확성 증명

The algorithm finds factorization of ${\displaystyle f_{z}(x)}$ in all cases except for ones when all numbers ${\displaystyle z+\lambda _{1},z+\lambda _{2},\ldots ,z+\lambda _{n}}$ are quadratic residues or non-residues simultaneously.어디에 kcyclotomy,[8]의 이론에 그러한 사건의 사건의 확률 의하면 λ 1,…,λ n{\displaystyle \lambda_{1},\ldots(_{n}}모든 잔류물 또는 non-residues 동시에( 때 z 돌아선 0{\displaystyle z=0 그,}실패할 것은)2− k{\displaystyle 2^{-k}로}추정할 것이다뚜렷한 값 λ 1,…,λ n{\displaystyle \lambda_{1},\ldots 이러한 방법으로 k의 최악의 경우 심지어(_{n}}.[1]=1{\displaystyle k=1}와 f()))()− λ)n{\displaystyle f())=(x-\lambda)^{n}}에{k\displaystyle}을 몇번이나 오류의 확률 1/2{으로 추정될 수 있다.\di$splaystyle$1$/2}$ 및$$ 모듈형 사각형 루트 사례 오류 확률은 최대${\displaystyle }$1/$[\displaystyle 1/4}$ 입니다$.$

복잡성

다항식에게 학위 $n{\displaystyle }$ ${\displaystyle n}$을 부여한다$.$ 알고리즘의 복잡성은 다음과 같이 도출한다.

1. Due to the binomial theorem ${\textstyle (x-z)^{k}=\sum \limits _{i=0}^{k}{\binom {k}{i}}(-z)^{k-i}x^{i}}$, we may transition from ${\displaystyle f(x)}$ to ${\displaystyle f(x-z)}$ in ${\displaystyle O(n^{2})}$ ti나.
2. Polynomial multiplication and taking remainder of one polynomial modulo another one may be done in ${\textstyle O(n^{2})}$, thus calculation of ${\textstyle x^{2^{k}}{\bmod {f}}_{z}(x)}$ is done in ${\textstyle O(n^{2}\log p)}$.
3. 2진수 $지수$는${\displaystyle }$O(${\displaystyle n}$ 2 log${\displaystyle )}$ ${\displaystyle p}$ )$${\$displaystyle O(n^{2$}\$log$ p$)}$에서 작동한다$.$
4. 유클리드 알고리즘을 통해 두 다항식$$ 중 ${\displaystyle gcd}$ ${\displaystyle \gcd }$을(를$)$ 가져오는 작업은 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$)${\displaystyle O(n^{2$})에서 수행된다$.$

algorithm,[9] 알고리즘의 복잡성 O(n로그⁡와 로그 ⁡ pn){O(n\log n\log pn)\displaystyle}에 개선될 지도 모르따라서 절차를 전부 O(n2로그 ⁡ p){O(n^{2}\log p)\displaystyle}. 빠른 푸리에 변환과 Half-GCD이 사용됩니다. 그것은 모듈식의 제곱 근 경우, 그 학위 n은=2{\displaystyl 질 수 있다.en$=2}$따라서 그러한 경우 알고리즘의 전체 복잡성은 반복당$$ $O{\displaystyle (\log }$ ${\displaystyle }$ $){\displaystyle$ O$(\log$ p$)}$로 제한된다.^[7]

참조