i=1

is called absolutely convergent if the series ∞ |xi | is convergent.

i=1

It is a basic fact from calculus that if an in¬nite series ∞ xi isi=1

absolutely convergent, then not only does the series itself converge to

some value y, but any in¬nite series whose terms are a rearrangement

of the xi also converges to the same value y.

A5. Double in¬nite series. The topic of double in¬nite series may not

be discussed in a typical introductory calculus course; we summa-

rize here the basic facts that we need. We state these facts without

proof, but all of them are fairly straightforward applications of the

de¬nitions.

Suppose that xij , i, j = 1, 2, . . . are non-negative real numbers. The

Appendix: Some useful facts 503

ith row gives a series j xij , and if each of these converges, one can

form the double in¬nite series i j xij . Similarly, one may form

the double in¬nite series j i xij One may also arrange the terms

xij in a single in¬nite series ij xij , using some enumeration of the

set of pairs (i, j). Then these three series either all diverge or all

converge to the same value.

If we drop the requirement that the xij are non-negative, but instead

require that the single in¬nite series ij xij is absolutely convergent,

then these three series all converge to the same value.

As a special application of the above discussion, if the series i ai

is absolutely convergent and converges to A, and if the series j bj

is absolutely convergent and converges to B, then if we arrange the

terms ai bj in any way in a single in¬nite series ij ai bj , this latter

series is absolutely convergent and converges to AB.

Bibliography

[1] L. M. Adleman. A subexponential algorithm for the discrete logarithm prob-

lem with applications to cryptography. In 20th Annual Symposium on Foun-

dations of Computer Science, pages 55“60, 1979.

[2] L. M. Adleman. The function ¬eld sieve. In Proc. 1st International Sympo-

sium on Algorithmic Number Theory (ANTS-I), pages 108“121, 1994.

[3] L. M. Adleman and M.-D. Huang. Primality Testing and Two Dimen-

sional Abelian Varieties over Finite Fields (Lecture Notes in Mathematics

No. 1512). Springer-Verlag, 1992.

[4] L. M. Adleman and H. W. Lenstra, Jr. Finding irreducible polynomials over

¬nite ¬elds. In 18th Annual ACM Symposium on Theory of Computing, pages

350“355, 1986.

[5] L. M. Adleman, C. Pomerance, and R. S. Rumely. On distinguishing prime

numbers from composite numbers. Annals of Mathematics, 117:173“206,

1983.

[6] M. Agrawal, N. Kayal, and N. Saxena. PRIMES is in P. Manuscript, www.

cse.iitk.ac.in/news/primality.html, 2002.

[7] W. Alford, A. Granville, and C. Pomerance. There are in¬ntely many

Carmichael numbers. Annals of Mathematics, 140:703“722, 1994.

[8] T. M. Apostol. Introduction to Analytic Number Theory. Springer-Verlag,

1973.

[9] E. Bach. How to generate factored random numbers. SIAM Journal on

Computing, 17:179“193, 1988.

[10] E. Bach. Explicit bounds for primality testing and related problems. Mathe-

matics of Computation, 55:355“380, 1990.

[11] E. Bach. E¬cient prediction of Marsaglia-Zaman random number generators.

IEEE Transactions on Information Theory, IT-44:1253“1257, 1998.

[12] E. Bach and J. Shallit. Algorithmic Number Theory, volume 1. MIT Press,

1996.

[13] M. Bellare and P. Rogaway. Random oracles are practical: a paradigm for

designing e¬cient protocols. In First ACM Conference on Computer and

Communications Security, pages 62“73, 1993.

[14] M. Ben-Or. Probabilistic algorithms in ¬nite ¬elds. In 22nd Annual Sympo-

sium on Foundations of Computer Science, pages 394“398, 1981.

504

Bibliography 505

[15] E. R. Berlekamp. Algebraic Coding Theory. McGraw-Hill, 1968.

[16] E. R. Berlekamp. Factoring polynomials over large ¬nite ¬elds. Mathematics

of Computation, 24(111):713“735, 1970.

[17] L. Blum, M. Blum, and M. Shub. A simple unpredictable pseudo-random

number generator. SIAM Journal on Computing, 15:364“383, 1986.

[18] D. Boneh. The Decision Di¬e-Hellman Problem. In Proc. 3rd International

Symposium on Algorithmic Number Theory (ANTS-III), pages 48“63, 1998.

