딕슨의 인자화법

수 이론에서 딕슨의 인자화 방법(Dixon의 무작위 제곱법^[1] 또는 Dixon의 알고리즘도 포함)은 범용 정수 인자화 알고리즘으로, 프로토타입적인 인자 베이스 방법이다.다른 인자 베이스 방법과 달리, 런타임 바운드는 다항식이 취한 값의 부드러움 특성에 대한 추측에 의존하지 않는 엄격한 증거를 가지고 있다.

그 알고리즘은 존 D에 의해 설계되었다. 칼턴 대학의 수학자 딕슨은 1981년에 출판되었다.^[2]

기본 아이디어

딕슨의 방법은 고려하고자 하는 정수 N의 제곱합성을 찾는 것에 기초한다.페르마의 인자화 방법은 무작위 또는 의사 무작위 x 값을 선택하고² 정수 x 모드의 N이 (정수에서) 완벽한 제곱이 되기를 바라면서 그러한 합치를 찾는다.

${\displaystyle x^{2}\equad ({\hbox{mod }}}}\quad),\qquad x\not \equiv \pm y\quad ({\hbox{mod }}}N).}$

예를 들어 N = 84923, (292부터 시작하여 countingN보다 큰 첫 번째 숫자를 세는 것) 505모드² 84923은 16의 제곱인 256이므로 (505 - 16)(505 + 16) = 0모드 84923이다.유클리드 알고리즘을 사용하여 505 - 16과 N의 가장 큰 공통점수를 계산하면 163이 나오는데, 이것이 N의 요인이다.

실제로 무작위 x 값을 선택하는 것은 N보다 작은 nN 제곱만이 있기 때문에 제곱의 합치를 찾는 데 비실용적으로 오랜 시간이 걸릴 것이다.

딕슨의 방법은 "정수의 제곱"이라는 조건을 "소수의 제곱"이라는 훨씬 약한 것으로 대체한다. 예를 들어, 84923보다 작은 292개의 제곱, 2,3,5 또는 7에 불과한 84923보다 작은 662개의 숫자, 30보다 작은 4767개의 소수 등이 있다. (그런 숫자를 B-smooth라고 한다.)어떤 구속 B.)

If there are many numbers ${\displaystyle a_{1}\ldots a_{n}}$ whose squares can be factorized as ${\displaystyle a_{i}^{2}\mod N=\prod _{j=1}^{m}b_{j}^{e_{ij}}}$ for a fixed set ${\displaystyle b_{1}\ldots b_{m}}$ of small primes, linear${\displaystyle {매트릭스}_{}}$ $e{\displaystyle {}_{}}$ ${\displaystyle j_{}}${\$displaystyle e_{ij}}$의 대수모듈로 2는$$ 정사각형이 작은 프리임의 곱과 짝수 전력에 $결합$된 ${\displaystyle i_{}}$$${\$displaystyle$ $a_{$$i}$의 부분집합, 즉$$ 정사각형이 (희망적으로 다른) N의 제곱에 곱한 i ${\$ a_{$i}$를 제공한다.

방법

복합 번호 N이 인수되고 있다고 가정합시다.바운드 B를 선택하고 요인 베이스(P라고 함)를 식별하며, 모든 프리마임이 B보다 작거나 같은 집합이다.다음으로, z² mod N이 B-smooth인 양의 정수 z를 구한다.따라서 적절한 지수 a에_i 대해 기록할 수 있다.

${\displaystyle z^{2}{\text{{}}모드 }N=\prod _{p_{i}\in P}p_{i}^{a_{i}}}}}}}$

이러한 관계가 충분히 생성되었을 때(일반적으로 관계의 수가 P의 크기보다 몇 개 더 많으면 충분하다), 선형대수의 방법(예를 들어 가우스 제거)을 사용하여 이러한 다양한 관계를 우측의 소수 지수가 모두 균등하게 곱할 수 있다.

${\displaystyle {z_{1}^{2}z_{2}^{2}\cdots z_{k}^{2}\equiv \prod _{p_{i}\in P}p_{i}^{a_{i,1}+a_{i,2}+\cdots +a_{i,k}}\ {\pmod {N}}\quad ({\text{where }}a_{i,1}+a_{i,2}+\cdots +a_{i,k}\equiv 0{\pmod {2}})}}$

