| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Efficient polynomial time algorithms computing industrial-strength primitive roots | Jacques Dubrois
; Jean-Guillaume Dumas
; | Date: |
14 Sep 2004 | Subject: | Symbolic Computation; Number Theory ACM-class: F.2.1.e;G.4.a;I.1.2.a | cs.SC math.NT | Affiliation: | LMC), Jean-Guillaume Dumas (LMC | Abstract: | 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}{epsilon}}log(p) + log^2(p))$ algorithm providing primitive roots of $p$ with probability of correctness greater than $1-epsilon$ and several $O(log^alpha(p))$, $4 leq alpha leq 4.959$ algorithms computing "Industrial-strength" primitive roots with probabilities e.g. greater than the probability of "hardware malfunctions". | Source: | arXiv, cs.SC/0409029 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |