Research ArticleOpen AccessGoogle Scholar indexed
Scholz’s First Conjecture: A Brief Demonstration
Campus Costa Chica, Universidad Autónoma de Guerrero, Guerrero, México
Facultad de Matemáticas, Universidad Autónoma de Guerrero, Acapulco, México
Facultad de Matemática y Computación, Universidad de la Habana, Ciudad de La Habana, Cuba
Campus Costa Chica, Universidad Autónoma de Guerrero, Guerrero, México
- 1 Campus Costa Chica, Universidad Autónoma de Guerrero, Guerrero, México
- 2 Facultad de Matemáticas, Universidad Autónoma de Guerrero, Acapulco, México
- 3 Facultad de Matemática y Computación, Universidad de la Habana, Ciudad de La Habana, Cuba
- 4 Campus Costa Chica, Universidad Autónoma de Guerrero, Guerrero, México
Copy link · social · email
Abstract
This paper presents a brief demonstration of Schulz’s first conjecture, which sets the upper and lower limits on the length of the shortest chain of addition. Two methods of the upper limit are demonstrated; the second one is based on the algorithm of one of the most popular methods for obtaining addition chains of a number, known as the binary method.
KeywordsAddition ChainExponentiationShort ChainScholz’s ConjectureBinary Method
- Scholz, A. (1937) Aufgabe 253. Jahresbericht der Deutschen Mathematiker-Vereingung, 47, 41-42.
- Brauer, A.T. (1939) On Addition Chains. Bulletin of the American Mathematical Society, 45, 736-739. http://dx.doi.org/10.1090/S0002-9904-1939-07068-7
- Knuth, D.E. (1969) The Art of Computer Programming. Vol. 1: Fundamental Algorithms. Second Printing, Addison- Wesley Publishing Co., Reading.
- Kunihiro, N. and Yamamoto, H. (2000) New Methods for Generating Short Addition Chains. IEICE Transactions on Fundamentals, E83-A, 60-67.
- Koc, C.K. (1995) Analysis of Sliding Window Techniques for Exponentiation. Computers & Mathematics with Applications, 30, 17-24. http://dx.doi.org/10.1016/0898-1221(95)00153-P
- Cruz-Cortes, N., et al. (2008) An Artificial Immune System Heuristic for Generating Short Addition Chains. IEEE Transactions on Evolutionary Computation, 12, 1-24. http://dx.doi.org/10.1109/TEVC.2007.906082
- Bos, J. and Coster, M. (1990) Addition Chain Heuristics. Advances in Cryptology, 435, 400-407. http://dx.doi.org/10.1007/0-387-34805-0_37
- Sautto-Vallejo, J.M., Agustín, S.-M., Carlos, B.-H. and Verónica, C.-G. (2013) Scholz’s Third Conjecture: A Demonstration for Star Addition Chains. Applied Mathematics, 4, 1-12. http://dx.doi.org/10.4236/am.2013.410A1001