Time Complexities of Multiple-precision Modular Operations and Related Ratios

Shenghui Su; Ping Luo

Paper 2023/596

Time Complexities of Multiple-precision Modular Operations and Related Ratios

Shenghui Su, College of Computers, Nanjing University of Aero. and Astro.

Ping Luo, Software School, Tsinghua University

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 arithmetic Montgomery multiplication algorithm Time complexity 8-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},
      note = {\url{https://eprint.iacr.org/2023/596}},
      url = {https://eprint.iacr.org/2023/596}
}