May someone please explain what the notations in the image means?
In general, for a modulus $q$, what does the $+$ in here $\bmod^+ q$ indicate? What does the $\pm$ in here $\bmod^\pm q$ mean?
$\begingroup$
$\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$– DanielAug 4 at 16:51
-
1$\begingroup$ It's in the Dilithium, round 3 specification documents. $\endgroup$– user15651Aug 4 at 23:49
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
-
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$– qwrAug 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$– supercatAug 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