베를레캄프 알고리즘

수학, 특히 계산 대수학에서 베를레캄프의 알고리즘은 유한한 분야(갈루아 분야라고도 한다)보다 다항식을 인수하기 위한 잘 알려진 방법이다.알고리즘은 주로 매트릭스 감소와 다항식 GCD 연산으로 구성된다.그것은 1967년 엘윈 베를캄프에 의해 발명되었다.1981년 칸토르-자센하우스 알고리즘까지는 이 문제를 해결하기 위한 지배적인 알고리즘이었다.그것은 현재 잘 알려진 많은 컴퓨터 대수 체계에서 시행되고 있다.

개요

Berlekamp의 알고리즘은 유한 필드 $F{\displaystyle {\mathbb{}}_{}}$ $q {\displaystyle$ $n}$에 계수가 있는$$ $도{\displaystyle }$ n ${\displaystyle$ n}의 제곱 없는 다항식 $f{\displaystyle (x}$) ${\displaystyle$ $f(x)$를 입력으로 사용하고$$ 계수가 있는$$ 다항식 $g$를 출력 값으로 제공한다.$g{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle g(x)}$이(가) $f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$을(를) 나누는$$ 것과 같은 필드$.$$그런{\displaystyle }$ 다음 f (${\displaystyle x}$) ${\displaystyle f(x)}$이(가) 수정 불가능한 다항식의 힘으로 분해되는$$ 것을 발견할 때까지(유한 필드 위에 있는 다항식의 링이 고유한 인수화 영역이라는 것을 상기) 알고리즘은 이들 및 후속 divisor에 재귀적으로 적용될 수 있다.

f${\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$의 모든 가능한 요인이 요인 링 안에 포함됨$$

${\displaystyle R={\frac {\mathb {F} _{q}[x]}{\langle f(x)\angle }}.}$

알고리즘은 합치를 충족하는$$ 다항식 ${\displaystyle g}$ (${\displaystyle x}$)${\displaystyle }$∈ R ${\displaystyle g(x)\in R}$에 초점을 맞춘다.

${\displaystyle g(x)^{q}\equiv g(x){\pmod {f(x)}}\,}$

이러한 다항식들은 Berlekamp 하위격자라 불리는 R의 하위격자$$(${\displaystyle {}_{}}$\$displaystyle \mathbb{F}$$$$_{q}})$를 형성한다.$$포함된$$ 다항식 g(${\displaystyle x}$) ${\displaystyle g(x)}$을(를) 충족하기 때문에 Berlekamp 서브algebra가 관심 대상이다.

${\displaystyle f(x)=\prod _{s\in \mathb {F} _{q}\gcd(x),g(x)-s).}$

일반적으로 위의 제품의 모든 GCD가 $f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$의 비경쟁 인자가 되지는 않겠지만$,$ 일부 인자는 우리가 추구하는 인자를 제공한다.

Berlekamp의 알고리즘은 ${\displaystyle \mathrm{Berlekamp}}$ 하위 골격의 기초를 계산하여 위의 결과와 함께 사용하기에 적합한$$ 다항식 g${\displaystyle (}x{\displaystyle }$) ${\displaystyle g(x)}$을 찾아낸다.This is achieved via the observation that Berlekamp subalgebra is in fact the kernel of a certain ${\displaystyle n\times n}$ matrix over ${\displaystyle \mathbb {F} _{q}}$, which is derived from the so-called Berlekamp matrix of the polynomial, denoted ${\displaystyle {\mathcal {Q}}}$. If ${\displaystyle \mathcal{Q}=[q_{}}$${\displaystyle i_{}}$, ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {Q}=[q_{i,j}],$ $q{\displaystyle {}_{}}$ ${\displaystyle {i,}_{}}$ ${\displaystyle j_{}}$ ${\displaystyle$ $q_{i,j}}}$는 $x{\displaystyle {}^{}}$ ${\displaystyle i^{}}$ ${\displaystyle q^{}}$ ${\$ x$^{iq}$ $모듈$로 f$$$(x)},$ $\{\backslash$$displaystystyle$ $j}$ -th$$ 전력 항의 계수다$$.

${\displaystyle x^{iq}\equiv q_{i,n-1}x^{n-1}+q_{n-2}x^{n-2}x^{n-2}+\ldots +q_{i,0}{\pmod {f(x)}}\,},},}$

