But these correspond to periodicities in the list Mod[a^Range[m], m] . … But now if one sets up a superposition of all these configurations, one can compute Mod[a # , m]& , then essentially use Fourier to find periodicities—all with a polynomial number of quantum gates. … In the mid-1990s it was thought that quantum computers might perhaps give polynomial solutions to all NP problems.

The number of operations to evaluate Mod[a, b] is of order n if a has n digits and b is small. … Roots of polynomials can thus almost always be found with NSolve in about Log[n] m[n] operations. If one evaluates NIntegrate or NDSolve by effectively fitting functions to order s polynomials the difficulty of getting results with n -digit precision typically increases like 2 n/s .

Continued fractions The first n terms in the continued fraction representation for a number x can be found from the built-in Mathematica function ContinuedFraction , or from Floor[NestList[1/Mod[#, 1]&, x, n - 1]] A rational approximation to the number x can be reconstructed from the continued fraction using FromContinuedFraction or by Fold[(1/#1 + #2 )&, Last[list], Rest[Reverse[list]]] The pictures below show the digit sequences of successive iterates obtained from NestList[1/Mod[#, 1]&, x, n] for several numbers x . … Numbers whose continued fraction terms are polynomials in n can presumably also be represented in terms of suitably generalized hypergeometric functions. (All so-called Hurwitz numbers have continued fractions that consist of interleaved polynomial sequences—a property left unchanged by x  (a x + b)/(c x + d) .)

In the late 1970s it was noted that by evaluating PowerMod[a, n - 1, n]  1 for several random integers a one can with high probability quickly deduce PrimeQ[n] . (In the 1960s it had been noted that one can factor polynomials by filling in random integers for variables and factoring the resulting numbers.)