Scholarlink

This paper investigates the design of a Polynomial Modular Number System (PMNS) for 256-bit prime field arithmetic on 8-bit architectures. To fit coefficients into 8-bit words, we target a basis matrix \(\textbf{B}\) with \(\left\| \textbf{B}\right\| _{1}<2^8\) and dimension \(n>31\) . We first demonstrate that standard LLL reduction is effective, achieving this 8-bit target for a wide range of parameters and approaching the heuristic theoretical limits for small \(\gamma \) . However, for large \(\gamma \) or as the dimension grows, a gap emerges between LLL’s output and the theoretical minimum. We prove the existence of a global minimum and propose a local-improvement framework using Integer Linear Programming (ILP). This work establishes LLL as a powerful initializer and provides a principled algorithmic foundation for purpose-specific PMNS optimization.

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

On the Feasibility of 256-Bit Prime Field Arithmetic via PMNS on 8-Bit Architectures

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Daichi Aoki,
  • Tsuyoshi Takagi

摘要

This paper investigates the design of a Polynomial Modular Number System (PMNS) for 256-bit prime field arithmetic on 8-bit architectures. To fit coefficients into 8-bit words, we target a basis matrix \(\textbf{B}\) with \(\left\| \textbf{B}\right\| _{1}<2^8\) and dimension \(n>31\) . We first demonstrate that standard LLL reduction is effective, achieving this 8-bit target for a wide range of parameters and approaching the heuristic theoretical limits for small \(\gamma \) . However, for large \(\gamma \) or as the dimension grows, a gap emerges between LLL’s output and the theoretical minimum. We prove the existence of a global minimum and propose a local-improvement framework using Integer Linear Programming (ILP). This work establishes LLL as a powerful initializer and provides a principled algorithmic foundation for purpose-specific PMNS optimization.