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

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

Where $v1$ and $v2$ are the output of the Gaussian lattice reduction algorithm and $\lvert v1 \rvert \leq \lvert v2 \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?

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}{2}$ and equals $-\frac{1}{2}$ when $\theta = \frac{2\pi}{3}$.

  • I was not entirely clear. I do not follow why the inequality proves $ \frac{\pi}{3} \leq \theta \leq \frac{2\pi}{3} $ – gaush Jun 2 '17 at 23:26
  • 1
    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}$. – galvatron Jun 2 '17 at 23:49

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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