Computer Security and Cryptography

15.6 COMPUTATIONS IN THE ELLIPTIC GROUP

Programs to manipulate polynomials are required to carry out arithmetic in the elliptic group . As described in Section 14.5, these programs include PADD, PMUL, and PDIV, and PXEUCLID; the last program, PXEUCLID, is used to find the inverse of an element in . Only one task remains to generate the elements (x, y) of . For this purpose, linear operations in viewed as a vector space need to be performed. An example may make the ideas clear.

Example 15.5

p(x) = 1 + x + x⁴ is primitive over . Suppose is the root of p(x) = 0 adjoined to to obtain the extension field .

Multiplication: xy, x = (x₀, x₁, x₂, x₃); y = (y₀, y₁, y₂, y₃)

Next, we use the formulas ...