Lattice reduction over Ring

[chandra chowdhury]

Hi, 

  I have lattice L generated by row vectors 

(1,1,2), (1,2,1) & (4,5,1) over Z_7. It is clear 

that (4,5,1)-3*(1,1,2)-(1,2,1)= (0,0,1) over Z_7. 

So (0,0,1) is on the Lattice L. Is it possible 

to find the shortest vector of L in Sage? Norm is 

normal Euclidean norm. 

Is there any concept of LLL algorithm over Z_7. 

Over integers, we can easily calculate these. 

Best,

Chandra

[Nils Bruin]

On Friday, July 8, 2016 at 10:17:20 AM UTC-7, chandra chowdhury wrote:

Hi, 

  I have lattice L generated by row vectors 

(1,1,2), (1,2,1) & (4,5,1) over Z_7. It is clear 

that (4,5,1)-3*(1,1,2)-(1,2,1)= (0,0,1) over Z_7. 

So (0,0,1) is on the Lattice L. Is it possible 

to find the shortest vector of L in Sage? Norm is 

normal Euclidean norm. 

You'll find that over Z/7Z, the "normal Euclidean norm" is not a norm at all.

Is there any concept of LLL algorithm over Z_7.

No, because there is no concept of "short vector"  that behaves sufficiently well.
 
You can try to find short representatives of vectors by lifting your module over Z/7Z to one over Z

In your case, you'd be looking at the module generated by (1,1,2), (1,2,1),(4,5,1),(7,0,0),(0,7,0),(0,0,7) over Z.
If you run LLL on that, you will get short vectors over Z that reduce to vectors that lie in the module over Z/7Z that you specified.

[Dima Pasechnik]

On Friday, July 8, 2016 at 7:23:01 PM UTC+1, Nils Bruin wrote:

On Friday, July 8, 2016 at 10:17:20 AM UTC-7, chandra chowdhury wrote:

Hi, 

  I have lattice L generated by row vectors 

(1,1,2), (1,2,1) & (4,5,1) over Z_7. It is clear 

that (4,5,1)-3*(1,1,2)-(1,2,1)= (0,0,1) over Z_7. 

So (0,0,1) is on the Lattice L. Is it possible 

to find the shortest vector of L in Sage? Norm is 

normal Euclidean norm. 

You'll find that over Z/7Z, the "normal Euclidean norm" is not a norm at all.

Is there any concept of LLL algorithm over Z_7.

No, because there is no concept of "short vector"  that behaves sufficiently well.

it is not 100% true;  Z_7 is a field, thus you get a vector space, and a coding theory-like problem

of finding a  some sort of measure to see how far apart two vectors are.

For instance it can be Hamming distance (# of coordinates in which two vectors differ), 

and then it's the classical coding theory setup.

Dima

[Nils Bruin]

On Friday, July 8, 2016 at 11:52:11 AM UTC-7, Dima Pasechnik wrote:

No, because there is no concept of "short vector"  that behaves sufficiently well.

it is not 100% true;  Z_7 is a field, thus you get a vector space, and a coding theory-like problem

of finding a  some sort of measure to see how far apart two vectors are.

For instance it can be Hamming distance (# of coordinates in which two vectors differ), 

and then it's the classical coding theory setup.

The key is in the "sufficiently well". If you could find a (positive definite) quadratic form that induces the Hamming weight (note it's called a weight, not a norm!) then we could use Gramm-Schmidt orthogonalization (we wouldn't even need LLL because we're working over a field!). That would probably solve the decoding problem quite efficiently.