8.5 BIBLIOGRAPHY

[BAI2001] D. V. Bailey and C. Paar, Efficient arithmetic in finite field extensions with application in elliptic curve cryptography. J. Cryptol., 14(3): 153–176 (2001).

[ITO1988] T. Itoh and S. Tsujii, A fast algorithm for computing multiplicative inverses in GF(2^m) using normal bases. Math. Computation 44(4): 519–521 (1985).

[MON1985] P. Montgomery, modular multiplication without trial division. Math. Computation 44(4): 519–521 (1985).

[ROS1999] M. Rosing, Elliptic Curve Cryptography. Manning Publications, Greenwich, CT, 1999.

[WOO2000] A. D. Woodbury, Elliptic curve cryptography on smart cards without coprocessors. IFIP CARDIS, 71–92 (2000).

APPENDIX 8.1 COMPUTATION OF f_ki

First compute the value of q(i) such that pⁱ = q(i).n + 1.

Lemma A8.1

Proof By induction,

so that

Then compute c^q(i) mod p.

Lemma A8.2

Proof By induction,

It remains to compute

Lemma A8.3

Proof According to (A8.2),

Example A8.1 (Complete Ada source code available.) Consider the following case:

First observe that 239 = 14.17+1 so that

then compute

The following Ada program computes all the coefficients f_ki (the complete source code is available).

Algorithm A8.1 Ada Program for Computing f_ki

procedure frobenius is
  type frobenius_matrix is array (0.n−1, 0.n−1) of
  coefficient;
  f: frobenius_matrix;
  q, qq: polynomial;
  quotient, power: coefficient;
  cr: character;
begin
  quotient:=p/n;
  for i in 1..n−1 loop
    q(i):=(p*q(i−1)+quotient) mod p;
  end loop;
  power:=(2**quotient) mod p;
  qq(0):=1;
  for i in 1..n−1 loop
    qq(i):=(power*qq(i−1)) mod p;
  end loop;
  for i in 1..n−1 loop
    f(0,i):=1;
    for k in 1..n−1 loop
      f(k,i):=(f(k−1, i)*qq(i)) mod p;
    end loop;
  end loop;
  for k in 1..n−1 loop
    for i in 1..n−1 loop
      put(“f(”); put(k); put(“,”); put(i); put(“)=”);
       put(f(k,i));
      new_line;
    end loop;
   get(cr);
  end loop;
end frobenius;