Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'487'895
Articles rated: 2609

29 March 2024
 
  » arxiv » cs.SC/0409029

 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
AffiliationLMC), Jean-Guillaume Dumas (LMC
AbstractE. 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   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  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






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica