Dave Ishii - Problem Solving Blog

Here are my guesses for the calculation size boundaries for each of those 6 cases.

First, a quick clarification: "Calculation size" in this context isn't a single number but a measure of computational complexity. This complexity depends almost entirely on two things:

1. Dimension ($n$): Fixed at 2 or 3. Because the dimension is so small, the problem is "easy" and can be solved efficiently.

2. Bit-Length ($B$): The size of the numbers in your basis vectors. This is the main factor that will change the calculation time for your examples.

For a fixed dimension $n$, the time to solve SVP is polynomial in the bit-length $B$.

• Lower Bound (all cases): $O(B)$. An algorithm must at least read the numbers, so the bare-minimum effort is proportional to the size of the numbers.

• Upper Bound (2D): $O(B^2)$. 2D SVP is solved by Gauss's algorithm, which is very fast—its complexity is related to the square of the bit-length.

• Upper Bound (3D): $O(B^3)$. 3D SVP can be solved by algorithms like LLL. The complexity is also polynomial, roughly scaling with the cube of the bit-length.

2D Lattice Guesses

Example 1: Orthogonal Basis

• Basis: $\mathbf{b_1} = (1, 0)$, $\mathbf{b_2} = (0, 1)$

• Bit-Length ($B$): Trivial ($B=1$).

• Lower Bound: $O(1)$ operations.

• Upper Bound: $O(1)$ operations.

• Guess: This is a "zero-calculation" problem. Any algorithm would check the vectors, see they are orthogonal and of length 1, and stop immediately.

Example 2: Slightly Skewed Basis

• Basis: $\mathbf{b_1} = (5, 3)$, $\mathbf{b_2} = (2, 2)$

• Bit-Length ($B$): Very small ($B \approx 3$ bits).

• Lower Bound: A few operations (proportional to $B$).

• Upper Bound: A few dozen operations (proportional to $B^2$, so maybe $3^2 = 9$).

• Guess: This is extremely fast. It's equivalent to running the Euclidean algorithm to find $\gcd(5, 2)$. It would take 1-2 reduction steps.

Example 3: Highly Skewed Basis

• Basis: $\mathbf{b_1} = (65537, 65536)$, $\mathbf{b_2} = (65536, 65535)$

• Bit-Length ($B$): Small ($B \approx 16$ bits).

• Lower Bound: Proportional to 16.

• Upper Bound: Proportional to $16^2 = 256$.

• Guess: Still instantaneous for a computer. This is a "bad" basis but for such small numbers, the $O(B^2)$ complexity is trivial. It would perform a few more reduction steps than Example 2, but the calculation size is still very low.

3D Lattice Guesses

Example 1: Orthogonal Basis

• Basis: $\mathbf{b_1} = (1, 0, 0)$, $\mathbf{b_2} = (0, 1, 0)$, $\mathbf{b_3} = (0, 0, 1)$

• Bit-Length ($B$): Trivial ($B=1$).

• Lower Bound: $O(1)$ operations.

• Upper Bound: $O(1)$ operations.

• Guess: Identical to the 2D orthogonal case. It's a "zero-calculation" problem.

Example 2: Symmetric, Non-Orthogonal Basis

• Basis: $\mathbf{b_1} = (15, -7, -7)$, etc.

• Bit-Length ($B$): Very small ($B \approx 4$ bits).

• Lower Bound: Proportional to 4.

• Upper Bound: Proportional to $4^3 = 64$.

• Guess: Very fast. A 3D reduction algorithm (like LLL) would perform a handful of vector swaps and subtractions and finish.

Example 3: Highly Skewed "Bad" Basis

• Basis: $\mathbf{b_1} = (1, 1894885908, 0)$, etc.

• Bit-Length ($B$): Moderate ($B \approx 31$ bits, as $1.8 \times 10^9 \approx 2^{31}$).

• Lower Bound: Proportional to 31.

• Upper Bound: Proportional to $31^3 \approx 30,000$.

• Guess: This is the only example with a non-trivial calculation size. The algorithm must perform many arithmetic operations (additions, multiplications, divisions) on 31-bit numbers. While still "instant" (microseconds) on a modern computer, its calculation size is thousands of times larger than any of the other examples. This is where you first see the algorithm actually having to do work.

Here's the generalization for the upper and lower boundaries for 2D and 3D SVP, based on the bit-length $B$ of the largest number in your basis vectors.

The most important takeaway is that for a fixed, small dimension (like 2 or 3), the problem is not exponentially hard. The difficulty scales polynomially with the size of the numbers ($B$), not the dimension.

Lower Boundary (For both 2D and 3D)

The lower bound is determined by the "cost of reading the input." An algorithm can't solve the problem without at least looking at all the numbers.

• Generalization: $O(B)$

• Explanation: The input consists of a fixed number of integers (4 for 2D, 9 for 3D). The algorithm must read each of these integers, and the time this takes is proportional to their bit-length, $B$. Therefore, the absolute minimum time required is linear in $B$.

Upper Boundary (The "Hardest Case")

The upper bound is determined by the worst-case performance of the best-known algorithm for that dimension.

2D SVP

• Algorithm: Gauss's Reduction Algorithm (which is essentially the Euclidean algorithm for vectors).

• Generalization: $O(B^2)$

• Explanation: The Gauss-Lagrange algorithm is guaranteed to find the shortest vector in 2D. Its computational complexity is well-known to be polynomial. It performs a number of steps related to $\log(B)$, but each step involves arithmetic operations (like division) on numbers of size $B$. This results in a total bit-complexity that is quadratic in $B$.

3D SVP

• Algorithm: LLL Algorithm (Lenstra–Lenstra–Lovász).

• Generalization (Classic): $O(B^3)$

• Generalization (Modern): $O(B^2)$

• Explanation: This is slightly more complex as algorithms have improved.

  • The classic LLL algorithm's complexity analysis (when fixing the dimension $n=3$) involves operations on numbers that can grow during the calculation, leading to a worst-case bound of $O(B^3)$.

  • More modern variants of LLL (like $L^2$) use clever floating-point arithmetic to control the size of the numbers, achieving a faster worst-case bound of $O(B^2)$.

For practical purposes, you can think of both 2D and 3D SVP as having a worst-case complexity of $O(B^2)$ using the best algorithms. The $O(B^3)$ bound is a more traditional, but still valid, upper bound for 3D if you are using a simpler LLL implementation.