# RNS arithmetic in Fpk and application to fast pairing computation

Abstract : In this work, we are interested in arithmetic on large prime field and their ex-tensions of small degree. We explain why it is very interesting to use RNS arithmetic forthe base field $\mathbb{F}p$ when computations in $\mathbb{F}p^k$ have to be done, essentially thanks to lazyreduction. This is for example the case for pairing computations on ordinary curves (asMNT or BN curves). We show that using RNS can considerably decrease the number ofbasic operations required for a pairing computation in many popular situations.
Keywords :
Document type :
Journal articles
Domain :

https://hal.archives-ouvertes.fr/hal-00687220
Contributor : Estelle Nivault <>
Submitted on : Friday, June 11, 2021 - 9:59:50 AM
Last modification on : Saturday, June 12, 2021 - 3:35:11 AM

### File

hal-00687220.pdf
Files produced by the author(s)

### Citation

Sylvain Duquesne. RNS arithmetic in Fpk and application to fast pairing computation. Journal of Mathematical Cryptology, De Gruyter, 2011, 5 (1), pp.51-88. ⟨10.1515/jmc.2011.006⟩. ⟨hal-00687220⟩

Record views