Upper bounds for least witnesses and generating sets

 Access to full text

 Full (PDF)

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.) 

1. Karl K. Norton, A character-sum estimate and applications