Patent ID: 7684564

Claim:
A computer-implemented method for computing the number of points on an elliptic curve, the method comprising: receiving an elliptic curve having a number of points on the curve; determining, with a processor, the number of points on the elliptic curve, wherein the determining includes solving a lifted Frobenius equation to a full precision by computing a plurality of partial solutions at a plurality of successively reduced precisions, wherein the solving includes: (a) computing, to a first reduced precision, a first partial solution of said lifted Frobenius equation, (b) applying a Frobenius operation to said first partial solution, (c) computing an error term for said lifted Frobenius equation using the first partial solution and/or a result of step (b), (d) computing correction factors for said lifted Frobenius equation using the first partial solution and/or a result of step (b), (e) computing, to the first reduced precision, a second partial solution of a modified lifted Frobenius equation using the error term, wherein computing the second partial solution includes: (1) computing, to another reduced precision, a third partial solution of said modified lifted Frobenius equation by recursively performing steps (1)-(5) to solve said modified lifted Frobenius equation from a lowest reduced precision to the another reduced precision, wherein the another reduced precision is less than the first reduced precision, (2) applying a Frobenius operation to said third partial solution, (3) updating said error term using results of steps (1) and (2) and the correction factors, (4) computing, to the another reduced precision, a fourth partial solution of said modified lifted Frobenius equation with the updated error term by recursively performing steps (1)-(5) to solve said modified lifted Frobenius equation with the updated error term from a lowest reduced precision to the another reduced precision, and (5) combining said third partial solution and said fourth partial solution to create the second partial solution, (f) combining said first partial solution and said second partial solution; and (g) repeating steps (a)-(f) one or more additional times to solve the lifted Frobenius equation to a full precision, wherein the result from step (f) is used as the first partial solution of step (a) for the next successively higher precision; and based on the number of points on the elliptic curve, generating a cryptographic key for use in a digital processing system.