Successive Square Method

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)

REFERENCES:

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