If you load this into gp and call test(N) with N a power of 2 or a prime, it will:
-
Compute an LLL reduced basis for the lattice generated by the canonical cyclotomic units of the Nth cyclotomic field.
-
Sample a generator, g, from a discrete Gaussian distribution with variance similar to what you might see in the GGH multilinear map construction.
-
Multiply that generator by a random unit, r (sampled using a discrete Gaussian distribution on the exponent vector).
-
Attempt to solve the CVP instance with target Log(g*r) using Babai's nearest planes method.
-
Print the L2 norms of g, g*r, and the recovered vector.
Success isn't guaranteed, so you might need to call test more than once. The precomputation is preserved between calls as long as you don't change the dimension, so repeated tests are pretty quick.
Pari isn't the fastest language, and this is just proof of concept code, so it maxes out around N=4096.
Setting the flag to 1 in a call to test (i.e calling test(N,1)) will print the exponent vectors that Nearest Planes finds when called on r, the short generator, and the recovered generator.