Faster PMNS Multi-precision Multiplications Using Truncated Montgomery Technique

1 Introduction

• PMNS represents numbers with polynomials and offers parallel properties, but large-number polynomials can exceed the word count needed for a multiprecision integer.The paper proposes truncation to reduce the cost of multiprecision coefficients, comparing its approach with.Source: §1 · p. 2

Contributions

• The paper presents a truncated Montgomery-like internal reduction inspired by [DMGR24] and software implementations using AVX512 and IFMA52.The implementations compare full and truncated configurations and count multiplication-accumulation instructions in the vectorized implementation.Source: Contributions · p. 2
• Up to 15% speedup over the full implementation is reported for the truncated Montgomery-like internal reduction on Sapphire Rapids and ZEN 4.The full implementation is reported as competitive with, the state of the art to the authors’ knowledge.Source: Contributions · p. 2

Notations

• The notation defines w as machine-word size, s as the number of machine words per multiprecision number, and a[i] as the ith word of a.It also uses a⟨i⟩ for the ith bit, W for logical OR, and >> for right shift.Source: Notations · pp. 2–3

2 Background on PMNS

• PMNS represents integers modulo p with bounded-coefficient polynomials of degree less than n, evaluated at γ to represent the integer modulo p.When polynomial operations exceed coefficient bounds, internal reduction restores bounded coefficients; degree overflow requires external reduction.Source: §2 · p. 3

2.1 External reduction

• External reduction computes a degree-bounded polynomial congruent to the input modulo E, preserving its value modulo p because E(γ) ≡ 0 mod p.It can also be expressed as a Toeplitz matrix-vector product, for which subquadratic complexity is noted.Source: §2.1 · pp. 3–4

2.2 Internal reduction

• Montgomery-like internal reduction maps a polynomial to a PMNS representation with the same value modulo p, and is efficient when ϕ is a power of two.The method induces a multiplicative factor ϕ^-1 on the output; the paper focuses on this approach and its coefficient-reduction algorithm.Source: §2.2 · pp. 4–5

2.3.1 Parameters generation

• Larger moduli require larger coefficient bounds or larger polynomial degree, creating a tradeoff between degree n and multiprecision coefficients.Building suitable parameters is difficult because p, ρ, n, and ϕ are related.Source: §2.3.1 · p. 5

2.3.2 PMNS complexity

• Multiprecision coefficients can offer a better memory compromise and reduce elementary multiplication cost relative to single-word coefficients, while SIMD vectorization can perform eight multiplications in one vector multiplier.The stated theoretical cost model counts word multiplications, additions, and logic operations; subquadratic polynomial multiplication trades fewer multiplications for more additions.Source: §2.3.2 · pp. 6–7, Table 1 · p. 6

• The paper expects larger polynomial coefficients to improve instruction count compared with single-word coefficients, while complexity depends on n.The chosen polynomial description is equivalent to a matrix-vector representation, which the authors omit for simplicity.Source: §3 · p. 7
• The same algorithms are used for the same operations with multiprecision coefficients; the difference is coefficient size.The multiplication example uses Algorithm 2.Source: §3 · p. 7
• For a PMNS (p, n, γ, ρ, E, ϕ) with E = Xn−λ, a multi-precision coefficient means ρ > 2w, and consequently ϕ = 2sw.Source: §3 · p. 7

4 Polynomial Multiprecision Coefficient using Montgomery Truncation Technique

• Following [DMGR24], the paper applies truncated Montgomery reduction to PMNS internal reduction by combining the approach with coefficient-wise polynomial computation.The prior integer technique evaluates only the most significant words of q × p; here truncation is applied to polynomial coefficient computations.Source: §4 · pp. 8–9, §4.1 · p. 9

4.1 Truncated PMNS software implementation

• The implementation skips least-significant-word products and reconstructs each coefficient using only its high part and the corresponding carry.The PMNS parameters set ϕ = 2^sw, so each polynomial coefficient occupies several machine words.Source: §4.1 · p. 9

4.2 Correctness of the truncated PMNS Montgomery-like internal reduction

• If bT is computed correctly, Algorithm 4 returns S ≡ C × ϕ^-1 mod N with every coefficient bounded by ρ.Theorem 2 states that computing bT requires only coefficient words of weight at least s−1 in Q × M.Source: §4.2 · pp. 11–12
• The truncation is valid because exact division by ϕ makes the sw least-significant bits of C + T zero, allowing carries to be determined without all low words.The correctness argument considers coefficients separately and avoids computing all least-significant words of tk.Source: §4.2 · pp. 11–12

5.1 Theoretical number of multiplications

• Theoretical multiplication counts in Table 3 make the truncated approach’s gain explicit, while executable madd52lo/madd52hi counts exceed the theoretical amount.The implementation performs schoolbook polynomial multiplication coefficient-wise and word-wise.Source: §5.1 · p. 15

5.2 Vectorized implementation

• AVX512/IFMA52 vectorization processes batches of eight values, with combined madd52lo and madd52hi call counts given for full and truncated multiplication.The reported expressions are 5n̄ns^2 for full multiplication and 5n̄ns^2 − n̄n(s − 1)^2 for truncated multiplication.Source: §5.2 · pp. 15–16

5.3 Memory Cost

• Parameter sets chosen specifically for efficient Toeplitz multiplication have increased memory cost.The section compares the memory costs of the authors’ parameter choices with those in.Source: §5.3 · p. 16, Table 4 · p. 16

6.1 Experimentation procedure

• Measurements used two computers, disabled Turbo Boost, warmed the cache, and averaged minimum cycle counts across 1200 random data sets.Each data set’s minimum was taken over 1800 runs after about 1300 warm-up runs.Source: §6.1 · pp. 16–17

6.2 Results

• At 2048 and 4096 bits, conventional schoolbook multiplication outperforms ’s Toeplitz PMNS; at 8192 bits, truncated schoolbook outperforms Toeplitz, though full schoolbook is slower on Xeon.The comparison reports cycle counts for full and truncated multiplication and their ratio across prime sizes.Source: §6.2 · p. 17, Table 5 · p. 18
• Memory moves and other non-multiplication instructions are costly through 4096 bits, and together with less favorable parameters can outweigh Toeplitz’s sub-quadratic advantage.The instruction-count analysis estimates costs for Sapphire Rapids under a perfect-pipeline assumption.Source: §6.2 · pp. 17–18

7 Conclusion

• The truncated Montgomery-like internal reduction improves asymptotic multiplication cost by about 20%.The approach is similar to the improvement in Montgomery reduction for large multiprecision integers proposed by [DMGR24].Source: §7 · p. 18
• The full Montgomery-like implementation uses AVX512/IFMA52 for modulus sizes of 2048, 4096, and 8192 bits and is competitive with the state of the art.The implementation takes advantage of better parameters with smaller memory cost.Source: §7 · pp. 18–19
• The truncated implementation achieves speed-ups up to 15% compared with the full Montgomery-like algorithm.The paper reports equivalent timings or speed-ups up to 20% versus the state of the art for the software implementations, depending on modulus size.Source: §7 · p. 19