Micciancio defined a generalization of cyclic lattices, called ideal lattices. These lattices can be used in cryptosystems to decrease the number of parameters necessary to describe a lattice by a square root, making them more efficient. He proves that the computational intractability of classic lattice problems for these lattices gives rise to provably secure one-way and collision-resistant hash functions. This provable security relies on the assumption that reducing bases of ideal lattices is similar to reducing bases of random lattices. We give an indication that lattice problems in ideal lattices do not represent the general case by providing a distinguisher, which decides in time O(n^4) whether a given basis of rank spans an ideal lattice or not. Using this algorithm we perform a statistical analysis for several dimensions and show that randomly generated lattices are practically never ideal.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

We consider the Laplacian in a strip R(0,d) with the boundary condition which is Dirichlet except at the segment of a length 2a of one of the boundaries where it is switched to Neumann. This operator is known to have a non-empty and simple discrete spectrum for any a>0. There is a sequence 0<a1<a2< of critical values at which new eigenvalues emerge from the continuum when the Neumann window expands. We find the asymptotic behavior of these eigenvalues around the thresholds showing that the gap is in the leading order proportional to (aan)2 with an explicit coefficient expressed in terms of the corresponding threshold-energy resonance eigenfunction.