2
$\begingroup$

If I have three integers $x,y,z\in \mathbb{F}_{2^n}$,

How do I convert the modulo addition operation into conjunctive normal form (CNF)? $$ (x+y)\pmod{2^n-1}=z $$

$\endgroup$
2
  • $\begingroup$ On the first look, the modulo $2^n-1$ looks nasty (not that I'd expect addition modulo $2^n$ to be nice). I'd start with writing down the equations for $n=2, 3$ to get a feeling. What do you need the formulas for? $\endgroup$
    – j.p.
    Aug 29, 2023 at 8:13
  • $\begingroup$ The question could be a dump of homework, and independently is unclear. It's otherwise on-topic. The reasons why it's unclear do not fit a comment (a first attempt did, but was itself unclear), thus I made an answer out of of these reasons. Please edit the question, clarifying it, and showing where you are stuck in it's resolution. $\endgroup$
    – fgrieu
    Aug 29, 2023 at 10:39

1 Answer 1

1
$\begingroup$

The question's expression $(x+y)\pmod{2^n-1}=z$ is ill-formed when it comes to the use of$\mod{}$, and independently is ambiguous as to what $+$ and$\mod{}$ are in the context.

When there is an opening parenthesis immediately on the left of a$\mod{}$ (as in the question, typeset using \pmod in LaTeX), standard notation is that this$\mod{}$ is not an operator returning a result. Rather it's a qualifier for a congruence on the left. E.g. $u\equiv v\pmod m$ can be read as "$u$ is congruent to $v$ [pause] modulo $m$", and means that $m$ divides the result of $u$ minus $v$, for a definition of divides and minus consistent with the type of $u$, $v$, and $m$.

When there is no opening parenthesis immediately on the left of a$\bmod{}$, it's an operator returning the remainder of the Euclidean division of it's left operand by it's right operand, for a definition of Euclidean division consistent with the (usually identical) type of it's left and right operands. That operator is typeset using \bmod in LaTeX. For non-negative integer operands, that operator is similar to % in C (except that$\mod{}$ is evaluated after what's on it's left, when % has the same priority as operator * in C).

In the following I'll rewrite the question's expression as $$(x+y)\bmod(2^n-1)\,=\,z$$ but that's still ambiguous on what $+$ and$\mod{}$ mean!

We are told that "$x,y,z\in\mathbb F_{2^n}$", thus $x$ $y$ $z$ are not integers, but rather elements of a/the finite field with $2^n$ elements, that is (depending on perspective)

  1. Polynomials with degree less than $n$ and coefficients in $\{0,1\}$ considered as the Boolean field $\mathbb F_2$; e.g. for $n=5$ that could be $x=1+X+X^4$ and $y=X+X^3$
  2. A vector/tuple of $n$ bits $(x_0,x_1,\ldots\,x_{n-1})$; e.g. $x=(1,1,0,0,1)$ and $y=(0,1,0,1,0)$ for the same example. That's the most useful perspective when it comes to CNF.
  3. An integer in range $[0,2^n-1]$ obtained by evaluating the polynomial of the first perspective in $\mathbb Z$ at the point $X=2$, or equivalently by considering the tuple of the second alternative as the little-endian binary representation of an integer; e.g. $x=19$ and $y=10$ for the same example.

Notice that for $n=5$, the integer $2^n-1=31$ in the question represents per perspective 3 the polynomial $1+X+X^2+X^3+X^4$ per perspective 1 and the vector/tuple $(1,1,1,1,1)$ per perspective 2.

Then what addition is used in $x+y$?

  • If that's the additive operation of the field $\mathbb F_{2^n}$, then still with the same example we have $(1+X+X^4)+(X+X^3)=1+X^3+X^4$ per perspective 1, $(1,1,0,0,1)+(0,1,0,1,0)=(1,0,0,1,1)$ per perspective 2, or $19+10=21$ per perspective 3 (notice that $+$ in $\mathbb F_{2^n}$ is not integer addition, rather it works like the ^ operator in C or Python when operating by perspective 3 above; that it, it's bitwise XOR).
  • If that's ordinary integer addition, then we should have $19+10=29$ per perspective 3. That's not a well-defined element of $\mathbb F_{2^5}$ (we'd need to know the irreducible polynomial associated with the field representation, it's not given, so I won't consider that). However the result can be mapped to $\mathbb F_{2^{n+1}}$ by perspective 3 (and that would ne necessary in the first alternative below).

There's a similar ambiguity about if$\mod{}$ yields the remainder per polynomial or integer division, and nothing in the question makes it sure that's the same as for addition. This matters because the result is different. For example $(1+X+X^4)\bmod(1+X+X^2+X^3+X^4)$ is $(X^2+X^3)$ per polynomial division with coefficients in $\mathbb F_2$, but $19\bmod31=19$.

Thus to answer the question, we must first choose one among the 2×2=4 most sensible meanings of the (rewritten) expression in the question! The rest is left as an exercise to the reader, at least until the question is clarified and shows the efforts made towards a resolution, per our policy on homework.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.