Random Primes without Primality Testing - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2022

Random Primes without Primality Testing

Pascal Giorgi
Bruno Grenet
Armelle Perret Du Cray
  • Function : Author
  • PersonId : 1064718
Daniel S. Roche
  • Function : Author
  • PersonId : 1047294


Numerous algorithms call for computation over the integers modulo a randomly-chosen large prime. In some cases, the quasi-cubic complexity of selecting a random prime can dominate the total running time. We propose a new variant of the classic D5 algorithm for "dynamic evaluation", applied to a randomly-chosen (composite) integer. Unlike the D5 principle which has been used in the past to compute over a direct product of fields, our method is simpler as it only requires following a single path after any modulus splits. The transformation we propose can apply to any algorithm in the algebraic RAM model, even allowing randomization. The resulting transformed algorithm avoids any primality tests and will, with constant positive probability, have the same result as the original computation modulo a randomly-chosen prime. As an application, we demonstrate how to compute the exact number of nonzero terms in an unknown integer polynomial in quasi-linear time. We also show how the same algorithmic transformation technique can be used for computing modulo random irreducible polynomials over a finite field.

Dates and versions

lirmm-03784821 , version 1 (23-09-2022)



Pascal Giorgi, Bruno Grenet, Armelle Perret Du Cray, Daniel S. Roche. Random Primes without Primality Testing. ISSAC 2022 - 47th International Symposium on Symbolic and Algebraic Computation, Jul 2022, Lille, France. pp.207-215, ⟨10.1145/3476446.3536191⟩. ⟨lirmm-03784821⟩
14 View
0 Download



Gmail Facebook Twitter LinkedIn More