Skip to Main Content


AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution


The Joy of Factoring

About this Title

Samuel S. Wagstaff Jr., Purdue University, West Lafayette, IN

Publication: The Student Mathematical Library
Publication Year: 2013; Volume 68
ISBNs: 978-1-4704-1048-3 (print); 978-1-4704-1413-9 (online)
DOI: https://doi.org/10.1090/stml/068
MathSciNet review: MR3135977
MSC: Primary 11Y05; Secondary 11A41, 11Y11, 11Y16

ePUB View full volume as ePUB

PDF View full volume as PDF

Read more about this volume

View other years and volumes:

Table of Contents

PDF Download chapters as PDF

Front/Back Matter

Chapters

References [Enhancements On Off] (What's this?)

References
  • L. M. Adleman, Molecular computation of solutions to combinatorial problems, Science 266 (November 11, 1994), 1021–1024.
  • D. Atkins, M. Graff, A. K. Lenstra, and P. C. Leyland, The magic words are squeamish ossifrage, ASIACRYPT ’94 Proceedings of the 4th International Conference on the Theory and Applications of Cryptology, pp. 263–277, Springer-Verlag, London, UK, 1995.
  • W. Alford, A. Granville, and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. 139 (1994), 703–722.
  • M. Agrawal, N. Kayal, and N. Saxena, PRIMES is in P, Ann. of Math. 160 (2004), 781–793.
  • A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29–68.
  • W. R. Alford and C. Pomerance, Implementing the self-initializing quadratic sieve on a distributed network, Number Theoretic and Algebraic Methods in Computer Science (Moscow) (A. van der Poorten, I. Shparlinski, and H. G. Zimmer, eds.), 1993, pp. 163–174.
  • V. I. Arnold, Lengths of periods of continued fractions of square roots of integers, Funct. Anal. Other Math. 2 (2009), 151–164.
  • E. Bach, Analytic Methods in the Analysis and Design of Number-Theoretic Algorithms, The MIT Press, Cambridge, Massachusetts, 1985.
  • L. Blum, M. Blum, and M. Shub, A simple unpredictable pseudo-random number generator, SIAM J. Comput. 15 (1986), 364–383.
  • R. P. Brent and G. L. Cohen, A new lower bound for odd perfect numbers, Math. Comp. 53 (1989), 431–437.
  • D. Boneh and G. Durfee, Cryptanalysis of RSA with private key $d$ less than $n^{0.292}$, IEEE Trans. on Info. Theory 46(4) (2000), 1339–1349.
  • E. T. Bell, Mathematics: Queen and Servant of Science, McGraw-Hill, New York, 1951.
  • D. J. Bernstein, Detecting perfect powers in essentially linear time, Math. Comp. 67 (1998), 1253–1283.
  • D. Boneh and M. Franklin, Identity based encryption from the Weil pairing, Advances in Cryptology—Proc. CRYPTO ’01 (Springer-Verlag, Berlin, New York), Lecture Notes in Computer Science, vol. 2139, 2001, pp. 213–229.
  • N. Bliss, B. Fulan, S. Lovett, and J. Sommars, Strong divisibility, cyclotomic polynomials, and iterated polynomials, Amer. Math. Monthly 120 (2013), 519–536.
  • J. P. Buhler and D. Harvey, Irregular primes to 163 million, Math. Comp. 80 (2011), 2435–2444.
  • J. Buhler, H. W. Lenstra, Jr., and C. Pomerance, Factoring integers with the number field sieve, The Development of the Number Field Sieve (Springer-Verlag, Berlin, New York) (A. K. Lenstra and H. W. Lenstra, Jr., eds.), Lecture Notes in Mathematics, vol. 1554, 1993, pp. 50–94.
  • J. Brillhart, D. H. Lehmer, and J. L. Selfridge, New primality criteria and factorizations of $2^m\pm 1$, Math. Comp. 29 (1975), 620–647.
  • John Brillhart, D. H. Lehmer, J. L. Selfridge, Bryant Tuckerman, and S. S. Wagstaff, Jr., Factorizations of $b^n \pm 1$, $b$ = 2, 3, 5, 6, 7, 10, 11, 12 up to high powers, Third ed., Contemporary Mathematics, vol. 22, Amer. Math. Soc., Providence, Rhode Island, 2002, Electronic book available at http://www.ams.org/bookstore/conmseries.
  • J. Brillhart, P. L. Montgomery, and R. D. Silverman, Tables of Fibonacci and Lucas factorizations, Math. Comp. 50 (1988), 251–260.
  • D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices Amer. Math. Soc. 46 (1999), 202–213.
  • R. P. Brent, An improved Monte Carlo factorization method, BIT 20 (1980), 176–184.
  • —, Some integer factorization algorithms using elliptic curves, Australian Computer Science Communications 8 (1986), 149–163.
  • —, On computing factors of cyclotomic polynomials, Math. Comp. 61 (1993), 131–149.
  • —, Computing Aurifeuillian factors, Computational Algebra and Number Theory (Sydney, 1992) (Dordrecht), Math. Appl., vol. 325, Kluwer Acad. Publ., 1995, pp. 201–212.
  • J. Brillhart and J. L. Selfridge, Some factorizations of $2^n\pm 1$ and related results, Math. Comp. 21 (1967), 87–96, Corrigendum, ibid., 251.
  • E. Bach and J. Shallit, Algorithmic Number Theory, Volume I: Efficient Algorithms, The MIT Press, Cambridge, Massachusetts, 1996.
  • P. T. Bateman, J. L. Selfridge, and S. S. Wagstaff, Jr., The new Mersenne conjecture, Amer. Math. Monthly 96 (1989), 125–128.
  • D. A. Buell, Binary Quadratic Forms, Springer-Verlag, New York, 1989.
  • B. D. Beach and H. C. Williams, Some computer results on periodic continued fractions, Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing, LSU, Baton Rouge, LA, 1971, pp. 133–146.
  • R. Baillie and S. S. Wagstaff, Jr., Lucas pseudoprimes, Math. Comp. 35 (1980), 1391–1417.
  • R. P. Brent and P. Zimmermann, Ten new primitive binary trinomials, Math. Comp. 78 (2009), 1197–1199.
  • —, Modern Computer Arithmetic, Cambridge University Press, 2010.
  • —, The great trinomial hunt, Notices Amer. Math. Soc. 58 (2) (2011), 233–239.
  • E. Canfield, P. Erdős, and C. Pomerance, On a problem of Oppenheim concerning “factorisatio numerorum”, J. Number Theory 17 (1983), 1–28.
  • W.-L. Chang, M. Guo, and M. S.-H. Ho, Fast parallel molecular algorithms for DNA-based computation: factoring integers, IEEE Trans. on Nanobioscience 4(2) (2005), 149–163.
  • J.-S. Coron and A. May, Deterministic polynomial time equivalence of computing the RSA secret key and factoring, J. Cryptology 20(1) (2007), 39–50.
  • D. Coppersmith, Solving homogeneous linear equations over GF(2) via block Wiedemann algorithm, Math. Comp. 62 (1994), 333–350.
  • —, Finding a small root of a bivariate integer equation; factoring with high bits known, Advances in Cryptology—Eurocrypt ’96 (Springer-Verlag, Berlin), Lecture Notes in Computer Science, vol. 1070, 1996, pp. 178–189.
  • —, Finding a small root of a univariate modular equation, Advances in Cryptology—Eurocrypt ’96 (Springer-Verlag, Berlin), Lecture Notes in Computer Science, vol. 1070, 1996, pp. 155–165.
  • —, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, J. Cryptology 10(4) (1997), 233–260.
  • R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Second ed., Springer-Verlag, New York, 2005.
  • A. J. C. Cunningham and H. J. Woodall, Factorisation of $y^n \mp 1$, $y$ $=$ $2$, $3$, $5$, $6$, $7$, $10$, $11$, $12$ up to High Powers $(n)$, Francis Hodgson, London, 1925.
  • L. Davis (ed.), Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991.
  • H. Dubner and R. Dubner, The development of a powerful, low-cost computer for number theory applications, J. Rec. Math. 18 (1986), 81–86.
  • M. Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, Abh. Math. Sem. Hansischen Univ. 14 (1941), 197–272.
  • D. S. Dummit and R. M. Foote, Abstract Algebra, Third ed., John Wiley & Sons, New York, 2004.
  • W. Diffie and M. Hellman, New directions in cryptography, IEEE Trans. on Info. Theory IT-22(6) (1976), 644–654.
  • K. Dickman, On the frequency of numbers containing prime factors of a certain relative magnitude, Ark. Mat., Astronomi och Fysik 22A, 10 (1930), 1–14.
  • L. E. Dickson, History of the Theory of Numbers, Volume I, Divisibility and Primality, Carnegie Institute of Washington, Reprinted by Chelsea Publishing Company, New York, 1971, originally published in 1919.
  • J. D. Dixon, Asymptotically fast factorization of integers, Math. Comp. 36 (1981), 255–260.
  • C. Ding, G. Xiao, and W. Shan, The stability theory of stream ciphers, Lecture Notes in Computer Science, vol. 561, Springer-Verlag, New York, 1991.
  • P. Erdős and M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math. 62 (1940), 738–742.
  • P. Erdős and C. Pomerance, On the number of false witnesses for a composite number, Math. Comp. 46 (1986), 259–279.
  • P. Erdős, On the normal number of prime factors of $p-1$ and some related problems concerning Euler’s $\phi$-function, Quarterly J. Math. 6 (1935), 205–213.
  • —, On pseudoprimes and Carmichael numbers, Publications Mathematicae Debrecen 4 (1956), 201–206.
  • N. Estibals, Compact hardware for computing the Tate pairing over 128-bit-security supersingular curves, Pairing-based cryptography—Pairing 2010 (Springer-Verlag, Berlin), Lecture Notes in Computer Science, vol. 6487, 2010, pp. 397–416.
  • P. Erdős and S. S. Wagstaff, Jr., The fractional parts of the Bernoulli numbers, Illinois J. Math. 24 (1980), 104–112.
  • Jan Feitsma, The pseudoprimes below $2^{64}$, 2013. See the URL http://www.janfeitsma.nl/math/psp2/.
  • J. Franke, T. Kleinjung, C. Paar, J. Pelzl, C. Priplata, and C. Stahlke, SHARK: a realizable special hardware sieving device for factoring 1024-bit integers, Workshop on Special Purpose hardware for attacking cryptographic systems (SHARCS), 2005, pp. 27–37.
  • C. F. Gauss, Disquisitiones Arithmeticae, G. Fleischer, Leipzig, 1801, English translation by A. A. Clarke published by Yale University Press, 1966, reprinted by Springer-Verlag, 1986.
  • A. Gérardin, Machine à congruences, 70e Congrès des Sociétés Savantes de Paris et des Départements, Section des Sciences (Gauthier-Villars, Paris), vol. II, 1937.
  • S. Goldwasser and J. Kilian, Almost all primes can be quickly certified, Proc. Eighteenth Annual ACM Symp. on the Theory of Computing (STOC), Berkeley, May 28-30, 1986, ACM, 1986, pp. 316–329.
  • T. Goto and K. Okeya, All harmonic numbers less than $10^{14}$, Japan J. Indust. Appl. Math. 24 (2007), 275–288.
  • S. W. Golomb, Shift Register Sequences, Revised ed., Aegean Park, 1982.
  • A. Granville and P. Pleasants, Aurifeuillian factorization, Math. Comp. 75 (2007), 497–508.
  • A. Granville, It is easy to determine whether a given integer is prime, Bull. Amer. Math. Soc. (N.S.) 42 (2005), 3–38.
  • R. K. Guy and J. L. Selfridge, What drives an aliquot sequence?, Math. Comp. 29 (1975), 101–107.
  • W. Geiselmann and R. Steinwandt, A dedicated sieving hardware, PKC 2003 (Springer-Verlag, Berlin), Lecture Notes in Computer Science, vol. 2567, 2003, pp. 254–266.
  • —, Yet another sieving device, CT-RSA 2004 (Springer-Verlag, Berlin), Lecture Notes in Computer Science, vol. 2964, 2004, pp. 278–291.
  • R. K. Guy, Unsolved Problems in Number Theory, Third ed., Springer-Verlag, New York, 2004.
  • J. Gower and S. S. Wagstaff, Jr., Square form factorization, Math. Comp. 77 (2008), 551–588.
  • R. W. Hamming, Numerical Methods for Scientists and Engineers, International Series in Pure and Applied Mathematics, McGraw-Hill, New York, 1962.
  • W. B. Hart, A one line factoring algorithm, J. Aust. Math. Soc. 92 (2012), 61–69.
  • I. N. Herstein, Abstract Algebra, Third ed., John Wiley & Sons, New York, 1999.
  • N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Proceedings of Cryptography and Coding (Springer-Verlag, Berlin), Lecture Notes in Computer Science, vol. 1355, 1997, pp. 131–142.
  • G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number $n$, Quart. J. Math. 48 (1917), 76–92.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth ed., Clarendon Press, Oxford, England, 1979.
  • K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer-Verlag, Berlin, New York, 1998.
  • G. Janusz, Algebraic Number Fields, Second ed., Amer. Math. Soc., Providence, Rhode Island, 1998.
  • H.-J. Kanold, Über das harmonische Mittel der Teiler einer natürlichen Zahl, Math. Annalen 133 (1957), 371–374.
  • D. E. Knuth, The Art of Computer Programming, Volume 2, Seminumerical Algorithms, Second ed., Addison-Wesley, Reading, Massachusetts, 1981.
  • N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag, New York, 1987.
  • —, Elliptic curve cryptosystems, Math. Comp. 48 (1987), 203–209.
  • A. Korselt, Probléme chinois, L’Intermédiaire des Mathématiciens 6 (1899), 142–143.
  • D. E. Knuth and L. Trabb Pardo, Analysis of a simple factorization algorithm, Theoretical Computer Science 3 (1976), 321–348.
  • M. Kraitchik, Recherches sur la Théorie des Nombres, Gauthiers-Villars, Paris, France, 1929.
  • F. W. Lawrence, Factorisation of numbers, Messinger of Math. 24 (1895), 100–109.
  • D. N. Lehmer, Factor table for the first ten millions containing the smallest factor of every number not divisible by 2, 3, 5, or 7 between the limits 0 and 10017000, Carnegie Institute of Washington, 1909.
  • —, On the history of the problem of separating a number into its prime factors, Scientific Monthly (September 1918), 227–234.
  • D. H. Lehmer, Tests for primality by the converse of Fermat’s theorem, Bull. Amer. Math. Soc. 33 (1927), 327–340.
  • —, A photo-electric number sieve, Amer. Math. Monthly 40 (1933), 401–406.
  • D. N. Lehmer, Hunting big game in the theory of numbers, Scripta Math. 1 (March 1933), 229–235.
  • D. H. Lehmer, An announcement concerning the delay line sieve DLS 127, Math. Comp. 20 (1966), 645–646.
  • —, Computer technology applied to the theory of numbers, Studies in Number Theory, Math. Assn. Amer. (distributed by Prentice-Hall), 1969, pp. 117–151.
  • R. S. Lehman, Factoring large integers, Math. Comp. 28 (1974), 637–646.
  • H. W. Lenstra, Jr., Primality testing, Computational Methods in Number Theory, Part 1 (CWI, Amsterdam) (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centrum Tract, vol. 154, 1982, pp. 55–77.
  • —, Factoring integers with elliptic curves, Ann. of Math. 126 (1987), 649–673.
  • W. J. Levesque, Fundamentals of Number Theory, Dover, 1977.
  • R. J. Lipton, DNA solution of hard computational problems, Science 268 (1995), 542–545.
  • D. H. Lehmer and Emma Lehmer, A new factorization technique using quadratic forms, Math. Comp. 28 (1974), 625–635.
  • A. K. Lenstra and H. W. Lenstra, Jr. (eds.), The development of the number field sieve, Lecture Notes in Mathematics, vol. 1554, Springer-Verlag, New York, 1993.
  • A. K. Lenstra, H. W. Lenstra, Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Annalen 261 (1982), 515–534.
  • A. K. Lenstra and M. S. Manasse, Factoring by electronic mail, Advances in Cryptology—EUROCRYPT ’89 (Springer, Berlin), Lecture Notes in Computer Science, vol. 434, 1989, pp. 355–371.
  • W. Looff, Über die Periodicität der Decimalbrüche, Archiv der Mathematik und Physik. 16 (1851), 54–57.
  • D. H. Lehmer and R. E. Powers, On factoring large numbers, Bull. Amer. Math. Soc. 37 (1931), 770–776.
  • H. W. Lenstra, Jr. and C. Pomerance, A rigorous time bound for factoring integers, Jour. Amer. Math. Soc. 5 (1992), no. 3, 483–516.
  • A. K. Lenstra, E. Tomer, A. Shamir, W. Kortsmit, B. Dodson, J. Hughes, and P. C. Leyland, Factoring estimates for a 1024-bit RSA modulus, Lecture Notes in Computer Science, vol. 2894, pp. 55–74, Springer, Berlin, 2003.
  • É. Lucas, Sur les formules de Cauchy et de Lejeune Dirichlet, Assoc. Française pour l’Advanc. Sci., Comptes Rendus 7 (1878), 164–173.
  • G. B. Mathews, Theory of Numbers, Part I, Deighton, Bell & Co., Cambridge, England, 1892.
  • A. May, Computing the RSA secret key is deterministic polynomial time equivalent to factoring, Advances in Cryptology—Proc. CRYPTO 2004 (Springer-Verlag, Berlin, New York), Lecture Notes in Computer Science, vol. 3152, 2004, pp. 213–219.
  • B. Mazur, How can we construct abelian Galois extensions of basic number fields?, Bull. Amer. Math. Soc. (N.S.) 48 (2011), 155–209.
  • M. A. Morrison and J. Brillhart, A method of factoring and the factorization of $F_7$, Math. Comp. 29 (1975), 183–205.
  • J. McKee, Speeding Fermat’s factoring method, Math. Comp. 68 (1999), 1729–1737.
  • G. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), 300–317.
  • V. Miller, Use of elliptic curves in cryptography, Advances in Cryptology—Proc. CRYPTO ’85 (Springer-Verlag, Berlin, New York), Lecture Notes in Computer Science, vol. 218, 1987, pp. 417–426.
  • M. Morimoto and Y. Kida, Factorization of Cyclotomic Numbers, Sophia University, Tokyo, 1987.
  • M. Morimoto, Y. Kida, and M. Kobayashi, Factorization of Cyclotomic Numbers, III, Sophia University, Tokyo, 1992.
  • M. Morimoto, Y. Kida, and M. Saito, Factorization of Cyclotomic Numbers, II, Sophia University, Tokyo, 1989.
  • P. L. Montgomery and B. Murphy, Improved polynomial selection for the number field sieve, The Mathematics of Public Key Cryptography Conference (Toronto), Fields Institute, 1999.
  • L. Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), 97–108.
  • P. L. Montgomery, Modular multiplication without trial division, Math. Comp. 44 (1985), 519–521.
  • —, Speeding the Pollard and elliptic curve methods of factoring, Math. Comp. 48 (1987), 243–264.
  • —, Square roots of products of algebraic numbers, Mathematics of Computation 1943–1993 (W. Gautschi, ed.), Proc. Symp. Appl. Math., vol. 48, Amer. Math. Soc., 1994, pp. 567–571.
  • —, A block Lanczos algorithm for finding dependencies over $GF(2)$, Advances in Cryptology—EUROCRYPT ’95 (Springer-Verlag, Berlin) (A. J. Menezes and S. A. Vanstone, eds.), Lecture Notes in Computer Science, vol. 921, 1995, pp. 106–120.
  • F. Morain, La primalité en temps polynomial (d’après Adleman, Huang; Agrawal, Kayal, Saxena), Astérisque 294 (2004), 205–230.
  • A. J. Menezes, T. Okamoto, and S. A. Vanstone, Reducing elliptic curve logarithms to logarithms in a finite field, IEEE Trans. on Info. Theory IT-39(5) (1993), 1639–1646.
  • C. J. Moreno and S. S. Wagstaff, Jr., Sums of Squares of Integers, Chapman & Hall/CRC Press, Boca Raton, Florida, 2006.
  • T. Nagell, Introduction to Number Theory, John Wiley, New York, 1951.
  • P. P. Nielsen, Odd perfect numbers have at least nine distinct prime factors, Math. Comp. 76 (2007), 2109–2126.
  • I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, Fifth ed., John Wiley, New York, 1991.
  • P. Ochem and M. Rao, Odd perfect numbers are greater than $10^{1500}$, Math. Comp. 81 (2012), 1869–1877.
  • O. Ore, On the averages of the divisors of a number, Amer. Math. Monthly 55 (1948), 615–619.
  • S. Pohlig and M. Hellman, An improved algorithm for computing logarithms over $\textbf {GF}(p)$ and its cryptographic significance, IEEE Trans. on Info. Theory IT-24(1) (1978), 106–110.
  • H. C. Pocklington, The determination of the prime or composite nature of large numbers by Fermat’s theorem, Proc. Camb. Phil. Soc. 18 (1914–16), 29–30.
  • J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc. 76 (1974), 521–528.
  • —, A Monte Carlo method for factorization, Nordisk Tidskr. Informationsbehandling (BIT) 15 (1975), 331–335.
  • —, Factoring with cubic integers, Lecture Notes in Mathematics, vol. 1554, pp. 4–10, Springer-Verlag, New York, 1993.
  • C. Pomerance, On the distribution of pseudoprimes, Math. Comp. 37 (1981), 587–593.
  • —, Analysis and comparison of some integer factoring algorithms, Computational Methods in Number Theory, Part 1 (CWI, Amsterdam) (H. W. Lenstra, Jr. and R. Tijdeman, eds.), Math. Centrum Tract, vol. 154, 1982, pp. 89–139.
  • —, The number field sieve, Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993) (Amer. Math. Soc., Providence, RI), Proc. Sympos. Appl. Math., vol. 48, 1994, pp. 465–480.
  • —, A tale of two sieves, Notices Amer. Math. Soc. 43 (1996), 1473–1485.
  • —, Primality testing: variations on a theme of Lucas, Congressus Numerantium 201 (2010), 301–312.
  • V. R. Pratt, Every prime has a succinct certificate, SIAM J. Comput. 4 (1975), 214–220.
  • P. A. Pritchard, A sublinear additive sieve for finding prime numbers, Comm. ACM 24 (1981), 18–23.
  • C. Pomerance, J.W. Smith, and R. Tuler, A pipeline architecture for factoring large integers with the quadratic sieve algorithm, SIAM J. Comput. 17 (1988), no. 2, 387–403.
  • C. Pomerance, J. L. Selfridge, and S. S. Wagstaff, Jr., The pseudoprimes to $25\cdot 10^9$, Math. Comp. 35 (1980), 1003–1026.
  • M. Rabin, Digitized signatures and public-key functions as intractable as factoring, Tech. Report LCS/TR-212, M.I.T. Lab for Computer Science, 1979.
  • —, Probabilistic algorithms for testing primality, J. Number Theory 12 (1980), 128–138.
  • V. Ramaswami, The number of positive integers $<x$ and free of prime divisors $>x^c$, and a problem of S. S. Pillai, Duke Math. J. 16 (1949), 99–109.
  • K. G. Reuschle, Mathematische Abhandlung, enthaltend: Neue zahlentheoretische Tabellen, Königl. Gymnasium Stuttgart, 1856.
  • H. Riesel, Prime Numbers and Computer Methods of Factorization, Second ed., Birkhäuser, Boston, Massachusetts, 1994.
  • K. H. Rosen, Elementary Number Theory and Its Applications, Second ed., Addison-Wesley, Reading, Massachusetts, 1988.
  • R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. A. C. M. 21(2) (1978), 120–126.
  • A. Schinzel, On primitive prime factors of $a^n-b^n$, Proc. Cambridge Philos. Soc. 58 (1962), 555–562.
  • R. Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), 483–494.
  • D. Shanks, Class number, a theory of factorization, and genera, 1969 Number Theory Institute, Stony Brook, N.Y., Proc. Sympos. Pure Math., vol. 20, Amer. Math. Soc., 1971, pp. 415–440.
  • —, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) (Winnipeg, Man.), Congressus Numerantium, no. VII, Utilitas Math., 1973, pp. 51–70.
  • —, Analysis and improvement of the continued fraction method of factorization. Abstract 720-10-43, Notices Amer. Math. Soc. 22 (1975), A–68.
  • A. Shamir, Factoring numbers in O$(\log n)$ arithmetic steps, Inform. Proc. Lett. 8 (1979), 28–31.
  • —, Factoring large numbers with the TWINKLE device (extended abstract), Cryptographic Hardware and Embedded Systems, First International Workshop, CHES ’99, Worcester, MA (Springer-Verlag, New York) (Ç. Koç and C. Paar, eds.), Lecture Notes in Computer Science, vol. 1717, 1999, pp. 2–12.
  • P. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings of the Thirty-Fifth Annual Symposium on the Foundations of Computer Science, 1994, pp. 124–134.
  • —, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review 41 (1999), 303–332.
  • C. L. Siegel, Zu zwei Bemerkungen Kummers, Nachr. Akad. Wiss. Göttingen Math-Phys. Kl II 1964 (1964), 51–57.
  • R. D. Silverman, The multiple polynomial quadratic sieve, Math. Comp. 48 (1987), 329–339.
  • J. H. Silverman and J. Tate, Rational Points on Elliptic Curves, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1992.
  • A. Shamir and E. Tromer, Factoring large numbers with the TWIRL device, Advances in Cryptology—Proc. CRYPTO 2003 (Springer-Verlag, Berlin, New York), Lecture Notes in Computer Science, vol. 2729, 2003, pp. 1–26.
  • V. Strassen, Einige Resultate über Berechnungskomplexität, Jahresber. Deutsch. Math.-Verein. 78 (1976/77), 1–8.
  • H. Suyama, Searching for prime factors of Fermat numbers with a microcomputer, BIT (Tokyo) 13 (1981), 240–245.
  • J. W. Smith and S. S. Wagstaff, Jr., An extended precision operand computer, Proc. of the Twenty-First Southeast Region ACM Conference (ACM), 1983, pp. 209–216.
  • R. D. Silverman and S. S. Wagstaff, Jr., A practical analysis of the elliptic curve factoring algorithm, Math. Comp. 61 (1993), 445–462.
  • J. Shallit, H. C. Williams, and F. Morain, Discovery of a lost factoring machine, Math. Intelligencer 17 (1995), 41–47.
  • J. Touchard, Propriétés arithmétiques de certain nombres recurrents, Ann. Soc. Sci. Bruxelles 53A (1933), 21–31.
  • W. Trappe and L. C. Washington, Introduction to Cryptography with Coding Theory, Prentice Hall, Upper Saddle River, New Jersey, 2002.
  • B. L. van der Waerden, Algebra, vol. 1, Frederick Ungar, New York, 1970.
  • L. M. K. Vandersypen, M. Steffen, G. Breyta, C. S. Yannoni, M. H. Sherwood, and I. L. Chuang, Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance, Nature 414 (6866) (2001), 883–887.
  • S. S. Wagstaff, Jr., Divisors of Mersenne numbers, Math. Comp. 40 (1983), 385–397.
  • —, Computing Euclid’s primes, Bull. of the Inst. for Combinatorics and Its Applications 8 (1993), 23–32.
  • —, Aurifeuillian factorizations and the period of the Bell numbers modulo a prime, Math. Comp. 65 (1996), 383–391.
  • —, Cryptanalysis of Number Theoretic Ciphers, Chapman & Hall/CRC Press, Boca Raton, Florida, 2003.
  • —, The search for Aurifeuillian-like factorizations, Integers 12A (2012), 1449–1461.
  • L. C. Washington, Introduction to Cyclotomic Fields, Second ed., Springer-Verlag, New York, 1996.
  • —, Elliptic Curves: Number Theory and Cryptography, Chapman & Hall/CRC Press, Boca Raton, Florida, 2003.
  • H. C. Williams and H. Dubner, The primality of $R1031$, Math. Comp. 47 (1986), 703–711.
  • S. H. Weintraub, Several proofs of the irreducibility of the cyclotomic polynomials, Amer. Math. Monthly 120 (2013), 537–545.
  • M. J. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Trans. on Info. Theory 36 (1990), 553–558.
  • G. T. Williams, Numbers generated by the function $e^{e^x-1}$, Amer. Math. Monthly 52 (1945), 323–327.
  • H. C. Williams, Some primes with interesting digit patterns, Math. Comp. 32 (1978), 1306–1310.
  • —, A modification of the RSA public-key encryption procedure, IEEE Trans. on Info. Theory IT-26(6) (1980), 726–729.
  • —, A $p+1$ method of factoring, Math. Comp. 39 (1982), 225–234.
  • —, Édouard Lucas and Primality Testing, Canadian Mathematics Society Series of Monographs and Advanced Texts, vol. 22, John Wiley & Sons, New York, 1998.
  • H. C. Williams and C. D. Patterson, A report on the University of Manitoba sieve unit, Congressus Numerantium 37 (1983), 85–98.
  • S. S. Wagstaff, Jr. and J. W. Smith, Methods of factoring large integers, Number Theory, New York, 1984–1985 (Springer-Verlag, New York) (D. V. Chudnovsky, G. V. Chudnovsky, H. Cohn, and M. B. Nathanson, eds.), Lecture Notes in Mathematics, vol. 1240, 1987, pp. 281–303.
  • M. C. Wunderlich, A performance analysis of a simple prime-testing algorithm, Math. Comp. 40 (1983), 709–714.
  • N. Xu, J. Zhu, D. Lu, X. Zhou, X. Peng, and J. Du, Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system, Phys. Rev. Lett. 108 (2012), 130501.
  • P. Zimmermann and B. Dodson, 20 years of ECM, Algorithmic Number Theory, Proceedings ANTS 2006 (Berlin), Lecture Notes in Computer Science, vol. 4076, Springer, 2006, pp. 525–542.
  • K. Zsigmondy, Zur Theorie der Potenzreste, Monatsh. Math. 3 (1892), 265–284.