Counting the values taken by algebraic exponential polynomials

We prove an effective mean-value theorem for the values of a non-degenerate, algebraic exponential polynomial in several variables. These objects generalise simultaneously the fundamental examples of linear recurrence sequences and sums of -units. The proof is based on an effective, uniform estimate for the deviation of the exponential polynomial from its expected value. This estimate is also used to obtain a non-effective asymptotic formula counting the norms of these values below a fixed bound.

     

On quadratic fields generated by polynomials

Let be a polynomial of degree d ≥ 2 without multiple roots. Under the assumption of the ABC-conjecture, an asymptotic formula for the number of distinct fields among for has recently been given by Cutter, Granville, and Tucker. We use bounds for character sums to obtain an unconditional lower bound on the number of such fields for . Received: 19 November 2007     

Visible points on multidimensional modular hyperbolas

For integers q?1, s?3 and a with gcd(a,q)=1 and a real U?0, we obtain an asymptotic formula for the number of integer points (u₁,…,us)∈s[1,U] on the s-dimensional modular hyperbola with the additional property gcd(u₁,…,us)=1. Such points have a geometric interpretation as points on the modular hyperbola which are “visible” from the origin. This formula complements earlier results of the first author for the case s=2 and a=1. Moreover, we prove stronger results for smaller U on “average” over all a. The proofs are based on the Burgess bound for short character sums.     

Arithmetic properties of Apery numbers

Let (A_n)_n1 be the sequence of Apéry numbers with a generalterm given by . In thispaper, we prove that both the inequalities (A_n) > c₀ loglog log n and P(A_n) > c₀ (log n log log n)^1/2 hold fora set of positive integers n of asymptotic density 1. Here,(m) is the number of distinct prime factors of m, P(m) is thelargest prime factor of m and c₀ > 0 is an absolute constant.The method applies to more general sequences satisfying botha linear recurrence of order 2 with polynomial coefficientsand certain Lucas-type congruences.     

Distribution of Farey fractions in residue classes and Lang-Trotter conjectures on average

We prove that the set of Farey fractions of order , that is, the set , is uniformly distributed in residue classes modulo a prime provided for any fixed . We apply this to obtain upper bounds for the Lang-Trotter conjectures on Frobenius traces and Frobenius fields ``on average' over a one-parametric family of elliptic curves.

     

On the distribution of inversive congruential pseudorandom numbers in parts of the period

The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present the first nontrivial bounds on the discrepancy of individual sequences of inversive congruential pseudorandom numbers in parts of the period. The proof is based on a new bound for certain incomplete exponential sums.

     

Partitions into two Lehmer numbers

We prove an asymptotic formula for the number of representations of an integer as sum of two Lehmer numbers which implies that under some natural restrictions each sufficiently large integer is a sum of two such numbers.     

The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces

Nguyen and Shparlinski have recently presented a polynomial-time algorithm that provably recovers the signer's secret DSA key when a few consecutive bits of the random nonces k (used at each signature generation) are known for a number of DSA signatures at most linear in log q (q denoting as usual the small prime of DSA), under a reasonable assumption on the hash function used in DSA. The number of required bits is about log ^1/2 q, but can be decreased to log log q with a running time q ^{O(1/log log q)} subexponential in log q, and even further to two in polynomial time if one assumes access to ideal lattice basis reduction, namely an oracle for the lattice closest vector problem for the infinity norm. All previously known results were only heuristic, including those of Howgrave-Graham and Smart who introduced the topic. Here, we obtain similar results for the elliptic curve variant of DSA (ECDSA).     

On the maximal difference between an element and its inverse modulo n

Periodica Mathematica Hungarica -     

Concentration of points on curves in finite fields

We obtain analogues of several recent bounds on the number of solutions of polynomial congruences modulo a prime with variables in short intervals in the case of polynomial equations in high degree extensions of finite fields. In these settings low-dimensional affine spaces play the role of short intervals and thus several new ideas are required.