Efficient polynomial time algorithms computing industrial-strength primitive roots
| dc.creator | Dubrois, Jacques | |
| dc.creator | Dumas, Jean-Guillaume | |
| dc.date | 2004-09-14 | |
| dc.date | 2008-12-09 | |
| dc.date.accessioned | 2026-07-07T12:10:19Z | |
| dc.date.available | 2026-07-07T12:10:19Z | |
| dc.description | E. Bach, following an idea of T. Itoh, has shown how to build a small set of numbers modulo a prime p such that at least one element of this set is a generator of $\pF{p}$\cite{Bach:1997:sppr,Itoh:2001:PPR}. E. Bach suggests also that at least half of his set should be generators. We show here that a slight variant of this set can indeed be made to contain a ratio of primitive roots as close to 1 as necessary. We thus derive several algorithms computing primitive roots correct with very high probability in polynomial time. In particular we present an asymptotically $O^{\sim}(\sqrt{\frac{1}ε}log^1.5(p) + \log^2(p))$ algorithm providing primitive roots of $p$ with probability of correctness greater than $1-ε$ and several $O(log^α(p))$, $α\leq 5.23$ algorithms computing "Industrial-strength" primitive roots with probabilities e.g. greater than the probability of "hardware malfunctions". | |
| dc.identifier | https://arxiv.org/abs/cs/0409029 | |
| dc.identifier | http://arxiv.org/abs/cs/0409029 | |
| dc.identifier | Information Processing Letters 97, 2 (2006) 41-45 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/209905 | |
| dc.subject | Symbolic Computation | |
| dc.subject | Number Theory | |
| dc.title | Efficient polynomial time algorithms computing industrial-strength primitive roots | |
| dc.type | text |