Guangwu Xu

Guangwu Xu, Zhiqiang Xu

The class of Fourier matrices is of special importance in compressed sensing (CS). This paper concerns deterministic construction of compressed sensing matrices from Fourier matrices. By using Katz' character sum estimation, we are able to design a deterministic procedure to select rows from a Fourier matrix to form a good compressed sensing matrix for sparse recovery. The sparsity bound in our construction is similar to that of binary CS matrices constructed by DeVore which greatly improves previous results for CS matrices from Fourier matrices. Our approach also provides more flexibilities in terms of the dimension of CS matrices. As a consequence, our construction yields an approximately mutually unbiased bases from Fourier matrices which is of particular interest to quantum information theory. This paper also contains a useful improvement to Katz' character sum estimation for quadratic extensions, with an elementary and transparent proof. Some numerical examples are included.

Hongyuan Qu, Chengliang Tian, Guangwu Xu

Banaszczyk's inequality establishes a tail estimate for the discrete Gaussian measure on a lattice in $\mathbb{R}^n$. This classic result has been influential and plays an important role in lattice-based cryptography. An improvement of the inequality with a transparent proof was given by Tian, Liu and Xu. In this note, we further improve this inequality by imposing an appropriate condition, obtaining a significantly better bound. This refined inequality can be used to investigate dual attacks against the Learning With Errors (LWE) problem.

Guangwu Xu, Yunxiao Tian, Bingxin Yang

Recently, Koç proposed a neat and efficient algorithm for computing \[ x = a^{-1} \pmod {p^k} \] for a prime $p$ based on the exact solution of linear equations using $p$-adic expansions. The algorithm requires only addition and right shift per step. In the first part of this paper, we design an algorithm that computes \[ x = a^{-1} \pmod {n^k} \] for any integers $a, n>1$ with $\gcd(a, n)=1$. The algorithm has a motivation from the schoolbook multiplication and achieves both efficiency and generality. The greater flexibility of our algorithm is explored by utilizing the built-in arithmetic of computer architecture, e.g., $n=2^{64}$, and experimental results show significant improvements. This paper also contains some results on modular inverse based on an alternative proof of correctness of Koç algorithm. For the computation of modular inverses when the modulus is a special power of a prime $p$ (i.e., of the form $p^{2^s}$), an efficient algorithm was developed by Dumas and later improved by Hurchalla. These methods are based on Hensel lifting and perform particularly well when $p=2$ and $2^s$ matches the native bit width of a computer. In the second part of the paper, we present a generalization of these methods to moduli of the form $n^{2^s}$ for any integer $n>1$. The derivation of our algorithm follows from a simple algebraic manipulation.