Nadia El Mrabet

Laurent-Stéphane Didier, Léa Glandus, Nadia El Mrabet et al.

This paper presents a novel method to compare two numbers in Residue Number System (RNS) using an additional modulus, which is often already available because it is required in modular computations and digital signal processing scaling.Our method provides the comparison of two integers in the full range of the RNS base. It does not require moduli of a special form, unlike other state-of-the-art methods that are restricted to specific RNS bases or require bounds on input numbers. Our approach only requires one single conversion to a mixed radix representation with a complexity of O(n2), which can be reduced to O(log(n)) in time with parallelization. This provides a significant advantage over classical methods and more recent competitive methods which work under restrictions. This opens perspectives for advancements in challenging RNS operations such as division, scaling, and cryptographic applications.

Duc-Phong Le, Nadia El Mrabet, Safia Haloui et al.

In their seminar paper, Miyaji, Nakabayashi and Takano introduced the first method to construct families of prime-order elliptic curves with small embedding degrees, namely k = 3, 4, and 6. These curves, so-called MNT curves, were then extended by Scott and Barreto, and also Galbraith, McKee and Valenca to near prime-order curves with the same embedding degrees. In this paper, we extend the method of Scott and Barreto to introduce an explicit and simple algorithm that is able to generate all families of MNT curves with any given cofactor. Furthermore, we analyze the number of potential families of these curves that could be obtained for a given embedding degree $k$ and a cofactor h. We then discuss the generalized Pell equations that allow us to construct particular curves. Finally, we provide statistics of the near prime-order MNT curves.

Nadia El Mrabet, Laurent Poinsot

Pairings are particular bilinear maps, and as any bilinear maps they factor through the tensor product as group homomorphisms. Besides, nothing seems to prevent us to construct pairings on other abelian groups than elliptic curves or more general abelian varieties. The point of view adopted in this contribution is based on these two observations. Thus we present an elliptic curve free study of pairings which is essentially based on tensor products of abelian groups (or modules). Tensor products of abelian groups are even explicitly computed under finiteness conditions. We reveal that the existence of pairings depends on the non-degeneracy of some universal bilinear map, called the canonical bilinear map. In particular it is shown that the construction of a pairing on $A\times A$ is always possible whatever a finite abelian group $A$ is. We also propose some new constructions of pairings, one of them being based on the notion of group duality which is related to the concept of non-degeneracy.