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

Random Primes without Primality Testing

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

Abstract

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.
Fichier principal
Vignette du fichier
2202.12073.pdf (268.17 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-03784821 , version 1 (11-10-2023)

Identifiers

Cite

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⟩
42 View
14 Download

Altmetric

Share

More