Multibase scalar multiplications in cryptographic pairings (Q300879)

In elliptic curve cryptosystems based on bilinear pairings on the additive group of \({\mathbb F}_q\)-rational points of an elliptic curve, \textit{V. S. Miller}'s algorithm [J. Cryptology 17, No. 4, 235--261 (2004; Zbl 1078.14043)] computes these bilinear pairings evaluating certain functions which involve integer scalar multiplications \([n]P\). The standard Miller implementation uses binary representations of the scalar integers \(n\), and in the paper under review, the author optimizes Miller's algorithm using three different non-binary representations of a positive integer: The non-adjacent form, a signed-ternary base, and a double-base number representation. The last section of the paper compares the computational gains of implementatios of the improved Miller's algorithm in the three cases.