### RNS arithmetic in ${\mathbb F}_{p^k}$ and application to fast pairing computation

S. Duquesne

##### Abstract

In this work, we are interested in arithmetic in large prime field and their extensions of small degree. We explain why it is very interesting to use RNS arithmetic for the base field ${\mathbb F}_p$ when computations in ${\mathbb F}_{p^k}$ 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 prove that using RNS can considerably decrease the number of basic operations required for a pairing computation in many popular situations.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
sylvain duquesne @ univ-rennes1 fr
History
Short URL
https://ia.cr/2010/555

CC BY

BibTeX

@misc{cryptoeprint:2010/555,
author = {S.  Duquesne},
title = {RNS arithmetic in ${\mathbb F}_{p^k}$ and application to fast pairing computation},
howpublished = {Cryptology ePrint Archive, Paper 2010/555},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/555}},
url = {https://eprint.iacr.org/2010/555}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.