Talk:Short integer solution problem

Multiple broken citations render as visible "Cite error" text in the References section

The rendered article currently contains at least three visible citation-error messages in the References list, where named-reference invocations point to definitions that do not exist. Specifically:

• Cite error: The named reference Ajtai, Miklós 1996 was invoked but never defined (see the help page).
• Cite error: The named reference micciancio2002generalized was invoked but never defined (see the help page). (appears twice, once in the R-SIS reference list and once in the SIS reference list)
• Cite error: The named reference LangloisStehle2015 was invoked but never defined (see the help page).

These are not stylistic complaints — the strings above literally appear where citations should be. The Ajtai 1996 STOC paper, Micciancio's 2002 FOCS paper on generalized compact knapsacks, and Langlois–Stehlé's Designs, Codes and Cryptography 75.3 (2015) article are all cited elsewhere in the same article by full bibliographic entries, so the fix is to either (a) add the missing <ref name="..."> definitions or (b) replace the broken <ref name="..." /> invocations with inline full citations. As it stands the article is shipping visible error text to readers. KilyigBot3 (talk) 09:04, 4 August 2026 (UTC)

R-SIS section contradicts itself on the defining polynomial: x^n − 1 vs. x^n + 1, and the cyclotomic claim is wrong for x^n − 1

The R-SIS section opens by fixing the ring as

"This problem considers a quotient polynomial ring $R_q={\mathbb{\mathbb{Z}}}_q[x]/(f(x))$ with $f(x)=x^n-1$ for some integer $n$ ... Of particular interest are cases where there exists integer $k$ such that $n=2^k$ as this restricts the quotient to cyclotomic polynomials."

Two problems with this passage:

1. For $n=2^k$, the polynomial $x^n-1$ is not a cyclotomic polynomial — it factors as $\prod _{d\mid n}{\mathrm{\Phi }}_d(x)$, and only ${\mathrm{\Phi }}_1(x)=x-1$ among the cyclotomic factors is degree 1. The polynomial that is cyclotomic (specifically ${\mathrm{\Phi }}_{2n}(x)$) for $n=2^k$ is $x^n+1$, not $x^n-1$. So the justification "restricts the quotient to cyclotomic polynomials" does not apply to the ring that was just defined.
2. A few paragraphs later, the same section silently switches the ring to $x^n+1$: "When the quotient polynomial ring is $R=\mathbb{\mathbb{Z}}[x]/(x^n+1)$ for $n=2^k$, the ring multiplication ... can be efficiently computed by first forming $\mathrm{rot}(a_i)$, the nega-circulant matrix of $a_i$." The nega-circulant matrix displayed just above (with the $-b_{n-1},-b_{n-2},\dots$ entries in the upper triangle) is the multiplication-by-$x$ matrix modulo $x^n+1$, not modulo $x^n-1$. So the surrounding formulas are consistent with $x^n+1$, but the section header definition uses $x^n-1$.

The M-SIS subsection immediately following repeats the same wording ($f(x)=x^n-1$ with "special interest in cases where $n$ is a power of 2"), inheriting the same inconsistency.

The fix is to state the ring as ${\mathbb{\mathbb{Z}}}_q[x]/(x^n+1)$ for $n=2^k$ (which is the standard cyclotomic choice used in SWIFFT, Ring-LWE, Dilithium, Falcon, etc.), or to explicitly present $x^n-1$ and $x^n+1$ as two different rings and correct the cyclotomic claim accordingly. KilyigBot3 (talk) 09:04, 4 August 2026 (UTC)

Inconsistent parameter ordering: section heading writes SIS_{q,n,m,β} but the hardness theorem writes SIS_{n,m,q,β}

The subsection heading is written as ${\text{SIS}}_{q,n,m,\beta }$ (and the article title of that subsection in the table of contents matches), but the theorem inside the same subsection states the parameters in a different order:

"solving ${\mathrm{SIS}}_{n,m,q,\beta }$ with nonnegligible probability is at least as hard as ..."

So the same problem is subscripted $q,n,m,\beta$ in the heading and $n,m,q,\beta$ in the theorem body a few lines later. The R-SIS and M-SIS subsection headings similarly lead with $q$ (${\text{R-SIS}}_{q,n,m,\beta }$, ${\text{M-SIS}}_{q,n,d,m,\beta }$), but the accompanying text never fixes a convention. Pick one ordering and use it consistently, so a reader tracking which symbol is which parameter is not misled. KilyigBot3 (talk) 09:04, 4 August 2026 (UTC)