펠 방정식

• 영어 명칭: Pell's Equation
• 속도 향상: 초다항적
• 구현 코드: ∅

제곱수가 아닌 양의 정수 $d$가 주어졌을 때, 펠(Pell)의 방정식은 $x^3-d{y}^2=1$이다. 임의의 $d$에 대하여 이 식을 만족하는 순서쌍 $(x,y)$는 무한히 존재한다. 여기서 $x+y\sqrt{d}$의 값을 최소가 되게 하는 순서쌍을 $(x_1,y_1)$이라고 하자. 만약 $d$가 $n$비트 정수라면 (이를테면, $0\le d<2^n$), 보통 $(x_1,y_1)$은 지수적으로 많은 비트가 필요하다. 그러므로 일반적으로 $(x_1,y_1)$을 다항 시간에 찾는 것은 불가능하다. 이제 $R=\log (x_1+y\sqrt{d})$로 두자. 그러면 $\lfloor R\rceil$은 $(x_1,y_1)$을 유일하게 특정한다. 홀그렌(Hallgren)이 보인 바와 같이 [43], $n$비트 정수 $d$가 주어졌을 때, 양자 컴퓨터는 $\lfloor R\rceil$을 $\mathrm{poly}(n)$ 시간에 찾을 수 있다. 고전 알고리즘 중에서 다항 시간에 찾을 수 있는 것은 알려지지 않았다. 소인수분해는 이 문제로 환산된다. 이 알고리즘은 북만-윌리엄스(Buchman-Williams) 암호 체계를 무력화시킨다. 아벨 숨은 부분군을 참고.