1
$\begingroup$

I am stuck here and can't map the coding part to the algorithm.

$$\underline{\text{Power2Round}_q(r, d)}\\ r := r \bmod^+ q\\ r_0 := r mod^\pm 2^d\\ \textbf{return}\big((r-r_0) / 2^d, r_0\big) $$

What I tried:

int32_t power2round (int32_t *a0, int32_t a) {
    int32_t al;
    a1 = (a + (1 << (D-1)) - 1) >> D;
    *a0 = a - (a1 << D);
    return a1;
}
$\endgroup$
1
  • $\begingroup$ Note that placing images instead of text is not allowed on this site. If you want to format your question using latex you can see the post here. Otherwise at least also copy the text. $\endgroup$
    – Maarten Bodewes
    Sep 4, 2023 at 6:59

1 Answer 1

2
$\begingroup$

Conceptually what is happening with this algorithm is simple, so I will describe that first. To simplify things, I will simply write $a\bmod b$ rather than $a\bmod^+b$ or $a\bmod^{\pm}b$. I'll mention the distinction between those two notations later.

One can always write

$$x = (x\bmod q) + qy$$

where $y$ is the remainder of $x\bmod q$. Note that one can solve for $y$ to get that $y = \frac{x-(x\bmod q)}{q}$. All that Power2Round is doing is computing

  • the remainder $\frac{r-(r\bmod 2^d)}{2^d}$ and
  • modular reduction $r\bmod 2^d$

of a value $r$ that it computes $r = r\bmod q$ to enforce that it has not gotten too large.


Next, we need to go over the difference between $\bmod^+$ and $\bmod^\pm$. Reducing $x\mapsto x\bmod q$ maps $x\in\mathbb{Z}$ to $x\bmod q\in\mathbb{Z}/q\mathbb{Z}$. This later object is known as a "quotient ring". It supports addition and products, like you might expect. The somewhat surprising part of it is that it has many different (but all mutually valid) representations of its elements. For a basic example, one can write

$$\mathbb{Z}/2\mathbb{Z}\cong \{0,1\},$$

or

$$\mathbb{Z}/2\mathbb{Z}\cong \{-2, 3\},$$

or many other options. So to map $x\in\mathbb{Z}\mapsto x\in\mathbb{Z}/q\mathbb{Z}$, we need to fix a representation of $\mathbb{Z}/q\mathbb{Z}$. You can see what these symbols mean on page 6 of the NIST draft standard, where they say

  • $x\bmod^+ q$ denotes the unique representative of $x$ modulo $q$ in the interval $[0, q)$, and
  • $x\bmod^\pm q$ denotes the unique representative of $x$ modulo $q$ in the interval $(-q/2, q/2]$.

I imagine handling these two points above are a significant issue with your code. I won't try to fully deconstruct your code, as honestly I can't really tell what you trying to do. If you want your code to be more interpretatble, I would suggest

  • explicitly defining the functions $x\bmod^+q$ and $x\bmod^\pm q$ that you need first, and ensuring they have the correct functionality (I currently doubt they do)
  • using consistent variable names with the pseudocode you have described, e.g. use $r, d, q, r_0$ in your code as well. This makes it easier to understand what you are trying to do.
$\endgroup$
1
  • $\begingroup$ Good point about the variable naming. Generally, when implementing these kind of things, I'd try to keep the naming intact and provide a reference to what I'm actually implementing in the comments. $\endgroup$
    – Maarten Bodewes
    Sep 4, 2023 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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