Short Integer Solution
Find a short nonzero modular relation.
Euclidean SIS · custom regime
Specify q(n), m(n), and the output norm bound β(n)
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| No checked result has been added for this comparison contract. | |||||
Comparison definition & assumptions
- Regime
- Specify q(n), m(n), and the output norm bound β(n)
- Computation
- Classical
- Rigor
- Regime dependent
- Instances
- Uniform matrix
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- An open category template: SIS needs a fixed modulus, density, norm, and success condition before an exponent is meaningful.
- Comparison rules
- No universal SIS exponent is seeded. Define q, m, β, the norm, and the asymptotic variable in the category before ranking results. Use separate categories for SIS∞, Euclidean SIS, and structured matrices.
- Tags