We develop the affine sieve in the context of orbits of congruence subgroups of semisimple groups acting linearly on affine space. In particular, we give effective bounds for the saturation numbers for points on such orbits at which the value of a given polynomial has few prime factors. In many cases these bounds are of the same quality as what is known in the classical case of a polynomial in one variable where the orbit consists of the integers. When the orbit is the set of integral matrices of a fixed determinant, we obtain a sharp result for the saturation number, and thus establish the Zariski density of matrices all of whose entries are prime numbers. Among the key tools used are explicit approximations to the generalized Ramanujan conjectures for such groups, and sharp and uniform counting of points on such orbits when ordered by various norms.

The public key of the Oil-Vinegar scheme consists of a set of m quadratic equations in m + n variables over a finite field F_q. Kipnis and Shamir broke the balanced Oil-Vinegar scheme where d = n − m = 0 by finding equivalent keys of the cryptosytem. Later their method was extended by Kipnis et al to attack the unbalanced case where 0 < d < m and d is small with a complexity of O(q^{d−1} m^4). This method uses the matrices associated with the quadratic polynomials in the public key, which needs to be symmetric and invertible. In this paper, we give an optimized search method for Kipnis el al’s attack. Moreover, for the case that the finite field is of characteristic 2, we find the situation becomes very subtle, which, however, was totally neglected in the original work of Kipnis et al. We show that the Kipnis-Shamir method does not work if the field characteristic is 2 and d is a small odd number, and we fix the situation by proposing an alternative method and give an equivalent key recovery attack of complexity O(q^{d+1} m^4). We also prove an important experimental observation by Ding et al for the Kipnis-Shamir attack on balanced Oil-Vinegar schemes in characteristic 2.

No abstract uploaded!

We study the problem of density of polynomials in the de Branges spaces ℋ($E$) of entire functions and obtain conditions (in terms of the distribution of the zeros of the generating function$E$) ensuring that the polynomials belong to the space ℋ($E$) or are dense in this space. We discuss the relation of these results with the recent paper of V. P. Havin and J. Mashreghi on majorants for the shift-coinvariant subspaces. Also, it is shown that the density of polynomials implies the hypercyclicity of translation operators in ℋ($E$).

No abstract uploaded!