Abstract
In this thesis, we are interested in the problem of implementing point multiplication by a scalar on elliptic curves defined over prime fields. We address this problem both at the level of point multiplication algorithms and at the level of the arithmetic of the curve or the underlying body. The originality of the work presented here is that it does not deal with each aspect separately. Indeed we have always tried to develop the arithmetic at a given level keeping in mind its link with the lower or higher levels.The present thesis consists of three parts. The first part is devoted to the state of the art concerning the arithmetic of elliptic curves. Chapter 1 is an overview of the main properties of elliptic curves and of the different formulas for adding points according to the chosen coordinate system. In chapter 2, we present the main methods of point multiplication by a scalar, both for curves defined on prime fields and for curves defined on binary fields.The second part deals with the study of new point addition formulas on curves and the new point multiplication algorithms that can be derived from them. Chapter 3 details the new point addition formulas, as well as the so-called "Fibonacci" algorithm and addition. In chapter 4 we present a type of addition chains, the differential addition chains, naturally adapted to the formulas introduced in the previous chapter, then we propose a construction of particular chains, in order to deduce the most efficient point multiplication algorithm possible.The third part deals with the RNS representation and its adaptation to the arithmetic of elliptic curves. In chapter 5 we recall the main properties of the RNS representation. In chapter 6, we propose particular RNS bases allowing to improve the efficiency of the calculations. Then, in chapter 7, we propose a modular inversion algorithm in RNS. Finally, chapter 8 is devoted to the study of the complexity of the sums of modular products according to the chosen representation system, and then to the development of the formulas of addition of points on the curves in order to take advantage of the specificity of RNS.