Dyadically Resolving Trinomials for Fast Modular Arithmetic

Abstract

Residue number systems based on pairwise relatively prime moduli are a powerful tool for accelerating integer computations via the Chinese Remainder Theorem. We study a structured family of moduli of the form 2n−2k+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$2^{n} - 2^{k} + 1$\end{document}, originally proposed for their efficient arithmetic and bit-level properties. These trinomial moduli support fast modular operations and exhibit scalable modular inverses. We investigate the problem of constructing large sets of pairwise relatively prime trinomial moduli of fixed bit length. By analyzing the corresponding trinomials xn−xk+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$x^{n} - x^{k} + 1$\end{document}, we establish a sufficient condition for coprimality based on polynomial resultants. This leads to a graph-theoretic model where maximal sets correspond to cliques in a compatibility graph, and we use maximum clique-finding algorithms to construct large examples in practice. Based on the theory of graph colorings, polynomial resultants, and properties of cyclotomic polynomials, we also prove upper bounds on the size of such sets as a function of n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$n$\end{document}.