Trinomial moduli are essential for speeding up modular arithmetic in finite fields—especially when working with hardware that uses fixed-bit registers and Chinese remainder theorem. Though their form may appear simple, they conceal profound connections to contemporary algebraic number theory and adjacent domains. In this brief blog, I draw on Robert Dougherty-Bliss’s YouTube talk “Modular Arithmetic with Trinomial Moduli” and use the reference paper Robert Dougherty-Bliss, Mits Kobayashi, Natalya Ter-Saakov, Eugene Zima, Dyadically resolving trinomials for fast modular arithmetic, arXiv:2508.11043. https://doi.org/10.48550/arXiv.2508.11043 to guide a Wolfram Language–based exploration of the subject.

Basics

The trinomial of x of order
n
that we are interested here looks like
n
x
-
m
x
+1
with positive integers
1<m<n
. The authors, Robert Dougherty-Bliss, Mits Kobayashi, Natalya Ter-Saakov and Eugene Zima, started from the computation of the following modular inverses:
Out[]//TraditionalForm=
Use the modular inverse function to quickly compute the results above. All moduli are
-
2
(
k
2
)
:
In[]:=
Table[​​With[{mod=2^(5*i)-2^(3*i)+1},ModularInverse[2^(5*i)-2^i+1,mod]-mod],{i,1,8}]
Out[]=
{-4,-16,-64,-256,-1024,-4096,-16384,-65536}
In[]:=
Log2@(-%)
Out[]=
{2,4,6,8,10,12,14,16,18,20}
The underlying reason is the pair of trinomial satisfies the following extended Bezout equation. Use PolynomialExtendedGCD to find the solution:
In[]:=
PolynomialExtendedGCD[x^5-x+1,x^5-x^3+1,x]
Out[]=
{1,{-
2
x
,1+
2
x
}}
We can interpret the solution in the following way:
In[]:=
FullSimplify[(x^5-x+1)*(-x^2)+(x^5-x^3+1)*(1+x^2)]==1
Out[]=
True
Mod
(x^5-x^3+1)
on both side of the equation Replace
x
with
k
2
we immediately have the pattern for the moduli equation at the beginning. More generally, we are looking pairs of trinomial of given order
n
,
T
1
(x)
and
T
2
(x)
, such that
-1
T
2
(
k
2
)
=f(
k
2
)(mod
T
1
(
k
2
))
for all integer
k
with a fixed polynomial
f
. This also requires that that the fraction term the result from PolynomialExtendedGCD to be
1/
p
2
for some integer
p
. In the example above the polynomial
f
is
f(x)=-
2
x
.
Dougherty-Bliss’s paper discovers that one has to choose the trinomial pairs such that their resultant is a
±
power of 2 (including 1 =
0
2
). Thus the dyadic part in the title means that the resultant is just a prime power of 2, regardless of its sign. Lets take a look at another example:
In[]:=
Resultant[x^20-x^4+1,x^20-x^18+1,x]
Out[]=
64
In[]:=
PolynomialExtendedGCD[x^20-x^4+1,x^20-x^18+1,x]
Out[]=
1,
1
32
(16-16
6
x
-16
10
x
+16
12
x
-16
14
x
+32
16
x
-16
18
x
),
1
32
(16+16
4
x
+16
6
x
-16
12
x
-16
16
x
+16
18
x
)
Then the following two ways to compute moduli are equivalent:
In[]:=
Table[ModularInverse[x^20-x^4+1,x^20-x^18+1],{x,2^Range[10]}]
Out[]=
{320993,485204948993,558725663570132993,599758954179909356879873,632588568410929022545734664193,664289558557292978039321582425341953,696813222054490150437740713328188265070593,730728518260532699290823553483651424394760159233,766241924448695808230897715517910705739807611202568193,803467489635415772822555967901039929769464725893698354675713}
In[]:=
Table​​With[{mod=x^20-x^18+1},Mod[ModularInverse[32,mod]*(16-16
6
x
-16
10
x
+16
12
x
-16
14
x
+32
16
x
-16
18
x
),mod]],{x,2^Range[10]}
Out[]=
{320993,485204948993,558725663570132993,599758954179909356879873,632588568410929022545734664193,664289558557292978039321582425341953,696813222054490150437740713328188265070593,730728518260532699290823553483651424394760159233,766241924448695808230897715517910705739807611202568193,803467489635415772822555967901039929769464725893698354675713}
The key takeaway here is that we have extremely efficient algorithm to find
-1
(
k
2
)
(mod
n
2
-
m
2
+1)
with
n>m
without the expensive modular inverse operation. The modular inverse is simply a trinomial itself:
In[]:=
k.
2
*2^n.-k.-2^m.-k.^2//Expand
Out[]=
-k.+2m.
2
-
1-k.+m.+n.
2
+
-k.+2n.
2
But
n
2
-
m
2
+1=0
in this finite field, we can further simplify the expression above to only use fixed bit operation
-1
(
k
2
)
=
m-k
2
-
n-k
2
+
n
2
-
m
2
+1
, which can be implemented in BitVector efficiently to avoid overflow and division on the finite field. Check that the three expressions are equivalent with
k=5
with
20
x
-
18
x
+1=
20
(
i
2
)
-
18
(
i
2
)
+1
for positive integer
i
. Notice that the last step is free of Mod function:
In[]:=
Table[​​With[{mod=2^(i*20)-2^(i*18)+1},ModularInverse[32,mod]],{i,1,10}]
Out[]=
{761857,998579896321,1099441259031822337,1166572095221392044195841,1226837264558039520558622703617,1287375243567780650983991907251650561,1350158019806545158238550406251518881693697,1415808107317401125468651318966822547191475732481,1484599391894985174285840643273135246033952357876760577,1556719745770841615601444242306818719331362519573555943833601}
In[]:=
With{k=5,n=20,m=18},TableMod
-k+2m*i
2
-
1-k+(m+n)*i
2
+
-k+2n*i
2
,2^(i*n)-2^(i*m)+1,{i,1,10}
Out[]=
{761857,998579896321,1099441259031822337,1166572095221392044195841,1226837264558039520558622703617,1287375243567780650983991907251650561,1350158019806545158238550406251518881693697,1415808107317401125468651318966822547191475732481,1484599391894985174285840643273135246033952357876760577,1556719745770841615601444242306818719331362519573555943833601}
In[]:=
With{k=5,n=20,m=18},Table
-k+m*i
2
-
-k+n*i
2
+2^(i*n)-2^(i*m)+1,{i,1,10}
Out[]=
{761857,998579896321,1099441259031822337,1166572095221392044195841,1226837264558039520558622703617,1287375243567780650983991907251650561,1350158019806545158238550406251518881693697,1415808107317401125468651318966822547191475732481,1484599391894985174285840643273135246033952357876760577,1556719745770841615601444242306818719331362519573555943833601}
A counterexample. The following resultant is not a power of 2:
In[]:=
Resultant[x^20-x^4+1,x^20-x^9+1,x]
Out[]=
31
In[]:=
PolynomialExtendedGCD[x^20-x^9+1,x^20-x^4+1,x]
Out[]=
1,
1
31
(23+15x-
2
x
-2
3
x
+4
4
x
+8
5
x
+16
6
x
+
7
x
+2
8
x
+4
9
x
+8
10
x
+16
11
x
+
12
x
+2
13
x
+4
14
x
+8
15
x
-15
16
x
+
17
x
+2
18
x
+4
19
x
),
1
31
(8-15x+
2
x
+2
3
x
+4
4
x
-23
5
x
-15
6
x
+
7
x
+2
8
x
-4
9
x
-8
10
x
-16
11
x
-
12
x
-2
13
x
-4
14
x
-8
15
x
+15
16
x
-
17
x
-2
18
x
-4
19
x
)
The inverse of 31 does not have fixed bit operation as
a
2
-
b
2
+
c
2
-
d
2
+1
over modular
n
(
i
2
)
-
m
(
i
2
)
+1
. So it does not produce fixed
f
in
-1
T
2
(
k
2
)
=f(
k
2
)(mod
T
1
(
k
2
))
.
{
20
x
-
9
x
+1,
20
x
-
4
x
+1}
is not going to help to accelerate the modular arithmetic on finite field due to the expensive modular inverse function call.

