liveBook · Manning

Power method

As explained in Elliptic Curve Cryptography for Developers

A modular square-root technique that obtains the root by exponentiating when the prime modulus is congruent to 3 modulo 4.

Computes a modular square root directly when the prime modulus is congruent to 3 modulo 4. For input a, raise a to (p+1)/4 modulo p; the result is the candidate root. section 2.5

The implementation follows a short decision path:

  • Fall back to Tonelli–Shanks when bit 1 is clear. section 2.5

Choosing the method

For 27213068317, inspect the modulus’ low bits: because the number is congruent to 1 modulo 4, use Tonelli–Shanks rather than the power method. section 2.5

How Elliptic Curve Cryptography for Developers covers it

How deep it goes
Derives the direct exponent operation and implements its modulus-bit test, but defers general moduli to Tonelli–Shanks.
Examples
Uses low-bit inspection and the modulus 27213068317 to practice choosing between the power method and Tonelli–Shanks.
What it assumes
Assumes modular arithmetic, prime moduli, quadratic residues, and modular exponentiation.
What you can do after
Apply it via GMP to compute modular square roots for primes congruent to 3 modulo 4.
How it connects
Connects modular square roots with quadratic residues, modular exponentiation, and Tonelli–Shanks.
Cover of Elliptic Curve Cryptography for Developers
liveBookmanning.com
Read Elliptic Curve Cryptography for Developers on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Elliptic Curve Cryptography for Developers. The section links point to the parts of the book it draws on.