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.
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
Reference