Patent US 7,684,564

The present invention comprises fast new methods for computing high-precision solutions of Frobenius equations that arise in elliptic-curve cryptography. In particular, this invention may be used to accelerate the computation of the number of points on an elliptic curve over a finite field. The advantage over methods in prior art is that the invention is faster than previously known methods. The methods enable optimally fast canonical lifting of elliptic curves defined over finite fields, optimally fast pre-computations to determine an efficient representation of intermediate quantities, and optimally fast lifting of finite-field elements to compute multiplicative representatives. Furthermore the invention enables rapid computation of norms and traces amongst other applications.