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].