The average least witness is 2

Ronald Joseph Burthe Jr.

Acta Arithmetica (1997)

  • Volume: 80, Issue: 4, page 327-341
  • ISSN: 0065-1036

How to cite


Ronald Joseph Burthe Jr.. "The average least witness is 2." Acta Arithmetica 80.4 (1997): 327-341. <>.

author = {Ronald Joseph Burthe Jr.},
journal = {Acta Arithmetica},
keywords = {average least witness; primality testing; zero density estimate; Dirichlet -functions},
language = {eng},
number = {4},
pages = {327-341},
title = {The average least witness is 2},
url = {},
volume = {80},
year = {1997},

AU - Ronald Joseph Burthe Jr.
TI - The average least witness is 2
JO - Acta Arithmetica
PY - 1997
VL - 80
IS - 4
SP - 327
EP - 341
LA - eng
KW - average least witness; primality testing; zero density estimate; Dirichlet -functions
UR -
ER -


  1. [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
  2. [B] E. Bach, Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms, MIT Press, Cambridge, Mass., 1985. Zbl0572.10001
  3. [Bo] E. Bombieri, On the large sieve, Mathematika 12 (1965), 201-225. Zbl0136.33004
  4. [Bu] D. A. Burgess, On character sums and L-series II, Proc. London Math. Soc. 13 (1963), 524-536. Zbl0123.04404
  5. [BE] D. A. Burgess and P. D. T. A. Elliott, The average of the least primitive root, Mathematika 15 (1968), 39-50. Zbl0174.08105
  6. [Bur] R. J. Burthe Jr., Upper bounds for least witnesses and generating sets, this volume, 311-326. 
  7. [C] M. D. Coleman, On the equation b₁p - b₂P₂ = b₃, J. Reine Angew. Math. 403 (1990), 1-66. 
  8. [D] H. Davenport, Multiplicative Number Theory, 2nd ed., Springer, New York, 1980. Zbl0453.10002
  9. [E1] P. Erdős, On pseudoprimes and Carmichael numbers, Publ. Math. Debrecen 4 (1956), 201-206. Zbl0074.27105
  10. [E2] P. Erdős, On the integers relatively prime to n and on a number theoretic function considered by Jacobsthal, Math. Scand. 10 (1962), 163-170. Zbl0202.33002
  11. [G] P. X. Gallagher, A large sieve density estimate near σ = 1, Invent. Math. 11 (1970), 329-339. Zbl0219.10048
  12. [HB] D. R. Heath-Brown, The density of zeros of Dirichlet's L-functions, Canad. J. Math. 31 (1979), 231-240. 
  13. [H] C. Hooley, On the difference of consecutive numbers prime to n, Acta Arith. 8 (1963), 343-347. Zbl0121.04706
  14. [I] H. Iwaniec, On the problem of Jacobsthal, Demonstratio Math. 11 (1978), 225-231. Zbl0378.10029
  15. [Ju1] M. Jutila, A statistical density theorem for L-functions with applications, Acta Arith. 16 (1969), 207-216. 
  16. [Ju2] M. Jutila, On Linnik's constant, Math. Scand. 41 (1977), 45-62. Zbl0363.10026
  17. [Ju3] M. Jutila, Zero-density estimates for L-functions, Acta Arith. 32 (1977), 55-62. 
  18. [LMO] J. L. Lagarias, H. L. Montgomery and A. M. Odlyzko, A bound for the least prime ideal in the Chebotarev density theorem, Invent. Math. 54 (1979), 271-296. Zbl0401.12014
  19. [M] L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), 97-108. Zbl0443.10002
  20. [Mo1] H. L. Montgomery, Mean and large values of Dirichlet polynomials, Invent. Math. 8 (1969), 334-345. Zbl0204.37301
  21. [Mo2] H. L. Montgomery, Zeros of L-functions, Invent. Math., 346-354. Zbl0204.37401
  22. [Mo3] H. L. Montgomery, Topics in Multiplicative Number Theory, Lecture Notes in Math. 227, Springer, New York, 1971. 
  23. [Mo4] H. L. Montgomery, Zeros of L-functions, Chap. 9 of: Ten Lectures on the Interface between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., Providence, R.I., 1994, 163-178. 
  24. [Mot] Y. Motohashi, Lectures on Sieve Methods and Prime Number Theory, Tata Institute of Fundamental Research, Springer, Bombay, 1983. 
  25. [P1] C. Pomerance, A note on the least prime in an arithmetic progression, J. Number Theory 12 (1980), 218-223. Zbl0436.10020
  26. [P2] C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587-593. Zbl0511.10002
  27. [R] M. O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), 128-138. Zbl0426.10006
  28. [Ro] K. A. Rodosskiĭ, On non-residues and zeros of L-functions, Izv. Akad. Nauk SSSR Ser. Mat. 20 (1956), 303-306 (in Russian). 
  29. [Se] A. Selberg, Remarks on sieves, Proc. 1972 Number Theory Conference in Boulder, 1972, 205-216. 

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.