@article{Frame:1978,
	key = "Frame 1978",
	author = "J. S. Frame",
	title = "A short proof of quadratic reciprocity",
	journal = AMM,
	volume = 85,
	year = 1978,
	pages = "818-819"}

@article{Shallit:1990,
	key = "Shallit 1990",
	author = "J. O. Shallit",
	title = "On the worst case of three algorithms for computing the
{Jacobi} symbol",
	journal = JSC,
	year = 1990,
	volume = 10,
	pages = "593-610"}

@book{Hua:1982,
	key = "Hua 1982",
	author = "L. K. Hua",
	title = "Introduction to Number Theory",
	publisher = SV,
	address = NY,
	year = 1982}

@article{Estes&Pall:1973,
	key = "Estes and Pall 1973",
	author = "D. R. Estes and G. Pall",
	title = "A reconsideration of {Legendre-Jacobi} symbols",
	journal = JNT,
	volume = 5,
	year = 1973,
	pages = "433-434"}

@article{Cartier:1970,
	key = "Cartier 1970",
	author = "P. Cartier",
	title = "Sur une {g\'en\'eralisation} des symboles de
{Legendre-Jacobi}",
	journal = EM,
	volume = 16,
	year = 1970,
	pages = "31-48"}

@article{Graham&Yao&Yao:1978,
	key = "R. Graham, Yao, and Yao 1978",
	author = "R. L. Graham and A. C.-C. Yao and F.-F. Yao",
	title = "Addition chains with multiplicative cost",
	journal = DM,
	volume = 23,
	year = 1978,
	pages = "115-119"}

@article{Kannan&Lipton:1986,
	key = "Kannan and Lipton 1986",
	author = "R. Kannan and R. J. Lipton",
	title = "Polynomial-time algorithm for the orbit problem",
	journal = JACM,
	volume = 33,
	year = 1986,
	pages = "808-821"}

@article{Collins&Reddy&Sloane:1978,
	key = "S. Collins, Reddy, and Sloane 1978",
	author = "S. Collins and S. M. Reddy and N. J. A. Sloane",
	title = "Elementary Problem 2704",
	journal = AMM,
	volume = 85,
	year = 1978,
	pages = "198"}

@article{Ecker:1979,
	key = "Ecker 1979",
	author = "M. W. Ecker",
	title = "Elementary Problem 2773",
	journal = AMM,
	volume = 86,
	year = 1979,
	pages = "393"}