Springer LNCS 1423.

[19] D. Boneh and G. Durfee. Cryptanalysis of RSA with private key d less than

N 0.292 . IEEE Transactions on Information Theory, IT-46:1339“1349, 2000.

[20] R. P. Brent and H. T. Kung. Fast algorithms for manipulating formal power

series. Journal of the ACM, 25:581“595, 1978.

[21] J. P. Buhler, H. W. Lenstra, Jr., and C. Pomerance. Factoring integers with

the number ¬eld sieve. In A. K. Lenstra and H. W. Lenstra, Jr., editors, The

Development of the Number Field Sieve, pages 50“94. Springer-Verlag, 1993.

[22] D. A. Burgess. The distribution of quadratic residues and non-residues. Math-

ematika, 4:106“112, 1957.

[23] E. Can¬eld, P. Erd˝s, and C. Pomerance. On a problem of Oppenheim

o

concerning ˜Factorisatio Numerorum™. Journal of Number Theory, 17:1“28,

1983.

[24] D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over

arbitrary rings. Acta Informatica, 28:693“701, 1991.

[25] J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal

of Computer and System Sciences, 18:143“154, 1979.

[26] A. L. Chistov. Polynomial time construction of a ¬nite ¬eld. In Abstracts

of Lectures at 7th All-Union Conference in Mathematical Logic, Novosibirsk,

page 196, 1984. In Russian.

[27] D. Coppersmith. Modi¬cations to the number ¬eld sieve. Journal of Cryp-

tology, 6:169“180, 1993.

[28] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic pro-

gressions. Journal of Symbolic Computation, 9(3):23“52, 1990.

[29] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to

Algorithms. MIT Press, second edition, 2001.

[30] R. Crandall and C. Pomerance. Prime Numbers: A Computational Perspec-

tive. Springer, 2001.

[31] I. Damg˚ and G. Frandsen. E¬cient algorithms for gcd and cubic residu-

ard

osity in the ring of Eisenstein integers. In 14th International Symposium on

Fundamentals of Computation Theory, Springer LNCS 2751, pages 109“117,

2003.

[32] I. Damg˚ P. Landrock, and C. Pomerance. Average case error estimates

ard,

for the strong probable prime test. Mathematics of Computation, 61:177“194,

1993.

[33] W. Di¬e and M. E. Hellman. New directions in cryptography. IEEE Trans-

actions on Information Theory, IT-22:644“654, 1976.

[34] J. Dixon. Asymptotocally fast factorization of integers. Mathematics of Com-

putation, 36:255“260, 1981.

506 Bibliography

[35] J. L. Dornstetter. On the equivalence between Berlekamp™s and Euclid™s

algorithms. IEEE Transactions on Information Theory, IT-33:428“431, 1987.

[36] E. Fouvry. Th´or`me de Brun-Titchmarsh; application au th´or`me de Fer-

ee ee

mat. Inventiones Mathematicae, 79:383“407, 1985.

[37] J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge

University Press, 1999.

[38] J. von zur Gathen and V. Shoup. Computing Frobenius maps and factoring

polynomials. Computational Complexity, 2:187“224, 1992.

[39] S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer

and System Sciences, 28:270“299, 1984.

[40] D. M. Gordon. Discrete logarithms in GF(p) using the number ¬eld sieve.

SIAM Journal on Discrete Mathematics, 6:124“138, 1993.

[41] J. Gordon. Very simple method to ¬nd the minimal polynomial of an arbitrary

non-zero element of a ¬nite ¬eld. Electronic Letters, 12:663“664, 1976.

[42] H. Halberstam and H. Richert. Sieve Methods. Academic Press, 1974.

[43] G. H. Hardy and J. E. Littlewood. Some problems of partito numerorum.

III. On the expression of a number as a sum of primes. Acta Mathematica,

44:1“70, 1923.

[44] G. H. Hardy and E. M. Wright. An Introduction to the Theory of Numbers.

Oxford University Press, ¬fth edition, 1984.

[45] D. Heath-Brown. Zero-free regions for Dirichlet L-functions and the least

prime in an arithmetic progression. Proceedings of the London Mathematical

Society, 64:265“338, 1992.

[46] R. Impagliazzo, L. Levin, and M. Luby. Pseudo-random number generation

from any one-way function. In 21st Annual ACM Symposium on Theory of

Computing, pages 12“24, 1989.