5
$\begingroup$

May someone please explain what the notations in the image means?

Modulous notation

In general, for a modulus $q$, what does the $+$ in here $\bmod^+ q$ indicate? What does the $\pm$ in here $\bmod^\pm q$ mean?

$\endgroup$
2
  • 4
    $\begingroup$ I don't think this is standard notation. Where did you find it? You should provide a reference. Guessing, it sounds like that defines the range of representatives, in the first line it would be $\{0,\ldots,q-1\}$ and in the second $\{-2^{d-1},\ldots,2^{d-1}-1\}$, but that's just a guess $\endgroup$
    – Daniel
    Aug 4, 2022 at 16:51
  • 1
    $\begingroup$ It's in the Dilithium, round 3 specification documents. $\endgroup$
    – user15651
    Aug 4, 2022 at 23:49

1 Answer 1

11
$\begingroup$

From the NIST Post-Quantum Cryptography Round 3 submission for Crystals-Kyber:

Modular reductions. For an even (resp. odd) positive integer α, we define $r' = r\bmod^± α$ to be the unique element $r'$in the range $-\frac{α}{2} < r' \le \frac{α}{2}$ (resp. $-\frac{α-1}{2} \le r' \le \frac{α-1}{2}$) such that $r' = r\bmod α$. For any positive integer α, we define $r' = r\bmod^+ α$ to be the unique element $r'$ in the range $0 ≤ r' < α$ such that $r' = r\bmod α$. When the exact representation is not important, we simply write $r' = r\bmod α$.

It is probably also available elsewhere, but this was my source.

$\endgroup$
5
  • 1
    $\begingroup$ I think the proof of Gauss's lemma used in quadratic reciprocity had similar ideas of a "centered" mod p instead of the usual 0 thru p-1. $\endgroup$
    – qwr
    Aug 5, 2022 at 5:48
  • 2
    $\begingroup$ I wish this definition had used $r'\equiv r\pmod\alpha$ where there is $r'=r\bmod\alpha$. The former means that $r'-r$ is a multiple of $\alpha$. The later, unless otherwise specified, tends to mean what they write $r'=r\bmod^+\alpha$. See e.g. FIPS 186-4. $\endgroup$
    – fgrieu
    Aug 5, 2022 at 6:08
  • $\begingroup$ Since the OP was asking about Dilithium, I checked and the definition is the same, except they added a sentence "We will sometimes refer to this as a centered reduction modulo α" $\endgroup$ Aug 5, 2022 at 13:55
  • 1
    $\begingroup$ I wish floating-point fmod() operator had been defined in this fashion, rather than as yielding a floating-point remainder in a manner that isn't a modular equivalence class. $\endgroup$
    – supercat
    Aug 5, 2022 at 20:33
  • 1
    $\begingroup$ @fgrieu arguably the notation should look something like $r' \stackrel{\operatorname{mod}\alpha}= r$ or perhaps $r' \in \{r|\operatorname{mod}\alpha\}$. I always found it weird to write $r' \equiv r\quad (\operatorname{mod}\alpha)$ because $r' \equiv r$ already looks like a strong equality between $r$ and $r'$, which it is not. $\endgroup$ Aug 5, 2022 at 20:58

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.