Editing Pell's equation (section)

===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" />