Parallel Formulations of Scalar Multiplication on Koblitz Curves

Abstract: we present an algorithm that by using the ô and ô.1 frobenius operators concur- rently allows us to obtain a parallelized version of the classical ô -and-add scalar multiplication algorithm for koblitz elliptic curves. furthermore, we report suitable irreducible polynomials that lead to efficient implementations of both ô and ô.1, thus showing that our algorithm can be effectively applied on all the nist-recommended curves. we also present design details of software and hardware implementations of our procedure. in a two-processor workstation soft- ware implementation, we report experimental data showing that our parallel algorithm is able to achieve a speedup factor of almost 2 when compared with the standard sequential point multipli- cation. in our hardware implementation, the parallel version yields a more modest acceleration of 17% when compared with the traditional point multiplication algorithm. although the focus is on koblitz curves, analogous strategies are discussed for other curves, in particular for random curves over binary fields.