A search for Wilson primes

Costa, Edgar; Gerbicz, Robert; Harvey, David

doi:10.1090/S0025-5718-2014-02800-7

A search for Wilson primes
HTML articles powered by AMS MathViewer

by Edgar Costa, Robert Gerbicz and David Harvey PDF

Math. Comp. 83 (2014), 3071-3091 Request permission

Abstract:

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.

References

David H. Bailey, FFTs in external or hierarchical memory, Journal of Supercomputing 4 (1990), 23–35.
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.
—, On the congruence $(p-1)! \equiv -1 \pmod {p^2}$, Messenger of Mathematics 49 (1920), 177–178.
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. MR 1625181
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. MR 2467550
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. MR 2299425, DOI 10.1137/S0097539704443793
Richard P. Brent and H. T. Kung, A regular layout for parallel adders, IEEE Trans. Comput. 31 (1982), no. 3, 260–264. MR 648375, DOI 10.1109/TC.1982.1675982
S. Chowla, B. Dwork, and Ronald Evans, On the mod $p^2$ determination of $\left ({(p-1)/2\atop (p-1)/4}\right )$, J. Number Theory 24 (1986), no. 2, 188–196. MR 863654, DOI 10.1016/0022-314X(86)90102-2
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Richard Crandall, Karl Dilcher, and Carl Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), no. 217, 433–449. MR 1372002, DOI 10.1090/S0025-5718-97-00791-6
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.
Harvey Dubner, Searching for Wilson primes, J. Recreational Math. 21 (1989), no. 1, 19–20.
Carl-Erik Fröberg, Diagonalization of Hermitian matrices, Math. Tables Aids Comput. 12 (1958), 219–220. MR 100351, DOI 10.1090/S0025-5718-1958-0100351-8
Carl-Erik Fröberg, Investigation of the Wilson remainders in the interval $3\leq p<50,000$, Ark. Mat. 4 (1963), 479–499 (1963). MR 174510, DOI 10.1007/BF02591598
Martin Fürer, Faster integer multiplication, SIAM J. Comput. 39 (2009), no. 3, 979–1005. MR 2538847, DOI 10.1137/070711761
Karl Goldberg, A table of Wilson quotients and the third Wilson prime, J. London Math. Soc. 28 (1953), 252–256. MR 55358, DOI 10.1112/jlms/s1-28.2.252
Törbjorn Granlund, The gnu Multiple Precision Arithmetic Library (Version 5.0.5), http://gmplib.org/.
David Harvey, Faster arithmetic for number-theoretic transforms, preprint http://arxiv.org/abs/1205.2926, 2012.
Henryk Iwaniec and Emmanuel Kowalski, Analytic number theory, American Mathematical Society Colloquium Publications, vol. 53, American Mathematical Society, Providence, RI, 2004. MR 2061214, DOI 10.1090/coll/053
K. E. Kloss, Some number-theoretic calculations, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 335–336. MR 190057, DOI 10.6028/jres.069B.035
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. MR 1035125
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. MR 1029028, DOI 10.1007/978-1-4612-0987-4
Emma Lehmer, Questions, Discussions, and Notes: A Note on Wilson’s Quotient, Amer. Math. Monthly 44 (1937), no. 4, 237–238. MR 1523917, DOI 10.2307/2300697
Emma Lehmer, Questions, Discussions, and Notes: On the Congruence $(p-1)!\equiv -1 (\operatorname {mod} p^2)$, Amer. Math. Monthly 44 (1937), no. 7, 462. MR 1524028, DOI 10.2307/2301133
Hendrik W. Lenstra Jr., Euclidean number fields. I, Math. Intelligencer 2 (1979/80), no. 1, 6–15. MR 558668, DOI 10.1007/BF03024378
G. B. Mathews, Theory of numbers, Chelsea Publishing Co., New York, 1961. 2nd ed. MR 0126402
Christos H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Reading, MA, 1994. MR 1251285
Erna H. Pearson, On the congruences $(p-1)!\equiv -1$ and $2^{p-1}\equiv 1\,(\textrm {mod}\,p^{2})$, Math. Comp. 17 (1964), 194–195. MR 159780, DOI 10.1090/S0025-5718-1963-0159780-0
Paulo Ribenboim, The book of prime number records, Springer-Verlag, New York, 1988. MR 931080, DOI 10.1007/978-1-4684-9938-4
Paulo Ribenboim and Wilfrid Keller, Die welt der primzahlen: Geheimnisse und rekorde, Springer-Verlag, New York, 1996.
A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
Arnold Schönhage, Andreas F. W. Grotefeld, and Ekkehart Vetter, Fast algorithms, Bibliographisches Institut, Mannheim, 1994. A multitape Turing machine implementation. MR 1290996
Victor Shoup, NTL: a library for doing number theory (Version 5.5.2), http://www.shoup.net/ntl/.
The PARI Group, Bordeaux, PARI/GP, version 2.3.5, 2010, available from http://pari.math.u-bordeaux.fr/.
Joachim von zur Gathen and Victor Shoup, Computing Frobenius maps and factoring polynomials, Comput. Complexity 2 (1992), no. 3, 187–224. MR 1220071, DOI 10.1007/BF01272074
Lawrence C. Washington, Introduction to cyclotomic fields, 2nd ed., Graduate Texts in Mathematics, vol. 83, Springer-Verlag, New York, 1997. MR 1421575, DOI 10.1007/978-1-4612-1934-7
Douglas Wikström, On the $l$-ary GCD-algorithm in rings of integers, Automata, languages and programming, Lecture Notes in Comput. Sci., vol. 3580, Springer, Berlin, 2005, pp. 1189–1201. MR 2184711, DOI 10.1007/11523468_{9}6