${\displaystyle \mathrm{특정}}$ ${\displaystyle \mathrm{다항식}}$ g${\displaystyle }$( x${\displaystyle }$) ${\displaystyle \in }$ R ${\displaystyle g(x)\in R}$을$($를) 사용하여 다음과 같이 말한다.

${\displaystyle g(x)=g_{n-1}x^{n-1}+g_{n-2}x^{n-2}+{n-2}x^{n-2}+\dots +g_{0},}$

행 벡터를 연결할 수 있음:

${\displaystyle g=(g_{0},g_{1},\ldots,g_{n-1}).\,}$

It is relatively straightforward to see that the row vector ${\displaystyle g{\mathcal {Q}}}$ corresponds, in the same way, to the reduction of ${\displaystyle g(x)^{q}}$ modulo ${\displaystyle f(x)}$. Consequently, a polynomial ${\displaystyle g(x)\in R}$ is in the Berlekamp subalgebra if and only if ${\displaystyle g({\mathcal {Q}}-I)=0}$ (where ${\displaystyle I}$ is the ${\displaystyle n\times n}$ identity matrix), i.e. if and only if it is in the null space of ${\displaystyle {\mathcal {Q}}-I}$.

행렬 $Q{\displaystyle \mathcal{}}$- ${\displaystyle I}$ ${\displaystyle {\mathcal {Q}-I}$을(를) 계산하고$$ 이를 축소된 행 에셀론 형식으로 줄인 다음 Null 공간의 기초를 쉽게 읽어냄으로써, 우리는 Berlekamp subalgebra의 기초를 찾아 그 안에서$$ 다항식 $){\displaystystyleg(x)$을 구성할 수 있다.그리고 나서 우리는 비독점적 요소를 찾을 때까지 위의 형태의 GCD를 연속적으로 계산해야 한다.필드 위의 다항식 링은 유클리드 영역이기 때문에 유클리드 알고리즘을 사용하여 이러한 GCD를 계산할 수 있다.

개념 대수적 설명

어떤 추상적인 대수학으로, 베를레캄프의 알고리즘 뒤에 숨겨진 생각은 개념적으로 명확해진다.We represent a finite field ${\textstyle \mathbb {F} _{q}}$, where ${\textstyle q=p^{m}}$ for some prime p, as ${\textstyle \mathbb {F} _{p}[y]/(g(y))}$. We can assume that ${\textstyle f(x)\in \mathbb {F} _{q}[x]}$ is square free, by taking all가능한 pth 뿌리와 그 파생상품으로 gcd를 계산하는 것.

이제 $f$( $x$)$$= f ${1\mathrm{}}_{}$( x$$)$$…$f_{}$n ( $x$) ${\textstyle f(x)=f_{1}(x)\ldots f_{n}(x)}}$이(가) 비reducible에 대한 인자화라고$$ 가정해 보자.Then we have a ring isomorphism, ${\textstyle \sigma :\mathbb {F} _{q}[x]/(f(x))\to \prod _{i}\mathbb {F} _{q}[x]/(f_{i}(x))}$, given by the Chinese remainder theorem.The crucial observation is that the Frobenius automorphism ${\textstyle x\to x^{p}}$ commutes with ${\textstyle \sigma }$, so that if we denote ${\textstyle {\text{Fix}}_{p}(R)=\{f\in R:f^{p}=f\}}$, then ${\textstyle \sigma }$ restricts to an isomorphism ${\text{Fix}}_{}$${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))\to \prod _{i=1}^{n}{\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f_{i}(x)))}$. By finite field theory, ${\textstyle {\text{Fix$$}}}_{p}(\mathb {F} _{q}[x]/(f_{i}(x)})}$은(는) 항상 해당 필드 확장의 기본 하위 필드임$$.따라서 ${\text{픽스}}_{}$ ${}_{}$($F$ ${}_{}$[ $x]$ /$$($x$)$$)$${\$textstyle${\$text{Fix}_{p}(\mathb {F} _{q}[/(f(x)))})$는 f$$( x$$) ${\textstyle f(x)}$이(가) 허용되지$$ 않는 경우에만 p ${\textstylease p}$ 요소를$$ 갖는다$$.

더욱이 프로베니우스 오토모르프리즘이 ${}_{}$ p ${\$선형이라는$$ 사실을 이용하여 고정 집합을 계산할 수 있다.That is, we note that ${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))}$ is a ${\textstyle \mathbb {F} _{p}}$-subspace, and an explicit basis for it can be calculated in the polynomial ring ${\textstyle \mathbb {F} _{p}[x,y]/(f,g)}$$$ $({xi}^{}$ ${}^{}{}^{}$ $j^{}{}^{}$) $p^{}$ ${\$을(를) 계산하고$$ 프로베니우스에 의해 고정된 경우 충족되는 $x$ ,$y$ ${\textstyle x,y}$의 계수에$$ 대한 선형 방정식을 설정함으로써.이 시점에서 우리는 효율적으로 계산할 수 있는 무효화 기준을 가지고 있으며, 나머지 분석은 요인을 찾기 위해 이것을 사용하는 방법을 보여준다.

알고리즘은 이제 두 가지 사례로 나뉜다.

• In the case of small ${\textstyle p}$ we can construct any ${\textstyle g\in {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))\setminus \mathbb {F} _{p}}$, and then observe that for some ${\textstyle a\in \mathbb {F} _{p}}$ there are ${\textsty$$le i,j}$ so that ${\textstyle g-a=0\mod f_{i}}$ and ${\textstyle g-a\not =0\mod f_{j}}$. Such a ${\textstyle g-a}$ has a nontrivial factor in common with ${\textstyle f(x)}$, which can be computed via the gcd.$p$ ${\textstyle p}$이(가) 작기 때문에 가능한 모든$${\$textstyle a}$을(를) 순환할 수 있다$.$
• For the case of large primes, which are necessarily odd, one can exploit the fact that a random nonzero element of ${\textstyle \mathbb {F} _{p}^{*}}$ is a square with probability ${\textstyle 1/2}$, and that the map ${\textstyle x\to x^{\frac {p-1}{2}}}$ maps the set of non-zero squaresto ${\textstyle 1}$, and the set of non-squares to ${\textstyle -1}$. Thus, if we take a random element ${\textstyle g\in {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/f(x))}$, then with good probability ${\textstyle g^{\frac {p-1}{2}}-1}$ will have a non-tr$f$( $x$) ${\textstyle f(x)}$과(와) 공통의 ivial 계수$.$