@article{Euler:1761,
	key = "Euler 1761",
	author = "L. Euler",
	title = "Theoremata circa residua ex divisione potestatum relicta",
	journal = NCASP,
	volume = "7 {\rm (1758/9)}",
	year = "1761",
	pages = "49-82",
	note = "Reprinted in {\it Opera Omnia}, Ser.~1, Vol.~2, 
		pp.~493--518"}

@article{Blakley&Borosh:1983,
	key = "Blakley and Borosh 1983",
	author = "G. R. Blakley and I. Borosh",
	title = "Modular arithmetic of iterated powers",
	journal = CMA,
	volume = 9,
	year = 1983,
	pages = "567-581"}

@article{Dawson:1994,
	key = "Dawson 1994",
	author = "R. J. M. Dawson",
	title = "Towers of powers modulo $m$",
	journal = CMJ,
	volume = 25,
	year = 1994,
	pages = "22-28"}

@article{Radke:1970,
	key = "Radke 1970",
	author = "C. E. Radke",
	title = "The use of quadratic residue research",
	journal = CACM,
	volume = 13,
	year = 1970,
	pages = "103-105"}

@article{Maurer:1968,
	key = "W. Maurer 1968",
	author = "W. D. Maurer",
	title = "An improved hash code for scatter storage",
	journal = CACM,
	volume = 11,
	year = 1968,
	pages = "35-38"}

@inproceedings{Egecioglu&Koc:1990,
	key = "{{E\~{g}ecio\~{g}lu} and Ko{\c c} 1990}",
	author = "O. {\noopsort{Egecioglu}}{E\~{g}ecio\~{g}lu}
and C. K. Ko{\c c}", 
	title = "Fast modular exponentiation",
	booktitle = "Proc. 1990 Bilkent Int'l. Conf. New 
		     Trends in Communication, 
		     Control, and Signal Processing",
	publisher = "Elsevier",
	year = 1990,
	volume = 1,
	pages = "188-194"}

@article{Yao:1976,
	key = "Yao 1976",
	author = "A. C. Yao",
	title = "On the evaluation of powers",
	journal = SIAMJC,
	volume = 5,
	year = 1976,
	pages = "100-103"}

@article{Brauer:1939,
	key = "Brauer 1939",
	author = "A. Brauer",
	title = "On addition chains",
	journal = BAMS,
	volume = 45,
	year = 1939,
	pages = "736-739"}

@article{Downey&Leong&Sethi:1981,
	key = "Downey, Leong, and Sethi 1981",
	author = "P. Downey and B. Leong and R. Sethi",
	title = "Computing sequences with addition chains",
	journal = SIAMJC,
	volume = 10,
	year = 1981,
	pages = "638-646"}

@article{Erdos:1960,
	key = "{Erd{\H{o}}s} 1960",
	author = "P. {Erd{\H{o}}s}",
	title = "Remarks on number theory {III}:  on addition chains",
	journal = AA,
	volume = 6,
	year = 1960,
	pages = "77-81"}

@article{Dobkin&Lipton:1980,
	key = "Dobkin and Lipton 1980",
	author = "D. Dobkin and R. J. Lipton",
	title = "Addition chain methods for the evaluation of specific polynomials",
	journal = SIAMJC,
	volume = 9,
	year = 1980,
	pages = "121-125"}

@article{Lipton&Dobkin:1976,
	key = "Lipton and Dobkin 1976",
	author = "R. J. Lipton and D. Dobkin",
	title = "Complexity measures and hierarchies for the evaluation
of integers and polynomials",
	journal = TCS,
	volume = 3,
	year = 1976,
	pages = "349-357"}

@inproceedings{Pippenger:1976,
	key = "Pippenger 1976",
	author = "N. Pippenger",
	title = "On the evaluation of powers and related problems",
	booktitle = FOCS76,
	year = 1976,
	pages = "258-263"}

@article{Semba:1983,
	key = "Semba 1983",
	author = "I. Semba",
	title = "Systematic method for determining the number of
multiplications required to compute $x^m$, where $m$ is a positive
integer",
	journal = JIP,
	volume = 6,
	year = 1983,
	pages = "31-33"}

@article{Scholz:1937,
	key = "Scholz 1937",
	author = "A. Scholz",
	title = "Aufgabe 253",
	journal = JDMV,
	volume = 47,
	year = 1937,
	pages = "Supplement, pp. 41-42"}

@article{Allouche&Shallit:1992,
	key = "Allouche and Shallit 1992",
	author = "J.-P. Allouche and J. O. Shallit",
	title = "The ring of $k$--regular sequences",
	journal = TCS,
	volume = 98,
	year = 1992,
	pages = "163-187"}

@article{Gioia&Subbarao&Sugunama:1962,
	key = "Gioia, Subbarao, and Sugunama 1962",
	author = "A. A. Gioia and M. V. Subbarao and M. Sugunama",
	title = "The {Scholz-Brauer} problem in addition chains",
	journal = DMJ,
	volume = 29,
	year = 1962,
	pages = "481-487"}

@article{Thurber:1976,
	key = "Thurber 1976",
	author = "E. G. Thurber",
	title = "Addition chains and solutions of
$\ell(2n) = \ell(n)$ and $\ell(2^n-1) = n + \ell(n) - 1$",
	journal = DM,
	volume = 16,
	year = 1976,
	pages = "279-289"}

@article{Thurber:1973a,
	key = "Thurber 1973a",
	author = "E. G. Thurber",
	title = "The {Scholz-Brauer} problem on addition chains",
	journal = PJM,
	volume = 49,
	year = "{\noopsort{1973a}}1973",
	pages = "229-242"}

@article{Thurber:1973b,
	key = "Thurber 1973b",
	author = "E. G. Thurber",
	title = "On addition chains $\ell(mn) \leq \ell(n) - b$ and lower
bounds for $c(r)$",
	journal = DMJ,
	volume = 40,
	year = "{\noopsort{1973b}}1973",
	pages = "907-913"}

@article{Cottrell:1973,
	key = "Cottrell 1973",
	author = "A. Cottrell",
	title = "A lower bound for the {Scholz-Brauer} problem",
	journal = NAMS,
	volume = 20,
	year = 1973,
	pages = "A-476",
	note = "Abstract 73T-A200"}

@article{Straus:1964,
	key = "Straus 1964",
	author = "E. G. Straus",
	title = "Solution to Problem 5125",
	journal = AMM,
	volume = 71,
	year = 1964,
	pages = "807-808"}

@article{Vegh:1975,
	key = "Vegh 1975",
	author = "E. Vegh",
	title = "A note on addition chains",
	journal = JCTA,
	volume = 19,
	year = 1975,
	pages = "117-118"}

@article{Tsai&Chin:1987,
	key = "Tsai and Chin 1987",
	author = "Y. H. Tsai and Y. H. Chin",
	title = "A study of some addition chain problems",
	journal = IJCM,
	volume = 22,
	year = 1987,
	pages = "117-134"}

@article{Olivos:1981,
	key = "Olivos 1981",
	author = "J. Olivos",
	title = "On vectorial addition chains",
	journal = JA,
	volume = 2,
	year = 1981,
	pages = "13-21"}

@article{Leeuwen:1977,
	key = "van Leeuwen 1977",
	author = "Leeuwen, J. van",
	title = "An extension of {Hansen's} theorem for star chains",
	journal = JFRAM,
	volume = 295,
	year = 1977,
	pages = "202-207"}

@inproceedings{Gioia&Subbarao:1978,
	key = "Gioia and Subbarao 1978",
	author = "A. A. Gioia and M. V. Subbarao",
	title = "The {Scholz-Brauer} problem in addition chains {II}",
	booktitle = "Proc. Eight Manitoba Conference on Numerical Math. and Computing",
	editor = "D. McCarthy and H. C. Williams",
	year = 1978,
	pages = "251-274",
	note = "(= {\it Congr. Numer.} {\bf XXII})"}

@incollection{Bos&Coster:1990,
	key = "Bos and Coster 1990",
	author = "J. Bos and M. Coster",
	title = "Addition chain heuristics",
	booktitle = CRYPTO89,
	editor = "G. Brassard",
	publisher = SV,
	year = 1990,
	series = LNICS,
	volume = 435,
	pages = "400-407"}



@techreport{Tompa:1991,
	key = "Tompa 1991",
	author = "M. Tompa",
	title = "Lecture notes on probabilistic algorithms and pseudorandom
generators",
	number = "91-07-05",
	institution = "Department of Computer Science and Engineering, University
of Washington",
	year = 1991,
	month = "July"}

@article{Karp&Rabin:1987,
	key = "Karp and Rabin 1987",
	author = "R. M. Karp and M. O. Rabin",
	title = "Efficient randomized pattern-matching algorithms",
	journal = IBMJ,
	volume = 31,
	year = 1987,
	pages = "249-260"}

@article{Zolotarev:1872,
	key = "Zolotarev 1872",
	author = "G. Zolotarev",
	title = "Nouvelle {d\'emonstration} de la loi de {r\'eciprocit\'e} de
{Legendre}",
	journal = NAM,
	volume = 11,
	year = 1872,
	pages = "354-362"}

@book{Pieper:1978,
	key = "Pieper 1978",
	author = "H. Pieper",
	title = "Variationen {\"uber} ein zahlentheoretisches {Thema} von {Carl}
{Friedrich} {Gauss}",
	publisher = "{Birkh\"auser}",
	address = "Basel",
	year = 1978}

@techreport{Brlek&Mallette:1992,
	key = "Brlek and Mallette 1992",
	author = "S. Brlek and R. Mallette",
	title = "Sur le calcul des chaines d'additions optimales",
	institution = "{D\'epartement} de {math\'ematiques} et d'informatique,
{Universit\'e} du {Qu\'ebec} {\`a} {Montr\'eal}",
	number = 173,
	month = "February",
	year = 1992,
	note = "Abbreviated version in J. Labelle and J.-G. Penaud,
eds., {\it Atelier de Combinatoire Franco-Qu\'ebecois, 6-7 mai 1991},
Publications du LaCIM {\bf 10} (1992), 71--85"}

@article{Prodinger&Tichy:1983,
	key = "Prodinger and Tichy 1983",
	author = "H. Prodinger and R. F. Tichy",
	title = "{\"Uber} ein zahlentheoretisches {Problem} aus der {Informatik}",
	journal = OAW,
	volume = 192,
	year = 1983,
	pages = "385-396"}

@incollection{Brickell&Gordon&McCurley&Wilson:1993,
	key = "Brickell, Gordon, McCurley, and Wilson 1993",
	author = "E. F. Brickell and D. M. Gordon and K. S. McCurley and D. B. Wilson",
	title = "Fast exponentiation with precomputation",
	booktitle = EUROCRYPT92,
	editor = "R. A. Rueppel",
	series = LNICS,
	volume = 658,
	year = 1993,
	publisher = SV,
	pages = "200-207"}

@incollection{Iwamura&Matsumoto&Imai:1993a,
	key = "Iwamura, Matsumoto, and Imai 1993a",
	author = "K. Iwamura and T. Matsumoto and H. Imai",
	title = "Systolic-arrays for modular exponentiation using {Montgomery} method",
	booktitle = EUROCRYPT92,
	editor = "R. A. Rueppel",
	series = LNICS,
	volume = 658,
	year = "{\noopsort{1993a}}1993",
	publisher = SV,
	pages = "477-481"}

@inproceedings{Kawamura&Hirano:1988,
	key = "Kawamura and Hirano 1988",
	author = "S.-I. Kawamura and K. Hirano",
	title = "A fast modular arithmetic algorithm using a
residue table",
	booktitle = EUROCRYPT88,
	volume = 330,
	series = LNICS,
	publisher = SV,
	editor = "C. G. {G\"unther}",
	year = 1988,
	pages = "245-250"}

@phdthesis{CooperA:1926,
	key = "A. Cooper 1926",
	author = "A. E. Cooper",
	title = "A Topical History of the Theory of Quadratic Residues",
	month = "June",
	year = 1926,
	school = "University of Chicago"}

@article{Aiello&Subbarao:1993,
	key = "Aiello and Subbarao 1993",
	author = "W. Aiello and M. V. Subbarao",
	title = "A conjecture in addition chains related to {Scholz}'s conjecture",
	journal = MC,
	volume = 61,
	year = 1993,
	pages = "17-23; S1-S6"}

@article{LenstraHW:1993,
	key = "H. W. Lenstra 1993",
	author = "Lenstra, Jr., H. W.",
	title = "Generating units modulo an odd integer by addition and
subtraction",
	journal = AA,
	volume = 64,
	year = 1993,
	pages = "383-388"}

@article{Lagrange:1771,
	key = "Lagrange 1771",
	author = "J. L. Lagrange",
	title = "{D\'emonstration} d'un {th\'eor\`eme} nouveau concernant
les nombres premiers",
	journal = "Nouveaux {M\'emoires} de l'{Acad\'emie} Royale des
Sciences et Belles-Lettres de Berlin",
	year = 1771,
	pages = "125-137",
	note = "Reprinted in {\it Oeuvres}, Vol.~3, 1869, pp.~425-438"}

@article{Egecioglu&Koc:1994,
	key = "{{E\~{g}ecio\~{g}lu} and Ko{\c c} 1990}",
	author = "O. {\noopsort{Egecioglu}}{E\~{g}ecio\~{g}lu}
and C. K. Ko{\c c}", 
	title = "Exponentiation using canonical recoding",
	journal = TCS,
	year = 1994,
	volume = 129,
	pages = "407-417"}

@unpublished{deMelo&Svaiter:1995,
	key = "de Melo and Svaiter 1995",
	author = "Melo, W. de and Svaiter, B. F.",
	title = "The cost of computing integers",
	note = "To appear, {\it Proc.\ Amer.\ Math.\ Soc.}",
	year = 1995}

@article{Thurber:1993,
	key = "Thurber 1993",
	author = "E. G. Thurber",
	title = "Addition chains -- an erratic sequence",
	journal = DM,
	volume = 122,
	year = 1993,
	pages = "287-305"}

@article{Utz:1953,
	key = "Utz 1953",
	author = "W. R. Utz",
	title = "A note on the {Scholz-Brauer} problem in addition chains",
	journal = PAMS,
	volume = 4,
	year = 1953,
	pages = "462-463"}