Multiprecision Arithmetic
Integer Square Root and Perfect Power Detection
Newton iteration for integer square roots, exact perfect power detection, and why these cheap tests belong at the front of every factoring routine.
Engineering / MathematicsMultiprecision Arithmetic2 min readKV-MATH-0512
Integer square root and perfect power detection are cheap, exact and easy to get subtly wrong. They belong at the front of any factoring pipeline, because a perfect power that reaches the sieving stage wastes an enormous amount of work.
Integer square root by Newton iteration
The integer square root of N is the largest integer whose square does not exceed N. Newton's method converges quadratically and, with care, terminates exactly.
Integer square root
- Initial estimateUse the bit length: start from a power of two just above the true root.
- IterateApply the update until the sequence stops decreasing.
- VerifyCheck the square against N and adjust by one if needed.
Perfect power detection
A number is a perfect power if it equals m^k for integers with k > 1. Only prime exponents need testing, and only up to the bit length of N, since 2^k must not exceed N.
Perfect power detection
- Bound the exponentOnly prime k up to log2(N) can occur.
- Estimate the rootCompute an approximate k-th root using floating point on the logarithm.
- RefineApply Newton iteration in integers to get an exact candidate.
- Verify exactlyRaise the candidate to the k-th power and compare. Floating point is used only to locate the candidate, never to decide.
Why it matters for factoring
| Method | Behaviour on a perfect power |
|---|---|
| Pollard rho | Can cycle without splitting |
| Quadratic sieve | Relation collection degenerates |
| ECM | Works but wastes effort rediscovering the same factor |
| Fermat-style methods | May fail to separate repeated factors |
Related uses
Integer square root also appears directly in SQUFOF, in continued fraction expansion of quadratic irrationals, and in bounding loops for form reduction.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.7. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.