Method of privacy communication using elliptic curves

Abstract

The present invention provides a method of privacy communication, in which an elliptic curve E and an element thereof are notified to all parties who wish to communicate, and data are transmitted from one party to another by using a calculation of the element and coded data made in secret by each party. The method is characterized by a construction of E(GF(p)) such whose number of elements has exactly p, assuming that p is a prime number and E(GF(p)) is a group of elements of GF(p) on the elliptic curve E. More particularly, E(GF(p)) is constructed by an algorithm: let d be a positive integer such that gives an imaginary quadratic field Q((-d.sup.1/2)) with a small class number; then find a prime number p such that 4.multidot.p-1=d.multidot.square number; and find a solution of a class polynomial H.sub.d (x)=0 modulo p such that is defined by d and given with a j-invariant.