×
Costa, Edgar; Gerbicz, Robert; Harvey, David

A search for Wilson primes. (English) Zbl 1370.11003

Math. Comput. 83, No. 290, 3071-3091 (2014).
Summary: A Wilson prime is a prime \( p\) such that \( (p-1)! = -1 \pmod {p^2}\). We report on a search for Wilson primes up to \( 2 \times 10^{13}\), and describe several new algorithms that were used in the search. In particular, we give the first known algorithm that computes \( (p-1)! \pmod {p^2}\) in average polynomial time per prime.

Cited in 9 Documents

MSC:

11A07 Congruences; primitive roots; residue systems
11Y16 Number-theoretic algorithms; complexity

Software:

PARI/GP; gmp; NTL
Cite Review PDF
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

Values of B such that p = prime(n) satisfies (p-1)! == -1-B*p (mod p^2), i.e., p is a near-Wilson prime.
Near-Wilson primes (p = prime(n) satisfying (p-1)! == -1-A250406(n)*p (mod p^2)) with A250406(n) < 10.
a(n) is the nearest integer to log(log(10^n)).

References:

[1] David H. Bailey, FFTs in external or hierarchical memory, Journal of Supercomputing 4 (1990), 23-35.
[2] N. G. W. H. Beeger, Quelques remarques sur les congruences \( r^{p-1} \equiv 1 \pmod {p^2}\) et \( (p-1)! \equiv -1 \pmod {p^2}\), Messenger of Mathematics 43 (1913), 72-84. · JFM 44.0227.01
[3] -, On the congruence \( (p-1)! \equiv -1 \pmod {p^2}\), Messenger of Mathematics 49 (1920), 177-178.
[4] Bruce C. Berndt, Ronald J. Evans, and Kenneth S. Williams, Gauss and Jacobi sums, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. · Zbl 0906.11001
[5] Daniel J. Bernstein, Fast multiplication and its applications, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 325 – 384. · Zbl 1208.68239
[6] Alin Bostan, Pierrick Gaudry, and Éric Schost, Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator, SIAM J. Comput. 36 (2007), no. 6, 1777 – 1806. · Zbl 1210.11126 · doi:10.1137/S0097539704443793
[7] Richard P. Brent and H. T. Kung, A regular layout for parallel adders, IEEE Trans. Comput. 31 (1982), no. 3, 260 – 264. · Zbl 0477.94037 · doi:10.1109/TC.1982.1675982
[8] S. Chowla, B. Dwork, and Ronald Evans, On the mod \?&sup2; determination of ((\?-1)/2\atop(\?-1)/4), J. Number Theory 24 (1986), no. 2, 188 – 196. · Zbl 0596.10003 · doi:10.1016/0022-314X(86)90102-2
[9] Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. · Zbl 0786.11071
[10] Richard Crandall, Karl Dilcher, and Carl Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), no. 217, 433 – 449. · Zbl 0854.11002
[11] Claus Diem, On the complexity of some computational problems in the Turing model, Preprint, http://www.math.uni-leipzig.de/ diem/preprints/turing.pdf, 2011. · Zbl 1258.68057
[12] Harvey Dubner, Searching for Wilson primes, J. Recreational Math. 21 (1989), no. 1, 19-20. · Zbl 0678.10001
[13] Carl-Erik Fröberg, Diagonalization of Hermitian matrices, Math. Tables Aids Comput. 12 (1958), 219 – 220. · Zbl 0083.35204
[14] Carl-Erik Fröberg, Investigation of the Wilson remainders in the interval 3\le \?&lt;50,000, Ark. Mat. 4 (1963), 479 – 499 (1963). · Zbl 0108.04502 · doi:10.1007/BF02591598
[15] Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979 – 1005. · Zbl 1192.68926 · doi:10.1137/070711761
[16] Karl Goldberg, A table of Wilson quotients and the third Wilson prime, J. London Math. Soc. 28 (1953), 252 – 256. · Zbl 0050.26705 · doi:10.1112/jlms/s1-28.2.252
[17] Törbjorn Granlund, The gnu Multiple Precision Arithmetic Library (Version 5.0.5), http://gmplib.org/.
[18] David Harvey, Faster arithmetic for number-theoretic transforms, preprint http://arxiv.org/abs/1205.2926, 2012. · Zbl 1284.65195
[19] Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. · Zbl 1059.11001
[20] K. E. Kloss, Some number-theoretic calculations, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 335 – 336. · Zbl 0141.03902
[21] Esayas George Kundert, A von Staudt-Clausen theorem for certain Bernoullianlike numbers and regular primes of the first and second kind, Fibonacci Quart. 28 (1990), no. 1, 16 – 21. · Zbl 0694.10013
[22] Serge Lang, Cyclotomic fields I and II, 2nd ed., Graduate Texts in Mathematics, vol. 121, Springer-Verlag, New York, 1990. With an appendix by Karl Rubin. · Zbl 0704.11038
[23] Emma Lehmer, Questions, Discussions, and Notes: A Note on Wilson’s Quotient, Amer. Math. Monthly 44 (1937), no. 4, 237 – 238. · JFM 63.0106.05 · doi:10.2307/2300697
[25] Hendrik W. Lenstra Jr., Euclidean number fields. I, Math. Intelligencer 2 (1979/80), no. 1, 6 – 15. · Zbl 0433.12004 · doi:10.1007/BF03024378
[26] G. B. Mathews, Theory of numbers, 2nd ed, Chelsea Publishing Co., New York, 1961.
[27] Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. · Zbl 0833.68049
[29] Paulo Ribenboim, The book of prime number records, Springer-Verlag, New York, 1988. · Zbl 0642.10001
[30] Paulo Ribenboim and Wilfrid Keller, Die welt der primzahlen: Geheimnisse und rekorde, Springer-Verlag, New York, 1996.
[31] A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281 – 292 (German, with English summary). · Zbl 0223.68007
[32] Arnold Schönhage, Andreas F. W. Grotefeld, and Ekkehart Vetter, Fast algorithms, Bibliographisches Institut, Mannheim, 1994. A multitape Turing machine implementation. · Zbl 0853.68108
[33] Victor Shoup, NTL: a library for doing number theory (Version 5.5.2), http://www.shoup.net/ntl/.
[34] The PARI Group, Bordeaux, PARI/GP, version 2.3.5, 2010, available from http://pari.math.u-bordeaux.fr/.
[35] Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187 – 224. · Zbl 0778.11076 · doi:10.1007/BF01272074
[36] Lawrence C. Washington, Introduction to cyclotomic fields, 2nd ed., Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1997. · Zbl 0966.11047
[37] Douglas Wikström, On the \?-ary GCD-algorithm in rings of integers, Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 3580, Springer, Berlin, 2005, pp. 1189 – 1201. · Zbl 1084.11068 · doi:10.1007/11523468_96
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.