Paper 2024/1054 Original: eprint.iacr.org/2024/1054 ↗
Optimized Computation of the Jacobi Symbol
Abstract
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.
- History
- 2024-06-28: last updated
- 2024-06-28: published
- Short URL
- https://ia.cr/2024/1054
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}