Number Theory Page
Mathematics
European Math. Information Service
Number Theory
The Prime Pages(Chris Caldwell)
List of my papers:
Not all free online, but papers 1, 9, 12, 17 and 21 (and all issues of Math. Comp. 1943-2016) are now freely available from the AMS website here: www.ams.org/mcom/ . Printed copies on request, by post.
My papers are mainly on computational number theory, especially factoring and discrete logarithms:
Factoring: 4,6,12,14-18
Discrete logarithms(*): 9,20,21.
Most cited papers: 1,4,6,9,12-17.
The above pictures illustrate some algorithms for factoring or discrete logarithms of which I am the inventor or joint inventor (see comments below).
1. The fast Fourier transform in a finite field, Math. Comp. 25(1971), 365-374.
2. An algorithm for testing the primality of any integer, Bull. London Math. Soc. 3(1971), 337-340.
{obsolete paper}
3. A generalisation of the theorem of Cauchy and Davenport, J. London Math. Soc. (2), 8(1974), 460-462.
{a theorem discovered by computer calculations}
4. Theorems on factorisation and primality testing, Proc. Camb. Phil. Soc. 76(1974), 521-528.
4. Theorems on factorisation and primality testing, Proc. Camb. Phil. Soc. 76(1974), 521-528.
{includes the two-stage p-1 method of factoring}
5. Addition properties of residue classes, J. London Math. Soc.(2), 11(1975), 147-152.
{an extension of [3]}
6. A Monte Carlo method for factorization, BIT 15(1975), 331-334.
{proposed the rho method for factoring}
7. Combinatorial properties of a queueing system with limited availability, Advances in Applied Prob. 7(1975), 864-877.
8. Implementation of number theoretic transforms, Elect. Lett., 22nd July 1976, 378-379.
{connected with [1]}
9. Monte Carlo methods for index computation (mod p), Math. Comp. 32(1978), 918-924.
{proposed the rho and kangaroo methods for discrete logarithms(*)}
10. Remarks on the convolution algorithm of Agarwal and Cooley, Elect. Lett., 13th Sept. 1979, 593-594.
{connected with [1,8]}
11. On not storing the path of a random walk, BIT 19(1979), 545-548.
{an algorithm looking for a problem?}
12. (With R.P.Brent), Factorisation of the eighth Fermat number, Math. Comp. 36(1981), 627-630.
{an application of the rho method[6]}
13. (With C.P.Schnorr), An efficient solution of the congruence x^2 + ky^2 = m (mod n), IEEE Trans. Inf. Theory, IT-33, No. 5, Sept. 1987, 702-709.
{broke several versions of the Ong-Schnorr-Shamir signature scheme}
14. Factoring with cubic integers, in “The development of the number field sieve", A.K.Lenstra and H.W.Lenstra(eds), Lecture Notes in Mathematics 1554, Springer-Verlag 1993, 4-10.
{First implementation of the number field sieve}
15. The lattice sieve, in ditto, 43-49.
16. (With A.K.Lenstra, H.W.Lenstra and M.S.Manasse), The number field sieve, in ditto, 11-40.
17. (With the same coauthors), The factorisation of the ninth Fermat number, Math. Comp. 61(1993), 319-349.
{an application of the special number field sieve}
18. Unforgettable Fermat factors, Math. Gazette 82(1998), 77-79.
{not a research paper - mnemonics for some Fermat factors!}
19. Kruskal`s card trick, Math. Gazette 84(2000), 265-267.
{connected with [20]}
20. Kangaroos, Monopoly and discrete logarithms, J. Crypt. 13(2000), 437-447.
{improvements to the kangaroo method and its analysis(*)}
21. (With S.D.Galbraith and R. S. Ruprai), Computing discrete logarithms in an interval., Math. Comp. 82(2013), 1181-1195.
{includes more improvements to the kangaroo methods(*)}
(*) Note. The terminology of discrete log methods got into confusion. I am trying to persuade people to use the names:
Rho method (serial and parallel) - for computing discrete logs in the whole group, and
Kangaroo method (serial and parallel) - for computing a discrete log known to lie in an interval.
Here the serial methods are essentially those of [9]. Parallel versions of both were introduced in:
P.C. van Orschot and M.J. Wiener, Parallel collision search with cryptanalytic applications, J. Crypt., 12 (1999), 1-28.
Their idea, the use of "distinguished points", also improves the serial versions of both - see their paper and [20,21]. Further improvements were made by Edlyn Teske (see her website).
The distinction between the two methods is both in the kind of random walk and in the way in which it is used.
1. A "kangaroo" moves in a series of small positive jumps in the discrete log. Note that the jumps are explicit chosen by us. We need two kangaroos (or two herds in the parallel version), just as we need two tables in the BSGS method.
2. The other kind of animal, a non-kangaroo or "snark" (invented by Lewis Carroll in his famous poem "The Hunting of the Snark") can make large jumps, and can even double its discrete log. The sizes of the jumps are not all known to us, since some, at least, depend on the unknown value of the discrete log.
The name "lambda method" became confusing - since some used it for the parallel version of the rho method, and others for either form of kangaroo method. Please use it only for the latter - but preferably not at all.
Some authors even applied the name "kangaroo" to any random walk in a cyclic group. This is zoologically absurd (a kangaroo cannot jump in one bound to another continent) - and mathematically confusing.
Note. A kangaroo with only two jumps has a best possible exponent of 2/3 not 1/2 (see paper 20). Thus the "kangaroo problem" is different from the birthday problem. Further, kangaroos have no concept of birthdays and could not do the birthday problem.
On the other hand, a snark with only two actions, one of them doubling, does apparently have exponent 1/2, although the "rho length" increases from the 1.25*sqrt(p) of a true random mapping to about 1.9*sqrt(p) - see E. Teske and P. Ebinger (ANTS 5).
(last modified 10th January 2022)