KEYWORDS: Binary data, Computing systems, Cryptography, Mathematics, Signal processing, Data processing, Current controlled current source, Visualization, Actinium, Silver
On an elliptic curve, the multiplication of a point P by a scalar k is defined by a series of operations over the
field of definition of the curve E, usually a finite field Fq. The computational cost of [k]P = P + P + ...+ P
(k times) is therefore expressed as the number of field operations (additions, multiplications, inversions). Scalar
multiplication is usually computed using variants of the binary algorithm (double-and-add, NAF, wNAF, etc).
If s is a small integer, optimized formula for [s]P can be used within a s-ary algorithm or with double-base
methods with bases 2 and s. Optimized formulas exists for very small scalars (s ≤ 5). However, the exponential
growth of the number of field operations makes it a very difficult task when s > 5. We present a generic method
to automate transformations of formulas for elliptic curves over prime fields in various systems of coordinates.
Our method uses a directed acyclic graph structure to find possible common subexpressions appearing in the
formula and several arithmetic transformations. It produces efficient formulas to compute [s]P for a large set
of small scalars s. In particular, we present a faster formula for [5]P in Jacobian coordinates. Moreover, our
program can produce code for various mathematical software (Magma) and libraries (PACE).
This paper presents the first version of a software library called PACE ("Prototyping Arithmetic in Cryptography
Easily"). This is a C++ library under LGPL license. It provides number systems and algorithms for prototyping
the arithmetic layer in cryptographic applications. The first version of PACE includes basic support of prime
finite fields and ECC (Elliptic Curve Cryptography) basic algorithms for software implementations.
This paper explores the use of a double-base number system (DBNS) in constant integer multiplication. The
DBNS recoding technique represents constants in a multiple-radix way in the hopes of minimizing computation
during constant multiplication. The paper presents a proof to show that multiple-radix representation diminishes
the number of additions in a sublinear way. We prove Lefevre's conjecture that the multiplication by an integer
constant is achievable in sublinear time. The proof is based on some interesting properties of the double-base
number system. The paper provides numerical data showcasing some of the most recent results.
KEYWORDS: Algorithms, Binary data, Cryptography, Digital signal processing, Information technology, Data processing, Computing systems, Computer engineering, Information security, Mathematics
This paper is an attempt to bring some theory on the top of some previously unproved experimental statements about the double-base number system (DBNS). We use results from diophantine approximation to address the problem of converting integers into DBNS. Although the material presented in this article is mainly theoretical, the proposed algorithm could lead to very efficient implementations.
The choice of modular multiplication algorithms for hardware implementation is not a straightforward problem. In this paper, we analyze and compare FPGA implementations of several state-of-the-art dedicated modular multipliers. For a given constant modulus M, there are several possible methods for generating an optimized modular multiplier, i.e. the dedicated (X x Y) mod M operator. Those modular multipliers can be generated using two kinds of algorithms: those that work for all values of M and those that only work for specific values of the modulo such as 2n ± 1. Several algorithms will be compared for both kind of algorithms. We also deal with two FPGA families, Virtex E and Virtex-II from Xilinx, to measure the impact of new specific built-in resources such as small embedded multipliers. The synthesizable VHDL files of the generated modular multipliers will be available on a web page.
We present an improvement of BKM: a shift-and-add algorithm based on the CORDIC that allows fast computation of complex exponential and logarithm functions. BKM is accelerated by the use of a redundant binary number system. Unlike the previous redundant CORDIC methods, we do not need neither to calculate the scale factor during the computation, nor to double the number of iterations. So our algorithm is suitable for an efficient hardware implementation.
Access to the requested content is limited to institutions that have purchased or subscribe to SPIE eBooks.
You are receiving this notice because your organization may not have SPIE eBooks access.*
*Shibboleth/Open Athens users─please
sign in
to access your institution's subscriptions.
To obtain this item, you may purchase the complete book in print or electronic format on
SPIE.org.
INSTITUTIONAL Select your institution to access the SPIE Digital Library.
PERSONAL Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.