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 at 16:51
  • 1
    $\begingroup$ It's in the Dilithium, round 3 specification documents. $\endgroup$
    – user15651
    Aug 4 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 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 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 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 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 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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