require a large number of bits, it may in many cases be represented more compactly in the form using much smaller integers ai, bi, and ci. For instance, Archimedes' cattle problem is equivalent to the Pell equation , the fundamental solution of which has digits if written out explicitly. However, the solution is also equal to where and and only have 45 and 41 decimal digits respectively. 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 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 where N = log n is the input size, similarly to the quadratic sieve. 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. 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. Example As an example, consider the instance of Pell's equation for n = 7; that is, The sequence of convergents for the square root of seven are {| class="wikitable" style="text-align:center;" |- ! h/k (convergent) ! h2 − 7k2 (Pell-type approximation) |- | 2/1 | −3 |- | 3/1 | +2 |- | 5/2 | −3 |- | 8/3 | +1 |} Therefore, the fundamental solution is formed by the pair (8, 3). Applying the recurrence formula to this solution generates the infinite sequence of solutions (1, 0); (8, 3); (127, 48); (2024, 765); (32257, 12192); (514088, 194307); (8193151, 3096720); (130576328, 49353213); ... (sequence (x) and (y) in OEIS) The smallest solution can be very large. For example, the smallest solution to is (, ), and this is the equation which Frenicle challenged Wallis to solve. Values of n such that the smallest solution of is greater than the smallest solution for any smaller value of n are 1, 2, 5, 10, 13, 29, 46, 53, 61, 109, 181, 277, 397, 409, 421, 541, 661, 1021, 1069, 1381, 1549, 1621, 2389, 3061, 3469, 4621, 4789, 4909, 5581, 6301,