Implement Optimized Montgomery Multiplication for Metal

[moven0831]

Problem

Montgomery multiplication is a critical operation in multi-scalar multiplication (MSM) that significantly impacts performance. The current implementation lacks an optimized Montgomery multiplication tailored for Metal, leading to slower field arithmetic operations on iOS devices.

Details

Implement an optimized version of Montgomery multiplication specifically designed for Metal to enhance the efficiency of field operations within the MSM process. This optimization should leverage Metal's capabilities to perform modular arithmetic more efficiently, thereby reducing the overall MSM runtime.

Acceptance criteria

• Develop a Metal shader that performs Montgomery multiplication optimized for Metal’s uint data types.
• Benchmark various limb sizes (e.g., 12 to 16 bits) to identify the optimal configuration for Metal on iOS devices.
• Adapt Gregor Mitscha-Baude's approach for limb sizes suitable for Metal.
• Integrate the optimized Montgomery multiplication into the existing MSM pipeline.
• Compare performance against the baseline implementation to demonstrate improvement.
• Create unit tests to verify the correctness of the optimized Montgomery multiplication.

Reference (optional)

• Montgomery Multiplication Overview
• Mitsch-Baude's Montgomery Implementation
• ZPrize 2023 Prize 2, Tal Derei and Koh Wei Jie

[moven0831]

update: the mont_mul backend has been imported from https://github.com/geometryxyz/msl-secp256k1. Noted the source in each imported file. For details please check development branch