18237859. OPTIMIZATION TECHNIQUE FOR MODULAR MULTIPLICATION ALGORITHMS simplified abstract (Intel Corporation)
OPTIMIZATION TECHNIQUE FOR MODULAR MULTIPLICATION ALGORITHMS
Organization Name
Inventor(s)
Kirk S. Yap of Westborough MA (US)
OPTIMIZATION TECHNIQUE FOR MODULAR MULTIPLICATION ALGORITHMS - A simplified explanation of the abstract
This abstract first appeared for US patent application 18237859 titled 'OPTIMIZATION TECHNIQUE FOR MODULAR MULTIPLICATION ALGORITHMS
Simplified Explanation
Methods and apparatus for optimizing modular multiplication algorithms are described in this patent application. These optimization techniques can be applied to different variants of modular multiplication algorithms, such as Montgomery multiplication algorithms and Barrett multiplication algorithms. The goal of these techniques is to reduce the number of serial steps in the Montgomery reduction and Barrett reduction processes.
- The optimization techniques aim to reduce the number of serial steps in modular multiplication algorithms.
- These techniques can be applied to various variants of modular multiplication algorithms, including Montgomery and Barrett multiplication algorithms.
- The optimization techniques allow for parallel execution of modular multiplication operations, resulting in faster computation.
- The number of serial steps in modular reductions is reduced to L, where L is determined by the digit size in bits and the number of digits of the operands.
Potential Applications
- Cryptography: These optimization techniques can be applied to improve the efficiency of modular multiplication operations in cryptographic algorithms, such as RSA and elliptic curve cryptography.
- Computer arithmetic: The techniques can be used to enhance the performance of modular multiplication algorithms in computer arithmetic operations, such as in hardware accelerators or specialized processors.
Problems Solved
- Serial steps in modular multiplication algorithms can be time-consuming and limit the overall performance of the algorithm.
- Traditional modular multiplication algorithms may not fully exploit parallelism, leading to slower computation times.
- The optimization techniques address these issues by reducing the number of serial steps and enabling parallel execution, resulting in faster modular multiplication operations.
Benefits
- Improved efficiency: The optimization techniques reduce the number of serial steps, leading to faster computation times for modular multiplication algorithms.
- Enhanced parallelism: By allowing parallel execution of modular multiplication and reduction operations, the techniques fully exploit the available parallelism, further improving performance.
- Versatility: The techniques can be applied to different variants of modular multiplication algorithms, making them applicable to a wide range of applications in cryptography and computer arithmetic.
Original Abstract Submitted
Methods and apparatus for optimization techniques for modular multiplication algorithms. The optimization techniques may be applied to variants of modular multiplication algorithms, including variants of Montgomery multiplication algorithms and Barrett multiplication algorithms. The optimization techniques reduce the number of serial steps in Montgomery reduction and Barrett reduction. Modular multiplication operations involving products of integer inputs A and B may be performed in parallel to obtain a value C that is reduced to a residual RES. Modular multiplication and modular reduction operations may be performed in parallel. The number of serial steps in the modular reductions are reduced to L, where L serial steps, where w is a digit size in bits, and L is a number of digits of operands=[k/w].
