Paper 2023/596
Time Complexities of Multiple-precision Modular Operations and Related Ratios
Abstract
Modular arithmetic used for cryptography includes modular adding, modular subtracting, modular multiplying, modular inverting, modular exponentiating etc. In this paper, the authors well analyze the bit complexity of a bitwise modular operation and the time complexity of a non-bitwise modular operation. Besides discuss the clock cycles for one bytewise modular operation utilizing directives from the ATmel 8-bit AVR instruction set. Last, reveal that the ratio of derivate numbers of clock cycles for two modular operations under different modulus lengths is almost a constant.
Note: 12 pages, and Sect 4.5 is supplemented.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Multiple-precision modular arithmeticMontgomery multiplication algorithmTime complexity8-bit AVR instruction set
- Contact author(s)
- idology98 @ gmail com
- History
- 2023-05-04: revised
- 2023-04-26: received
- See all versions
- Short URL
- https://ia.cr/2023/596
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/596,
author = {Shenghui Su and Ping Luo},
title = {Time Complexities of Multiple-precision Modular Operations and Related Ratios},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/596},
year = {2023},
url = {https://eprint.iacr.org/2023/596}
}