Search

Lattices are a popular field of study in mathematical research, but also in more practical areas like cryptology or multiple-input/multiple-output (MIMO) transmission. In mathematical theory, most often lattices over real numbers are considered. However, in communications, complex-valued processing is usually of interest. Besides, by the use of dual-polarized transmission as well as by the combination of two time slots or frequencies, four-dimensional (quaternion-valued) approaches become more and more important. Hence, to account for this fact, well-known lattice algorithms and related concepts are generalized in this work. To this end, a brief review of complex arithmetic, including the sets of Gaussian and Eisenstein integers, and an introduction to quaternion-valued numbers, including the sets of Lipschitz and Hurwitz integers, are given. On that basis, generalized variants of two important algorithms are derived: first, of the polynomial-time LLL algorithm, resulting in a reduced basis of a lattice by performing a special variant of the Euclidean algorithm defined for matrices, and second, of an algorithm to calculate the successive minima—the norms of the shortest independent vectors of a lattice—and its related lattice points. Generalized bounds for the quality of the particular results are established and the asymptotic complexities of the algorithms are assessed. These findings are extensively compared to conventional real-valued processing. It is shown that the generalized approaches outperform their real-valued counterparts in complexity and/or quality aspects. Moreover, the application of the generalized algorithms to MIMO communications is studied, particularly in the field of lattice-reduction-aided and integer-forcing equalization. [ABSTRACT FROM AUTHOR]

NTRU is a lattice-based cryptosystem built on a convolutional ring of polynomials. There are many generalizations of NTRU in the literature; however, group ring NTRU, or GR-NTRU, is the most reasonable description of NTRU as a general framework to design its variants. Most versions are commutative and are obtained by changing the ring of coefficients while keeping the cyclic structure intact. In this work, we analyze the noncommutative version of GR-NTRU designed with the group ring of dihedral group over the ring of Eisenstein integers. We experimentally test the size of the keyspace of this new variant and find that it is comparable and even larger for certain parameters compared to the existing commutative counterpart. We observe that although it is slightly slow in terms of speed of encryption and decryption, it has higher lattice security. [ABSTRACT FROM AUTHOR]

We define a Mendelsohn triple system (MTS) of order coprime with 3, and having multiplication affine over an abelian group, to be affine, nonramified. By exhibiting a one‐to‐one correspondence between isomorphism classes of affine MTS and those of modules over the Eisenstein integers, we solve the isomorphism problem for affine, nonramified MTS and enumerate these isomorphism classes (extending the work of Donovan, Griggs, McCourt, Opršal, and Stanovský). As a consequence, all entropic MTSs of order coprime with 3 and distributive MTS of order coprime with 3 are classified. Partial results on the isomorphism problem for affine MTS with order divisible by 3 are given, and a complete classification is conjectured. We also prove that for any affine MTS, the qualities of being nonramified, pure, and self‐orthogonal are equivalent. [ABSTRACT FROM AUTHOR]

In this paper, we consider the use of lattice codes over Eisenstein integers for implementing a compute-and-forward protocol in wireless networks when channel state information is not available at the transmitter. We extend the compute-and-forward paradigm of Nazer and Gastpar to decoding Eisenstein integer combinations of transmitted messages at relays by proving the existence of a sequence of pairs of nested lattices over Eisenstein integers in which the coarse lattice is good for covering and the fine lattice can achieve the Poltyrev limit. Using this result, we show that both the outage performance and error-correcting performance of the nested lattice codebooks over Eisenstein integers surpass those of lattice codebooks over integers considered by Nazer and Gastpar with no additional computational complexity. [ABSTRACT FROM PUBLISHER]

We describe a method to perform scalar multiplication on two classes of ordinary elliptic curves, namely E:y² = x³ + Ax in prime characteristic p ≡ 1 mod 4, and E:y² = x³ + B in prime characteristic p ≡ 1 mod 3. On these curves, the 4-th and 6-th roots of unity act as (computationally efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-w-NAF (Non-Adjacent Form) digit expansion of positive integers to the complex base of τ, where τ is a zero of the characteristic polynomial x²-tx+p of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo τ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve. [ABSTRACT FROM AUTHOR]

We describe a method to perform scalar multiplication on two classes of ordinary elliptic curves, namely E:y²=x³+Ax in prime characteristic p≡1mod4, and E:y²=x³+B in prime characteristic p≡1mod3. On these curves, the 4-th and 6-th roots of unity act as (computationally efficient) endomorphisms. In order to optimise the scalar multiplication, we consider a width-w-NAF (Non-Adjacent Form) digit expansion of positive integers to the complex base of τ, where τ is a zero of the characteristic polynomial x²-tx+p of the Frobenius endomorphism associated to the curve. We provide a precomputationless algorithm by means of a convenient factorisation of the unit group of residue classes modulo τ in the endomorphism ring, whereby we construct a digit set consisting of powers of subgroup generators, which are chosen as efficient endomorphisms of the curve. [ABSTRACT FROM AUTHOR]

Abstract: We classify all cyclotomic matrices over the Eisenstein and Gaussian integers, that is, all Hermitian matrices over the Eisenstein and Gaussian integers that have all their eigenvalues in the interval . [Copyright &y& Elsevier]

It is well known that a function can be decomposed uniquely into the sum of an odd and an even function. This notion can be extended to the unique decomposition into the sum of four functions - two of which are even and two odd. These four functions are eigenvectors of the Fourier Transform with four different eigenvalues. That is, the Fourier transformof each of the four components is simply that component multiplied by the corresponding eigenvalue. Some eigenvectors of the discrete Fourier transform of particular interest find application in coding, communication and imaging. Some of the underlying mathematics goes back to the times of Carl Friedrich Gauss. [ABSTRACT FROM AUTHOR]

Abstract: We give a computer-free proof of a theorem of Basak, describing the group generated by 16 complex reflections of order 3, satisfying the braid and commutation relations of the diagram. The group is the full isometry group of a certain lattice of signature over the Eisenstein integers . Along the way we enumerate the cusps of this lattice and classify the root and Niemeier lattices over . [Copyright &y& Elsevier]

Abstract: We prove lower bounds for the complexity of deciding several relations in imaginary, norm-Euclidean quadratic integer rings, where computations are assumed to be relative to a basis of piecewise-linear operations. In particular, we establish lower bounds for deciding coprimality in these rings, which yield lower bounds for gcd computations. In each imaginary, norm-Euclidean quadratic integer ring, a known binary-like gcd algorithm has complexity that is quadratic in our lower bound. [Copyright &y& Elsevier]