| We study several simple problems in number theory and their application to digital signature production. Our emphasis is on probabilistic algorithms.; A problem related to finding square roots modulo a prime is shown to be in deterministic polynomial time. We present an O(log('2)(n)/(epsilon)(,n)) Las Vegas algorithm to find a factor of n, where (epsilon)(,n) is the error probability of the Rabin or Solovay-Strassen primality tests. We give an elementary proof that factoring n is randomly reducible to computing orders modulo n. We give an analysis which shows that the Rabin primality test compares favorably with primality tests derived from algorithms to compute square roots modulo a prime. We study a family of digital signature schemes which has the property that forging signatures is provably as hard as factoring. We give a new Las Vegas algorithm for finding square roots modulo a prime, which is efficient for a large class of primes. |
