TOPICS
Search

Successive Square Method


The successive square method is an algorithm to compute a^b in a finite field GF(p). The first step is to decompose b in successive powers of two,

 b=sum_(i)delta_i2^i,
(1)

where delta_i in {0,1}, which gives b in base 2. a^b can then be represented as

a^b (mod p)=product_(i)(a^(delta_i2^i)) (mod p)
(2)
=product_(i)(a^(delta_i2^i) (mod p)) (mod p).
(3)

This term can be computed by successive steps as

a^1 (mod p)=alpha_1
(4)
a^2 (mod p)=alpha_1^2 (mod p)=alpha_2
(5)
a^4 (mod p)=alpha_2^2 (mod p)=alpha_4|
(6)
a^i (mod p)=alpha_(i/2)^2 (mod p)=alpha_i.
(7)

For example, to compute 28^(27) in the finite field GF(76), first decompose 28^(27) into 28^(16)·28^8·28^2·28^1, then follow the above steps:

28=28^1 (mod 76)
(8)
24=28^2 (mod 76)
(9)
44=24^2=28^4 (mod 76)
(10)
36=44^2=28^8 (mod 76)
(11)
4=36^2=28^(16) (mod 76).
(12)

From there, the final answer can be computed as

 20=(4·36·24·28)=28^(27) (mod 76).
(13)

The successive square method is implemented in the Wolfram Language as PowerMod[a, b, n].


Portions of this entry contributed by Pascal Perez

Explore with Wolfram|Alpha

References

Bressoud, D. and Wagon, S. Computational Number Theory. New York: Key College Publishing, pp. 30-40, 2000.

Referenced on Wolfram|Alpha

Successive Square Method

Cite this as:

Perez, Pascal and Weisstein, Eric W. "Successive Square Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SuccessiveSquareMethod.html

Subject classifications