NTT-based Integer Multiplication on AArch64

[吳述宇]

Dear GMP developers,

I am one of the authors of  https://eprint.iacr.org/2026/2366.pdf, David
Shu-Yu Wu.

We have developed fixed-size, constant-time multiplication kernels based on
NTT with RNS. Our measurements show that these kernels can outperform tuned
GMP for operand sizes as small as 88 64-bit limbs on several ARM processors.

Below are our current benchmark results for equal-size multiplication with
two runtime-unknown operands, compared against GMP 6.2.1 (mpn_mul_n). All
measurements are in CPU cycles.
CPU 88 limbs 132 limbs 176 limbs 220 limbs
Cortex-A53 33,998 / 45,702 (+25.6%) 58,052 / 81,564 (+28.8%) 91,772 /
126,862 (+27.7%) 120,239 / 169,507 (+29.1%)
Cortex-A72 26,111 / 28,373 (+8.0%) 45,095 / 49,517 (+8.9%) 72,726 / 74,823
(+2.8%) 100,220 / 99,443 (−0.8%)
Cortex-A76 21,472 / 22,903 (+6.2%) 34,212 / 41,051 (+16.7%) 59,775 / 63,750
(+6.2%) 83,234 / 88,863 (+6.3%)
Neoverse-N1 21,536 / 23,268 (+7.4%) 34,331 / 41,600 (+17.5%) 58,847 /
62,992 (+6.6%) 81,605 / 88,699 (+8.0%)
Neoverse-V1 10,085 / 9,464 (−6.6%) 16,762 / 16,828 (+0.4%) 28,918 / 26,318
(−9.9%) 39,422 / 36,854 (−7.0%)
Neoverse-V2 9,820 / 8,340 (−17.7%) 16,042 / 15,003 (−6.9%) 27,342 / 23,621
(−15.8%) 36,354 / 33,416 (−8.8%)

Each entry reports *our cycles / GMP cycles*, followed by the percentage
reduction in cycles relative to GMP. Positive percentages indicate that our
implementation is faster. The 88- and 132-limb results use our
second-generation implementation; the 176- and 220-limb results use our
first-generation implementation. The crossover and performance gains vary
significantly across microarchitectures.

We would be interested to hear whether the GMP development team sees
potential value in exploring NTT-based multiplication in this operand-size
range for AArch64.

We would appreciate any feedback on the approach and its potential
suitability for GMP.

You can also visit the repo : https://github.com/Aurivelle/BigIntMul

Best regards,

David Shu-Yu Wu


[image: Mailsuite] 寄件者已透過Mailtrack收到通知  ·  退出
<https://u.list-pref-center.com/en/privacy/opt-out/unsubscribe/bee47e2ae6dc70ef8083a4a948f21b776f5f7724/1051dc7d9dd91e21ab8438e81e21fa4b6e59f2dcbd71923b0fdf00105f6c972f3966c9be215ba707e66fd6fbfb00870ec77931b98e883cc56f77c50c98b835d8>
26/11/10 下午08:07:51