[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(2m) 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).
First compute the value of q(i) such that pi = q(i).n + 1.
Lemma A8.1
Proof By induction,
so that
Then compute cq(i) mod p.
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 fki (the complete source code is available).
Algorithm A8.1 Ada Program for Computing fki
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;
Synthesis of Arithmetic Circuits: FPGA, ASIC, and Embedded Systems
By Jean-Pierre Deschamps, Géry J. A. Bioul, and Gustavo D. Sutter
Copyright © 2006 John Wiley & Sons, Inc.