Back to results
US 7,623,655 B2Granted
Computing modular polynomials modulo large primes
AssigneeMicrosoft Corporation
InventorsKristin E. Lauter, Denis X Charles
Life of this patent
Estimating the term…
Abstract
Systems and methods for computing modular polynomials modulo large primes are described. In one aspect, the systems and methods generate 1-isogenous elliptic curves. A modular polynomial modulo a large prime p is then computed as a function of 1-isogenous elliptic curves modulo p.
Claims4
A method implemented by a computing device, the method comprising:
- providing two distinct primes p and l;
- providing j a j-invariant of a supersingular elliptic curve E over a finite field Fq of degree at most 2 over a prime field of characteristic p;
- determining univariate polynomial φl(x,j) modulo p by computing the l+1 distinct subgroups of order l and computing the j-invariants (j1, . . . , jl+1) of the l+1 supersingular elliptic curves that are l-isogenous to E;
- based on information associated with a plurality of values of j, determining bivariate polynomial φl(x, y) modulo p via interpolation;
- and
- using the bivariate polynomial in a cryptosystem.
3 more elements
Dependencies are inferred from the claim text.