In this study high‐performance and high‐speed field‐programmable gate array (FPGA) implementations of polynomial basis Itoh–Tsujii inversion algorithm (ITA) over GF(2 m ) constructed by irreducible trinomials and pentanomials are presented. The proposed structures are designed by one field multiplier and k ‐times squarer blocks or exponentiation by 2 k , where k is a small positive integer. The k ‐times squarer blocks have an efficient tree structure with low critical path delay, and the multiplier is based on a proposed high‐speed digit‐serial architecture with minimum hardware resources. Furthermore, to reduce the computation time of ITA, the critical path of the circuit is broken to finer path using several registers. The computation times of the structure on Virtex‐4 FPGA family are 0.262, 0.192 and 0.271 µs for GF(2 163 ), GF(2 193 ) and GF(2 233 ), respectively. The comparison results with other implementations of the polynomial basis Itoh–Tsujii inversion algorithm verify the improvement in the proposed architecture in terms of speed and performance.

Let E be an elliptic curve over a finite field Fqof q elements, with gcd(q,6)=1, given by an affine Weierstraß equation. We use x(P) to denote the x-component of a point P=(x(P),y(P)) ∈ E. We estimate character sums of the form Σn=1Nχ(x(nP)x(nQ)) and Σn1,⋯,nk=1Nψ(Σj=1kcjx((Πi=1jni)R)) on average over all Fqrational points P, Q, and R on E, where χ is a quadratic character, ψ is a nontrivial additive character in Fq, and (c1,..., ck) ∈ Fqkis a nonzero vector. These bounds confirm several recent conjectures of Jao, Jetchev, and Venkatesan, related to extracting random bits from various sequences of points on the elliptic curves.

We propose a simple and efficient deterministic extractor for an ordinary elliptic curve E, defined over $$\mathbb{F}_{2^n}$$ , where n = 2ℓ and ℓ is a positive integer. Our extractor, for a given point P on E, outputs the first $${\mathbb{F}}_{2^\ell}$$ -coefficient of the abscissa of the point P. We also propose a deterministic extractor for the main subgroup G of E, where E has minimal 2-torsion. We show that if a point P is chosen uniformly at random in G, the bits extracted from the point P are indistinguishable from a uniformly random bit-string of length ℓ.