Implement Barrett Reduction Techniques in Metal

[moven0831]

Problem

Efficient modular reduction is essential for converting point coordinates into Montgomery form. The current implementation does not use the Montgomery form in Metal, resulting in unnecessary computational overhead.

Details

Integrate efficient Barrett reduction methods within Metal shaders to facilitate the conversion of point coordinates into Montgomery form. Evaluate both "vanilla" Barrett reduction and Barrett-Domb reduction to determine the most performant approach on iOS devices.

Acceptance criteria

• Implement "vanilla" Barrett reduction based on Project Nayuki's algorithm within Metal.
• Implement Barrett-Domb reduction as an alternative method.
• Conduct benchmarks to compare the performance of both methods on iOS devices.
• Select and integrate the most efficient reduction technique into the MSM pipeline based on benchmark results.
• Ensure comprehensive testing to validate the correctness of the reduction methods.

Reference

• "Vanilla" Barrett Reduction Implementation
• Barrett-Domb Reduction Reference
• ZPrize 2023 Prize 2, Tal Derei and Koh Wei Jie