The successive square method is an algorithm to compute 
in a finite field 
. The first step is to decompose 
in successive powers of two,
 |
(1)
|
where 
,
which gives 
in base 2. 
can then be represented as
 |  |  |
(2)
|
 |  |  |
(3)
|
This term can be computed by successive steps as
 |  |  |
(4)
| ||
 |  |  |
(5)
| ||
 |  |  |  |  |
(6)
|
 |  |  |
(7)
|
For example, to compute 
in the finite field 
, first decompose 
into 
, then follow the above
steps:
 |
(8)
|
 |
(9)
|
 |
(10)
|
 |
(11)
|
 |
(12)
|
From there, the final answer can be computed as
 |
(13)
|
The successive square method is implemented in the Wolfram Language as PowerMod[a, b, n].
