3
$\begingroup$

In "An Introduction to Mathematical Cryptography"'s section on lattice reduction algorithms, the authors describe Gaussian lattice reduction and claim:

[...] the angle $\theta$ between $v_1$ and $v_2$ satisfies $\left| \cos \theta \right| \leq \frac{\lvert v_1 \rvert}{2\lvert v_2 \rvert}$, so in particular $ \frac{\pi}{3} \leq \theta \leq \frac{2\pi}{3}$.

Where $v_1$ and $v_2$ are the output of the Gaussian lattice reduction algorithm and $\lvert v_1 \rvert \leq \lvert v_2 \rvert $. This result seems very close to a few trigonometric identities but I don't see why this is true in every case. Can someone shine some light on why this guarantees the reduced vectors share an angle in that range?

$\endgroup$
0

1 Answer 1

6
$\begingroup$

When the algorithm ends, $m = 0$, which means that

$$\left| \frac{v_1v_2}{||v_1||^2} \right| \le \frac{1}{2}$$

otherwise, the nearest integer would not be zero (and $m$ would be different from zero).

Now, you just use the well-known cosine similarity: since both vectors are non-zero (because they belong to a basis of the lattice), we have that $v_1 v_2 = || v_1 || || v_2 || \cos \theta$.

Combining those two expressions, we get

$$\left| \frac{v_1v_2}{||v_1||^2} \right| = \left| \frac{|| v_1 || || v_2 || \cos \theta}{||v_1||^2} \right| = \left| \frac{|| v_2 || \cos \theta}{||v_1||} \right| = \frac{|| v_2 || \left| \cos \theta \right|}{||v_1||} \le \frac{1}{2} $$

which gives us $\left| \cos \theta \right| \le \frac{||v_1||}{2||v_2||}$, the expected inequality.

-- EDIT

As galvatron commented, the inequality involving the angle $\theta$ is obtained simply by using the fact that $||v_1|| \le ||v_2||$, which together with the first inequality, gives you $| \cos \theta | \le \frac{||v_2||}{2||v_2||} = \frac{1}{2}$. Therefore, $- \frac{1}{2} \le \cos \theta \le \frac{1}{2}$.

But $\cos \theta$ equals $\frac{1}{2}$ when $\theta = \frac{\pi}{3}$ and equals $-\frac{1}{2}$ when $\theta = \frac{2\pi}{3}$.

$\endgroup$
2
  • $\begingroup$ I was not entirely clear. I do not follow why the inequality proves $ \frac{\pi}{3} \leq \theta \leq \frac{2\pi}{3} $ $\endgroup$
    – gaush
    Jun 2, 2017 at 23:26
  • 3
    $\begingroup$ This follows because $|v_1| \leq |v_2|$. When they are equal, you get $-\frac{1}{2} \leq \cos \theta \leq \frac{1}{2}$. You get the condition since $\cos \frac{2 \pi}{3} = -\frac{1}{2}$ and $\cos \frac{\pi}{3} = \frac{1}{2}$. $\endgroup$
    – user47922
    Jun 2, 2017 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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