Reconstruct some diagrams in the paper

Say we have a family of all trinomial functions of certain order
n
. Then we record a pair of dyadically resolved trinomials if the absolute value of their resultant is 1 ,2, 4, 8, 16, ... ,
k
2
. For instance
n=20
with
T
i
(x)=
20
x
-
i
x
+1
:
In[]:=
Module{n=20,r},Tabler=Resultantx.^n-x.^i+1,x.^n-x.^j+1,x.;If[r!=0&&BitAnd[r,r-1]==0,Highlighted[r],r],{i,1,n-1},{j,1,n-1}​​//MatrixForm
Out[]//MatrixForm=
The construction of the cardiac shaped graph uses the similar idea above and we only link
i,j
(indexed point evenly laying on a circle) if
T
i
(x)
and
T
j
(x)
are dyadically resolving. We set the order of trinomials as 200 for good visualization:
In[]:=
LaunchKernels[];
ParallelEvaluate[ds=CreateDataStructure["Queue"]];
In[]:=
circleLayout[n_]:=Table[{Cos[2π/n(i-1)],Sin[2π/n(i-1)]},{i,n}];
In[]:=
With{n=200},ParallelEvaluate[ds["DropAll"]];​​ParallelDo​​Withres=Abs@Resultantx.^n-x.^i+1,x.^n-x.^j+1,x.,​​If[BitAnd[res,res-1]==0&&res!=0,​​ds["Push",{i,j}]​​]​​,{i,1,n-2},{j,i+1,n-1},ProgressReporting->True;​​ueEdges=UndirectedEdge@@@(Join@@ParallelEvaluate[ds["Elements"]]);​​ParallelEvaluate[ds["DropAll"]];​​vc=Thread[Range[n-1]->circleLayout[n-1]];​​g=Graph[ueEdges,​​VertexCoordinates->vc,VertexSize->Tiny​​]​​
The associated adjacent matrix of the graph above:
The distribution of the eigenvalues:
The density of the coprime pairs and dyadically resolved pairs for each order up to 200:

Remark

Since this blog is only a brief excursion into the themes of Robert Dougherty-Bliss’s paper, I have left out some details to keep it concise. I truly enjoy this line of research, which bridges finite fields, algebraic number theory, and striking visualizations. Many thanks to the Experimental Math team for sharing this fascinating topic on YouTube and making it accessible to everyone.

CITE THIS NOTEBOOK

Exploring moduli of dyadically resolved trinomials​
by Shenghui Yang​
Wolfram Community, STAFF PICKS, September 28, 2025
​https://community.wolfram.com/groups/-/m/t/3552427