Scholarlink

<p>We describe a new, highly optimized implementation of number theoretic transforms on processors with SIMD support (AVX, AVX-512, and Neon). For any prime modulus <i>p</i> and any order of the form <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(r = 2^i \cdot 3^j \mathrel {|}p - 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>=</mo> <msup> <mn>2</mn> <mi>i</mi> </msup> <mo>·</mo> <msup> <mn>3</mn> <mi>j</mi> </msup> <mo stretchy="false">|</mo> <mi>p</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, our implementation can automatically generate a dedicated codelet to compute the number theoretic transform of order <i>r</i> over <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\mathbb {F}_p\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="double-struck">F</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation>. New speed-ups were achieved by relying heavily on non-normalized modular arithmetic and allowing for orders <i>r</i> that are not necessarily powers of two.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Implementing number theoretic transforms

  • 期刊论文

  • 发表日期：

    2026年8月5日

查看全文
  • Joris van der Hoeven,
  • Grégoire Lecerf

摘要

We describe a new, highly optimized implementation of number theoretic transforms on processors with SIMD support (AVX, AVX-512, and Neon). For any prime modulus p and any order of the form \(r = 2^i \cdot 3^j \mathrel {|}p - 1\) r = 2 i · 3 j | p - 1 , our implementation can automatically generate a dedicated codelet to compute the number theoretic transform of order r over \(\mathbb {F}_p\) F p . New speed-ups were achieved by relying heavily on non-normalized modular arithmetic and allowing for orders r that are not necessarily powers of two.