자세한 사항은 상담할 수 있다.^[1]

적용들

Berlekamp 알고리즘의 중요한 적용은 유한한 필드 F ${\displaystyle {p^{}}_{}}$ {$n{\displaystyle {\mathbb{}}_{}}$ ${\$에 대한 이산 로그 계산에 있다$.$ 여기서 $p{\displaystyle }$ ${\displaystyle p}$은 prime이고 ${\displaystyle \mathrm{n}}$ ${\displaystyle \ge }$ 2 ${\displaystystyle n\geq 2}.$ 이산 로그 계산은 공개키 암호는 공개 키의 중요한 문제다.롤 코딩유한 분야의 경우, 가장 빨리 알려진 방법은 지수 미적분법이며, 이 방법은 필드 요소의 인자화를 포함한다.If we represent the field ${\displaystyle \mathbb {F} _{p^{n}}}$ in the usual way - that is, as polynomials over the base field ${\displaystyle \mathbb {F} _{p}}$, reduced modulo an irreducible polynomial of degree ${\displaystyle n}$ - then this is simply polynomial factorisation, as provided by Berlekamp의 알고리즘.

컴퓨터 대수 체계에서의 구현

Berlekamp의 알고리즘은 factormod 명령과 WolframAlpha[1] 웹사이트를 사용하여 PARI/GP 패키지에서 액세스할 수 있다.

참고 항목

• 다항식 인자화
• 유한장 및 재확정성 시험에 대한 다항식 인자화
• 칸토르-자센하우스 알고리즘

참조

• Berlekamp, Elwyn R. (1967). "Factoring Polynomials Over Finite Fields". Bell System Technical Journal. 46: 1853–1859. doi:10.1002/j.1538-7305.1967.tb03174.x. MR 0219231. BSTJ 나중에 다시 게시된 위치:
• Knuth, Donald E (1997). "4.6.2 Factorization of Polynomials". Seminumerical Algorithms. The Art of Computer Programming. Vol. 2 (Third ed.). Reading, Massachusetts: Addison-Wesley. pp. 439–461, 678–691. ISBN 0-201-89684-2.