Paper 2024/1054
Optimized Computation of the Jacobi Symbol
, Mysten Labs, Mysten LabsAbstract
The Jacobi Symbol is an essential primitive in cryptographic applications such as primality testing, integer factorization, and various encryption schemes. By exploring the interdependencies among modular reductions within the algorithmic loop, we have developed a refined method that significantly enhances computational efficiency. Our optimized algorithm, implemented in the Rust language, achieves a performance increase of 72% over conventional textbook methods and is twice as fast as the previously fastest known Rust implementation. This work not only provides a detailed analysis of the optimizations but also includes comprehensive benchmark comparisons to illustrate the practical advantages of our methods. Our algorithm is publicly available under an open-source license, promoting further research on foundational cryptographic optimizations.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- jacobi symboloptimizationcryptographyprimality testingRust
- Contact author(s)
-
jonas @ mystenlabs com
kostas @ mystenlabs com - History
- 2024-06-30: approved
- 2024-06-28: received
- See all versions
- Short URL
- https://ia.cr/2024/1054
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1054,
author = {Jonas Lindstrøm and Kostas Kryptos Chalkias},
title = {Optimized Computation of the Jacobi Symbol},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1054},
year = {2024},
url = {https://eprint.iacr.org/2024/1054}
}
