윌리엄스의 p+1 알고리즘

계산수 이론에서 윌리엄스의 p + 1 알고리즘은 대수군 인수 알고리즘의 한 계열인 정수 인수 알고리즘이다.그것은 휴 C에 의해 발명되었다. 윌리엄스는 1982년에 태어났다.

인수할 N 숫자가 하나 이상의 p + 1이 매끄러운 주요 요인 p를 포함하면, 즉, p + 1은 작은 요인만 포함하는 경우에 잘 작동한다.루카스 시퀀스를 사용하여 2차 필드에서 지수를 수행한다.

폴라드의 p - 1 알고리즘과 유사하다.

알고리즘.

Lucas 시퀀스를 특징으로 하는 2보다 큰 정수 A를 선택하십시오.

${\displaystyle V_{0}=2,V_{1}=A,V_{j}=AV_{j-1}-V_{j-2}}$

여기서 모든 연산이 수행된다.

Then any odd prime p divides ${\displaystyle \gcd(N,V_{M}-2)}$ whenever M is a multiple of ${\displaystyle p-(D/p)}$, where ${\displaystyle D=A^{2}-4}$ and ${\displaystyle (D/p)}$ is the Jacobi symbol.

${\displaystyle \mathrm{우리}}$는${\displaystyle }$(${\displaystyle D}$/ p${\displaystyle }$)${\displaystyle }$=${\displaystyle }$- 1 ${\displaystyle (D/p)=-1$ 즉 D는 2차 비 residue modulo p이어야 한다.그러나 우리가 p를 미리 알지 못하기 때문에 해결책을 찾기 전에 A의 두 가지 이상의 값이 필요할 수 있다.$({\displaystyle D}$ /${\displaystyle p}$)${\displaystyle }$=${\displaystyle }$+ ${\displaystyle 1}$ ${\displaystyle (D/p)=+1}$인 경우$,$ 이 알고리즘은 폴라드의 p - 1 알고리즘의 느린 버전으로 변질된다.

따라서 M의 다른 값에 대해 ${\displaystyle gcd(N}$, ${\displaystyle {}_{}}$ ${\displaystyle M_{}}$- ${\displaystyle 2}$) ${\displaystyle \gcd(N,V_{M}-2$을 계산하고, 결과가 1 또는 N과 같지 않을 때 N의 비경쟁 인자를 찾아냈다.

사용되는 M의 값은 연속적인 요인이고, ${\displaystyle V_{}}$ ${\displaystyle M_{}}$ ${\$은 $V{\displaystyle {}_{}}$ M -${\displaystyle 1_{}}$ ${\$이 특징인 시퀀스의 M-th 값이다$.$

B로 특징지어지는 수열의 M-th 요소 V를 찾기 위해, 좌-우 지수화와 유사한 방식으로 진행한다.

x := B y := (B ^ 2 - 2) M의 각 비트에 대해 가장 중요한 비트의 오른쪽에 있는 모드의 N은 비트가 1이면 x := (x × y - B) 모드의 N := (y ^ 2 - 2) 모드의 다른 N := (x × y - B) 모드의 N : (x ^ 2 - 2) 모드의 N : :

예

N=112729 및 A=5를 사용하는 경우 $V{\displaystyle {}_{}}$ ${\displaystyle M_{}}$ ${\$의 연속 값은 다음과 같다$$.

Seq(5)의₁ V = Seq(5)의_1! V = 5

Seq(5)의₂ V = Seq(5)의_2! V = 23

Seq(23)의₃ V = Seq(5)의_3! V = 12098

Seq(12098)의₄ V = Seq(5)의_4! V = 87680

Seq의 V₅(87680) = Seq의_5! V(5) = 53242

Seq의 V₆(53242) = Seq의 V(5_6!) = 27666

seq의 V₇(2766) = seq(5)의_7! V = 110229.

이 시점에서 gcd(110229-2,112729) = 139이므로 139는 비교인자 112729이다.p+1 = 140 = 2² × 5 × 7에 주목한다.숫자 7!은 140의 배수로 가장 낮은 요인인 139가 이 단계에서 발견된다.

A = 9라고 하는 다른 초기 값을 사용하면 다음과 같은 결과를 얻을 수 있다.

Seq(9)의₁ V = Seq(9)의_1! V = 9

Seq(9)의₂ V = Seq(9)의_2! V = 79

Seq(79)의₃ V = Seq(9)의_3! V = 41886

Seq의 V₄(41886) = Seq의_4! V(9) = 79378

Seq의 V₅(79378) = Seq(9)의_5! V = 1934

seq(1934)의₆ V = seq(9)의_6! V = 10582

Seq의 V₇(10582) = Seq의_7! V(9) = 84241

seq의₈ V(84241) = seq(9)의_8! V = 93973

seq의 V₉(93973) = seq(9)의_9! V = 91645.

이 시점에서 gcd(91645-2,112729) = 811이므로 811은 112729의 비경쟁적 요인이다.p-1 = 810 = 2 × 5 × 3에⁴ 주목한다.숫자 9!는 810의 배수로 가장 낮은 요인 811이 이 단계에서 발견된다.p-1 = 138 = 2 × 3 × 23, 9의 구분자가 아니기 때문에 이번에는 139 인자를 찾을 수 없다!

이러한 예에서 볼 수 있듯이 우리는 발견될 프라임이 매끄러운 p+1을 가지고 있는지 p-1을 미리 알 수 없다.

일반화

폴라드의 p - 1과 윌리엄스의 p+1 인수 알고리즘을 바탕으로 에릭^th 바흐와 제프리 샬릿은 kcylotomic 다항식 ((p_k)이 매끄러울 정도로 prime factor p가 있다는 전제하에 n을 효율적으로 인수하는 기법을 개발했다.^[1]처음 몇 개의 사이클로토믹 다항식은 φ₁(p) = p-1, φ₂(p) = p+1, φ₃(p) = p²+1, φ₄(p) = p+1의 순서로 주어진다².

참조

• Williams, H. C. (1982), "A p+1 method of factoring", Mathematics of Computation, 39 (159): 225–234, doi:10.2307/2007633, MR 0658227

외부 링크

• Prime Wiki에서 P + 1 인자화 방법