Editing Pell's equation (section)

==Solutions==
===Fundamental solution via continued fractions===

Let <math>h_i/k_i</math> denote the unique sequence of [[Convergent (continued fraction)|convergents]] of the [[continued fraction|regular continued fraction]] for <math>\sqrt{n}</math>. Then the pair of positive integers <math>(x_1, y_1)</math> solving Pell's equation and minimizing ''x'' satisfies ''x''<sub>1</sub> = ''h<sub>i</sub>'' and ''y''<sub>1</sub> = ''k<sub>i</sub>'' for some ''i''. This pair is called the ''fundamental solution''. The sequence of integers <math>[a_0; a_1,a_2,\ldots]</math> in the regular continued fraction of <math>\sqrt{n}</math> is always eventually periodic. It can be written in the form <math>\left[\lfloor\sqrt{n}\rfloor;\;\overline{a_1,a_2,\ldots,a_{r-1}, 2\lfloor\sqrt{n}\rfloor}\right]</math>, where <math>\lfloor\, \cdot\, \rfloor</math> denotes integer floor, and the sequence <math>a_1,a_2,\ldots,a_{r-1}, 2\lfloor\sqrt{n}\rfloor</math> repeats infinitely. Moreover, the tuple <math>(a_1,a_2,\ldots,a_{r-1})</math> is [[palindrome | palindromic]], the same left-to-right or right-to-left.<ref name="titu" /> 

The fundamental solution is
<math display="block">(x_1, y_1)=\begin{cases} (h_{r-1}, k_{r-1}),&\text{ for }r\text{ even}\\
(h_{2r-1},k_{2r-1}),&\text{ for }r\text{ odd}\end{cases}</math>

The computation time for finding the fundamental solution using the continued fraction method, with the aid of the [[Schönhage–Strassen algorithm]] for fast integer multiplication, is within a logarithmic factor of the solution size, the number of digits in the pair <math>(x_1, y_1)</math>. However, this is not a [[polynomial-time algorithm]] because the number of digits in the solution may be as large as {{radic|''n''}}, far larger than a polynomial in the number of digits in the input value ''n''.<ref name=":0">{{Citation |last=Lenstra |first=H. W. Jr. |title=Solving the Pell Equation |url=https://www.ams.org/notices/200202/fea-lenstra.pdf |journal=[[Notices of the American Mathematical Society]] |volume=49 |issue=2 |pages=182–192 |year=2002 |mr=1875156 |author-link=Hendrik Lenstra}}.</ref>

===Additional solutions from the fundamental solution===
Once the fundamental solution is found, all remaining solutions may be calculated algebraically from<ref name=":0" />
<math display="block">x_k + y_k \sqrt n = (x_1 + y_1 \sqrt n)^k,</math>
expanding the right side, [[equating coefficients]] of <math>\sqrt{n}</math> on both sides, and equating the other terms on both sides. This yields the [[recurrence relation]]s
<math display="block">x_{k+1} = x_1 x_k + n y_1 y_k,</math>
<math display="block">y_{k+1} = x_1 y_k + y_1 x_k.</math>

===Concise representation and faster algorithms===
Although writing out the fundamental solution (''x''<sub>1</sub>, ''y''<sub>1</sub>) as a pair of binary numbers may require a large number of bits, it may in many cases be represented more compactly in the form
<math display="block">x_1+y_1\sqrt n = \prod_{i=1}^t \left(a_i + b_i\sqrt n\right)^{c_i}</math>
using much smaller integers ''a''<sub>''i''</sub>, ''b''<sub>''i''</sub>, and ''c''<sub>''i''</sub>.

For instance, [[Archimedes' cattle problem]] is equivalent to the Pell equation <math>x^2 - 410\,286\,423\,278\,424\ y^2 = 1</math>, the fundamental solution of which has {{val|206545}} digits if written out explicitly. However, the solution is also equal to
<math display="block">x_1 + y_1 \sqrt n = u^{2329},</math>
where
<math display="block">u = x'_1 + y'_1 \sqrt{4\,729\,494} = (300\,426\,607\,914\,281\,713\,365\ \sqrt{609} + 84\,129\,507\,677\,858\,393\,258\ \sqrt{7766})^2</math> 
and <math>x'_1</math> and <math>y'_1</math> only have 45 and 41 decimal digits respectively.<ref name=":0" />

Methods related to the [[quadratic sieve]] approach for [[integer factorization]] may be used to collect relations between prime numbers in the number field generated by {{radic|''n''}} and to combine these relations to find a product representation of this type. The resulting algorithm for solving Pell's equation is more efficient than the continued fraction method, though it still takes more than polynomial time. Under the assumption of the [[generalized Riemann hypothesis]], it can be shown to take time
<math display="block">\exp O\left(\sqrt{\log N\cdot\log\log N}\right),</math>
where ''N''&nbsp;=&nbsp;log&nbsp;''n'' is the input size, similarly to the quadratic sieve.<ref name=":0" />

===Quantum algorithms===
Hallgren showed that a [[quantum computer]] can find a product representation, as described above, for the solution to Pell's equation in polynomial time.<ref>{{Citation |last=Hallgren |first=Sean |title=Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem |journal=Journal of the ACM |volume=54 |issue=1 |pages=1–19 |year=2007 |doi=10.1145/1206035.1206039 |s2cid=948064}}.</ref> Hallgren's algorithm, which can be interpreted as an algorithm for finding the group of units of a real [[quadratic number field]], was extended to more general fields by Schmidt and Völlmer.<ref>{{Citation |last1=Schmidt |first1=A. |title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing – STOC&nbsp;'05 |pages=475–480 |year=2005 |chapter=Polynomial time quantum algorithm for the computation of the unit group of a number field |chapter-url=http://www.cdc.informatik.tu-darmstadt.de/reports/reports/Schmidt_Vollmer_STOC05.pdf |location=New York |publisher=ACM, Symposium on Theory of Computing |citeseerx=10.1.1.420.6344 |doi=10.1145/1060590.1060661 |isbn=1581139608 |last2=Völlmer |first2=U. |s2cid=6654142 |access-date=25 October 2017 |archive-date=26 October 2017 |archive-url=https://web.archive.org/web/20171026110757/https://www.cdc.informatik.tu-darmstadt.de/reports/reports/Schmidt_Vollmer_STOC05.pdf |url-status=dead }}.</ref>