Upper bounds for least witnesses and generating sets

Ronald Joseph Burthe Jr.

Acta Arithmetica (1997)

  • Volume: 80, Issue: 4, page 311-326
  • ISSN: 0065-1036

How to cite


Ronald Joseph Burthe Jr.. "Upper bounds for least witnesses and generating sets." Acta Arithmetica 80.4 (1997): 311-326. <http://eudml.org/doc/207046>.

author = {Ronald Joseph Burthe Jr.},
journal = {Acta Arithmetica},
keywords = {upper bounds; least witnesses; generating sets; primality tests; strong pseudoprime},
language = {eng},
number = {4},
pages = {311-326},
title = {Upper bounds for least witnesses and generating sets},
url = {http://eudml.org/doc/207046},
volume = {80},
year = {1997},

AU - Ronald Joseph Burthe Jr.
TI - Upper bounds for least witnesses and generating sets
JO - Acta Arithmetica
PY - 1997
VL - 80
IS - 4
SP - 311
EP - 326
LA - eng
KW - upper bounds; least witnesses; generating sets; primality tests; strong pseudoprime
UR - http://eudml.org/doc/207046
ER -


  1. [AL] L. Adleman and F. Leighton, An O(n¹/10.89) primality testing algorithm, Math. Comp. 36 (1981), 261-266. Zbl0452.10011
  2. [AGP] W. R. Alford, A. Granville and C. Pomerance, On the difficulty of finding reliable witnesses, in: L. M. Adleman and M. D. Huang (eds.), Algorithmic Number Theory, Lecture Notes in Comput. Sci. 877, Springer, Berlin, 1994, 1-16. Zbl0828.11074
  3. [A] N. Ankeny, The least quadratic non-residue, Ann. of Math. 55 (1952), 65-72. Zbl0046.04006
  4. [B1] E. Bach, Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms, MIT Press, Cambridge, Mass., 1985. 
  5. [B2] E. Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), 355-380. Zbl0701.11075
  6. [BH] E. Bach and L. Huelsbergen, Statistical evidence for small generating sets, ibid. 61 (1993), 69-82. Zbl0784.11059
  7. [Buc] A. Buchstab, On those numbers in an arithmetic progression all prime factors of which are small in order of magnitude, Dokl. Akad. Nauk SSSR (N.S.) 67 (1949), 5-8 (in Russian). 
  8. [Bu1] D. A. Burgess, On character sums and primitive roots, Proc. London Math. Soc. 12 (1962), 179-192. Zbl0106.04003
  9. [Bu2] D. A. Burgess, On character sums and L-series II, ibid. 13 (1963), 524-536. Zbl0123.04404
  10. [Bu3] D. A. Burgess, The character-sum estimate with r=3, J. London Math. Soc. (2) 33 (1986), 219-226. Zbl0593.10033
  11. [Bur] R. Burthe, The average witness is 2, PhD dissertation, University of Georgia, 1995. 
  12. [E] P. Erdős, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206. Zbl0074.27105
  13. [FT] E. Fouvry and G. Tenenbaum, Diviseurs de Titchmarsh des entiers sans grand facteur premier, in: K. Nagasaka and E. Fouvry (eds.), Analytic Number Theory (Tokyo 1988), Lecture Notes in Math. 1434, Springer, Berlin, 1990, 86-102. 
  14. [F] V. R. Fridlender, On the least nth power non-residue, Dokl. Akad. Nauk SSSR 66 (1949), 351-352 (in Russian). 
  15. [Fu] A. Fujii, A note on character sums, Proc. Japan. Acad. 49 (1973), 723-726. Zbl0297.10024
  16. [GR] S. Graham and C. J. Ringrose, Lower bounds for least quadratic non-residues, in: B. Berndt, H. Diamond, H. Halberstam and A. Hildebrand (eds.), Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman, Birkhäuser, Boston, 1990, 269-309. Zbl0719.11006
  17. [Gr] A. Granville, On pairs of coprime integers with no large prime factors, Exposiotion. Math. 9 (1991), 335-350. Zbl0745.11043
  18. [HW] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 2nd ed., Oxford University Press, London, 1945. 
  19. [KS] G. Kolesnik and E. G. Straus, On the first occurrence of values of a character, Trans. Amer. Math. Soc. 246 (1978), 385-394. Zbl0399.10037
  20. [KP] S. Konyagin and C. Pomerance, On primes recognizable in deterministic polynomial time, in: R. L. Graham and J. Nesetril (eds.), The Mathematics of Paul Erdős, to appear. 
  21. [Len] H. W. Lenstra, Jr., Miller's primality test, Inform. Process. Lett. 8 (1979), 86-88. Zbl0399.10006
  22. [M] L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), 97-108. Zbl0443.10002
  23. [Mo] H. L. Montgomery, Topics in Multiplicative Number Theory, Lecture Notes in Math. 227, Springer, New York, 1971. Zbl0216.03501
  24. [N1] K. K. Norton, Numbers with small prime factors and the least kth power non-residue, Mem. Amer. Math. Soc. 106 (1971). 
  25. [N2] K. K. Norton, Upper bounds for kth power coset representatives modulo n, Acta Arith. 15 (1969), 161-179. Zbl0177.06801
  26. [Pa] F. Pappalardi, On Artin's conjecture for primitive roots, PhD dissertation, McGill University, 1993. 
  27. [P1] C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593. Zbl0511.10002
  28. [P2] C. Pomerance, Recent developments in primality testing, Math. Intelligencer 3 (1981), 97-105. Zbl0476.10004
  29. [PSW] C. Pomerance, J. L. Selfridge and S. Wagstaff, Jr., The pseudoprimes to 25 · 10⁹, Math. Comp. 35 (1980), 1003-1026. Zbl0444.10007
  30. [R] M. O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), 128-138. Zbl0426.10006
  31. [S] H. Salié, Über den kleinsten positiven quadratischen Nichtrest nach einer Primzahl, Math. Nachr. 3 (1949), 7-8. Zbl0034.17301
  32. [Vi] A. I. Vinogradov, On numbers with small prime divisors, Dokl. Akad. Nauk SSSR (N.S.) 109 (1956), 683-686 (in Russian). Zbl0071.27004
  33. [V] I. M. Vinogradov, On the bound of the least non-residue of nth powers, Bull. Acad. Sci. USSR 20 (1926), 47-58 (= Trans. Amer. Math. Soc. 29 (1927), 218-226.) 

NotesEmbed ?


You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.


Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.