Efficient polynomial time algorithms computing industrial-strength primitive roots

Details Efficient polynomial time algorithms computing industrial-strength primitive roots Efficient polynomial time algorithms computing industrial-strength primitive roots

2004-09-14

arxiv.org/abs/cs/0409029v2

Information Processing Letters 97, 2 (2006) 41-45

Computer Science

Symbolic Computation

Scientific paper

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^1.5(p) + \log^2(p))$ algorithm providing primitive roots of $p$ with probability of correctness greater than $1-\epsilon$ and several $O(log^\alpha(p))$, $\alpha \leq 5.23$ algorithms computing "Industrial-strength" primitive roots with probabilities e.g. greater than the probability of "hardware malfunctions".

Affiliated with

Also associated with

No associations

Rating

Efficient polynomial time algorithms computing industrial-strength primitive roots does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient polynomial time algorithms computing industrial-strength primitive roots, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient polynomial time algorithms computing industrial-strength primitive roots will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-415261