• Arithmetic properties of φ(n)/λ(n) and the structure of the multiplicative group modulo n 

    Banks, William David, 1964-; Luca, Florian; Shparlinski, Igor E. (European Mathematical Society, 2006)
    For a positive integer n, we let φ(n) and λ(n) denote the Euler function and the Carmichael function, respectively. We define ξ(n) as the ratio φ(n)/λ(n) and study various arithmetic properties of ξ(n).
  • Average Normalisations of Elliptic Curves 

    Banks, William David, 1964-; Shparlinski, Igor E. (Australian Mathematical Society, 2002)
    Ciet, Quisquater, and Sica have recently shown that every elliptic curve E over a finite field Fp is isomorphic to a curve y2 = x3 +ax+b with a and b of size O(p3/4). In this paper, we show that almost all elliptic curves ...
  • Character Sums over Integers with Restricted g-ary Digits 

    Banks, William David, 1964-; Conflitti, Alessandro; Shparlinski, Igor E. (2002)
    We establish upper bounds for multiplicative character sums and exponential sums over sets of integers that are described by various properties of their digits in a fixed base g ≥ 2. Our main tools are the Weil and ...
  • Coincidences in the values of the Euler and Carmichael functions 

    Banks, William David, 1964-; Friedlander, J. B. (John B.); Luca, Florian; Pappalardi, Francesco; Shparlinski, Igor E. (Polish Academy of Sciences, Institute of Mathematics, 2006)
    The Euler function has long been regarded as one of the most basic of the arithmetic functions. More recently, partly driven by the rise in importance of computational number theory, the Carmichael function has drawn an ...
  • Cryptographic applications of sparse polynomials over finite rings 

    Banks, William David, 1964-; Lieman, Daniel, 1965-; Shparlinski, Igor E.; To, Van Thuong (2001)
    This paper gives new examples that exploit the idea of using sparse polynomials with restricted coefficients over a finite ring for designing fast, reliable cryptosystems and identification schemes.
  • Distribution of Inverses in Polynomial Rings 

    Banks, William David, 1964-; Shparlinski, Igor E. (2001)
    Let IFp be the finite field with p elements, and let F(X) ∈ IFp[X] be a square-free polynomial. We show that in the ring R = IFp[X]/F(X), the inverses of polynomials of small height are uniformly distributed. We also show ...
  • Distributional Properties of the Largest Prime Factor 

    Banks, William David, 1964-; Harman, G. (Glyn), 1956-; Shparlinski, Igor E. (University of Michigan, 2005)
    Let P(n) denote the largest prime factor of an integer n ≥ 2, and put P(1) = 1. In this paper, we study the distribution of the sequence {P(n) : n ≥ 1} over the set of congruence classes modulo an integer q ≥ 2, and we ...
  • Exponential Sums over Mersenne Numbers 

    Banks, William David, 1964-; Conflitti, Alessandro; Friedlander, J. B. (John B.); Shparlinski, Igor E. (2004)
    We give estimates for exponential sums of the form Σn≤N Λ(n) exp(2πiagn/m), where m is a positive integer, a and g are integers relatively prime to m, and Λ is the von Mangoldt function. In particular, our results yield ...
  • An extremely small and efficient identification scheme 

    Banks, William David, 1964-; Lieman, Daniel, 1965-; Shparlinski, Igor E. (2000)
    We present a new identification scheme which is based on Legendre symbols modulo a certain hidden prime and which is naturally suited for low power, low memory applications.
  • An identification scheme based on sparse polynomials 

    Banks, William David, 1964-; Lieman, Daniel, 1965-; Shparlinski, Igor E. (2000)
    This paper gives a new example of exploiting the idea of using polynomials with restricted coefficients over finite fields and rings to construct reliable cryptosystems and identification schemes.
  • Incomplete exponential sums and Diffie-Hellman triples 

    Banks, William David, 1964-; Friedlander, J. B. (John B.); Koniagin, S. V. (Sergeĭ Vladimirovich); Shparlinski, Igor E. (Cambridge University Press, 2006)
    Let p be a prime and 79 an integer of order t in the multiplicative group modulo p. In this paper, we continue the study of the distribution of Diffie-Hellman triples (V-x, V-y, V-xy) by considering the closely related ...
  • Non-residues and primitive roots in Beatty sequences 

    Banks, William David, 1964-; Shparlinski, Igor E. (Australian Mathematical Society, 2006)
    We study multiplicative character sums taken on the values of a non-homogeneous Beatty sequence Bα,β = {⌊αn + β⌋ : n = 1,2,3,…}, where α,β ∈ R, and α is irrational. In particular, our bounds imply that for every fixed ε > ...
  • Nonlinear complexity of the Naor-Reingold pseudo-random function 

    Banks, William David, 1964-; Griffin, Frances; Lieman, Daniel, 1965-; Shparlinski, Igor E. (2000)
    We obtain an exponential lower bound on the non-linear complexity of the new pseudo-random function, introduced recently by M. Naor and O. Reingold. This bound is an extension of the lower bound on the linear complexity ...
  • Number Theoretic Designs for Directed Regular Graphs of Small Diameter 

    Banks, William David, 1964-; Conflitti, Alessandro; Shparlinski, Igor E. (Society for Industrial and Applied Mathematics, 2004)
    In 1989, F. R. K. Chung gave a construction for certain directed h-regular graphs of small diameter. Her construction is based on finite fields, and the upper bound on the diameter of these graphs is derived from bounds ...
  • On the Number of Sparse RSA Exponents 

    Banks, William David, 1964-; Shparlinski, Igor E. (2002)
    An RSA modulus is a product M = pl of two primes p and l. We show that for almost all RSA moduli M, the number of sparse exponents e (which allow for fast RSA encryption) with the property that gcd(e,φ(M)) = 1 (hence RSA ...
  • Prime divisors of palindromes 

    Banks, William David, 1964-; Shparlinski, Igor E. (Springer Verlag, 2005)
    In this paper, we study some divisibility properties of palindromic numbers in a fixed base g ≥ 2. In particular, if PL denotes the set of palindromes with precisely L digits, we show that for any sufficiently large value ...
  • Short Kloosterman Sums for Polynomials over Finite Fields 

    Banks, William David, 1964-; Harcharras, Asma; Shparlinski, Igor E. (2003)
    We extend to the setting of polynomials over a finite field certain estimates for short Kloosterman sums originally due to Karatsuba. Our estimates are then used to establish some uniformity of distribution results in the ...
  • Some Divisibility Properties of the Euler Function 

    Banks, William David, 1964-; Luca, Florian; Shparlinski, Igor E. (Oxford University Press, 2005)
    Let '(・) denote the Euler function, and let a > 1 be a fixed integer. We study several divisibility conditions which exhibit typographical similarity with the standard formulation of the Euler theorem, such as a n ≡ 1 ...
  • Values of Arithmetical Functions Equal to a Sum of Two Squares 

    Banks, William David, 1964-; Luca, Florian; Saidak, Filip; Shparlinski, Igor E. (Oxford University Press, 2005)
    Let '(n) denote the Euler function. In this paper, we determine the order of growth for the number of positive integers n ≤ x for which '(n) is the sum of two square numbers. We also obtain similar results for the Dedekind ...