이것은 ≡ b²²(모드 N) 형태의 제곱합을 산출하는데, 이것은 N, N = gcd(a + b, N) × (N/gcd(a + b, N)의 인자로 바뀔 수 있다.이 인자화는 사소한 것으로 판명될 수 있다(즉, N = N × 1) ≡ ±b(mod N)의 경우에만 발생할 수 있다. 이 경우 다른 관계 조합으로 다른 시도를 해야 하지만 N의 비종교적인 요인 쌍에 도달할 수 있고 알고리즘은 종료된다.

가성음

input: positive integer ${\textstyle N}$ output: non-trivial factor of ${\textstyle N}$  Choose bound ${\textstyle B}$ Let ${\textstyle P:=\{p_{1},p_{2},\ldots ,p_{k}\}}$ be all primes ${\textstyle \leq B}$ repeat for ${\textstyle i=1}$ to ${\tex$$tstyle k+1}$ do         Choose ${\textstyle 0<z_{i}<N}$ such that ${\textstyle z_{i}^{2}{\text{ mod }}N}$ is ${\textstyle B}$-smooth         Let ${\textstyle a_{i}:$$=\{a_{i1},a_{i2},\ldots ,a_{ik}\}}$ such that ${\textstyle z_{i}^{2}{\text{ mod }}N=\prod _{p_{j}\in P}p_{j}^{a_{ij}}}$ end for      Find non-empty ${\textstyle T\subseteq \{1,2,\ldots ,k+1\}}$ such that $\sum _{i\in T}{a}_i\equiv \overrightarrow{0}(\mathrm{mod}$${\textstyle \sum _{i\in T}a_{i}\equiv {\vec {0}}{\pmod {2}}}$     Let ${\textstyle x:=\left(\prod _{i\in T}z_{i}\right){\text{ mod }}N}$ ${\textstyle y:=\left(\prod _{p_{j}\in P}p_{j}^{\left(\sum _{i\i$n$$ $T}a_{ij}\right$){\$text{{{$ij$}}/{2}\right){\text{{$$n$$}$ 동안 $x$≡$$± y$$($\mathrm{모드}$ $){\$ $\$$pmod{{n$$}}}$는 $gcd$를 반환한다$.$

예

이 예에서는 바운드 B = 7을 사용하여 N = 84923을 인자화하려고 시도한다.그러면 인자 베이스는 P = {2, 3, 5, 7}이다.$\lceil {\displaystyle }$ ${\displaystyle \sqrt{84923}}$ ${\displaystyle \rceil }$= ${\displaystyle 292}$ ${\displaystyle \left\lceil {\sqrt{84923}\right\rceil =292}$과(와) N 사이의 정수를 검색할 수 있다. N의 제곱모드 N은 B-smooth이다.발견된 숫자 중 2개가 513과 537이라고 가정합시다.

${\displaystyle 513^{2}\mod 84923=8400=2^{4}\cdot 3\cdot 5^{2}\cdot 7}$

${\displaystyle 537^{2}\mod 84923=33600=2^{6}\cdot 3\cdot 5^{2}\cdot 7}$

그렇게

${\displaystyle (513\cdot 537)^{2}\mod 84923=2^{10}\cdot 3^{2}\cdot 5^{4}\cdot 7^{2}\mod 84923}$

그러면

${\displaystyle {\cdot}&{}(513\cdot 537)^{2}\mod 84923\&=(275481)^{2}\mod 84923\&=(84923\cdot 3+12)^{2}\mod 84923\&=(84923\cdot 3)^{2}+2\cdot (84923\cdot 3\cdot 20712)+#12^{2}\mod 84923\&=0+0+12^{2}\mod 84923\end{liged}}}}}}}}$

즉, ${\displaystyle {20712}^{}}$ ${\displaystyle \mathrm{2모드}{}^{}}$ ${\displaystyle 84923}$=${\displaystyle }$(${\displaystyle {2\mathrm{}}^{}}$ 5 ${\displaystyle {}^{}}$ ${\displaystyle 3}$ ${\displaystyle \cdot }$ ${\displaystyle {\mathrm{}}^{}}$ ${\displaystyle 2{}^{}}$2 ${\displaystyle {}^{}}$ 7 ) ${\displaystyle \mathrm{2모드}}$ ${\displaystyle {84923\mathrm{}}^{}}$ = ${\displaystyle {16800\mathrm{}}^{}}$ 2 ${\displaystyle \mathrm{mod}{}^{}}$ ${\displaystyle 84923.}$${\displaystyle 20712^{2}\mod 84923=(2^{5}\cdot 3\cdot 5^{2}\cdot 7)^{2}\mod 84923=16800^{2}\mod 84923).$$}$

결과 인자화는 84923 = gcd(20712 - 16800, 84923) × gcd(20712 + 16800, 84923) = 163 × 521이다.

최적화

이차 체는 딕슨의 방법을 최적화한 것이다.의 제곱근에 가까운 x 값을 선택한다.Nx² modulo N이 작기 때문에, 대체로 부드러운 숫자를 얻을 가능성이 증가한다.

딕슨의 방법을 최적화하는 다른 방법으로는 매트릭스 방정식을 해결하기 위해 더 나은 알고리즘을 사용하는 것이 있다. 매트릭스의 스파르시티를 이용하여 숫자 z는 ${\displaystyle {\mathrm{로그}}_{}}$ 2${\displaystyle {}_{}2}$ z ${\displaystyle \log _{2$}z$}$ 인자를$$ 초과할 수 없기 때문에 매트릭스의 각 행은 거의 모두 0이다.실제로 블록 란초스 알고리즘이 자주 사용된다.또한 요소 베이스의 크기는 신중하게 선택해야 한다: 너무 작으면 그 위에 완전히 요소화하는 숫자를 찾기가 어려울 것이고, 너무 크면 더 많은 관계를 수집해야 할 것이다.

${\displaystyle {\mathrm{숫자}}^{}}$가 $모든{\displaystyle {}^{}}$ 주요 인자를 - $displaystyle$ a$^{-a}($Dickman-de Bruijn 함수에 대한 개연성$)$에 대해 N 1 /${\displaystyle a^{}}${\$displaystyle N^{1$/a$}$보다 작다는 근사치를 사용하여 더 정교한 분석을 수행하면 너무 작은 인자 베이스 선택이 너무 큰 것보다 훨씬 나쁘다는 것을 알 수 있다.이상적인 요인 기준 크기가 ${\displaystyle \exp }$ ${\displaystyle (\sqrt{\log }}$ ${\displaystyle \sqrt{}}$ N ${\displaystyle \sqrt{\log }}$ ${\displaystyle \sqrt{}}$ ${\displaystyle \sqrt{\log }\sqrt{}}$ ${\displaystyle \sqrt{n}}$ $){\$\exp \$left({\sqrt {\log N}\log$ N}\$log$ N$}\right)$의 일부 검정력이라는 것$.$

딕슨의 방법의 최적의 복잡성은

${\displaystyle O\left(\exp \exp \left(2{\sqrt{2}}:\log n\log n}\오른쪽)}$

Big-O 표기법으로, 또는

${\displaystyle L_{n}[1/2,2{\sqrt{2}}]}$

L-notation으로

참조