A Note On Schoof's Algorithm

The key to finding a useful elliptic curve for Elliptic Curve Cryptosystem (ECC) is to compute the order of elliptic curve rational points group over a finite field. A well-known effective algorithm is Schoof's Algorithm introduced by R. Schoof in 1985. In Section 1, we briefly introduce the idea of ECC and several methods of finding useful elliptic curves needed for ECC.In Section 2, we introduce mathematical theories and basic idea of Schoof's Algorithm.In the practical realization of Schoof's Algorithm, a primitive root of a finite field Fp² is needed. Generally, we only need a prime p less than 200 in practice. In Section 3, we get an algorithm to look for a primitive root of Fp² from a given primitive root of the finite field Fp. What's more, a table of primitive roots over Fp² can be provided for those prime numbers p (p<200).