RNS arithmetic in đť”˝ pk and application to fast pairing computation
- 1 January 2011
- journal article
- research article
- Published by Walter de Gruyter GmbH in Journal of Mathematical Cryptology
- Vol. 5 (1), 51-88
- https://doi.org/10.1515/jmc.2011.006
Abstract
In this work, we are interested in arithmetic on large prime field and their extensions of small degree. We explain why it is very interesting to use RNS arithmetic for the base field F-p when computations in F-pk have to be done, essentially thanks to lazy reduction. This is for example the case for pairing computations on ordinary curves (as MNT or BN curves). We show that using RNS can considerably decrease the number of basic operations required for a pairing computation in many popular situations.Keywords
This publication has 30 references indexed in Scilit:
- The number field sieve for integers of low weightMathematics of Computation, 2010
- Ordinary abelian varieties having small embedding degreeFinite Fields and Their Applications, 2007
- A comparison of MNT curves and supersingular curvesApplicable Algebra in Engineering, Communication and Computing, 2006
- Generating More MNT Elliptic CurvesDesigns, Codes and Cryptography, 2006
- Elliptic Curves Suitable for Pairing Based CryptographyDesigns, Codes and Cryptography, 2005
- An RNS Montgomery modular multiplication algorithmIEEE Transactions on Computers, 1998
- A Remark Concerning m-Divisibility and the Discrete Logarithm in the Divisor Class Group of CurvesMathematics of Computation, 1994
- Reducing elliptic curve logarithms to logarithms in a finite fieldIEEE Transactions on Information Theory, 1993
- Modular multiplication without trial divisionMathematics of Computation, 1985
- The Area-Time Complexity of Binary MultiplicationJournal of the ACM, 1981