Czechoslovak Mathematical Journal, first online, pp. 1-10


The discrete logarithm problem over prime fields: the safe prime case. The Smart attack, non-canonical lifts and logarithmic derivatives

Hejmadi Gopalakrishna Gadiyar, Ramanathan Padma

Received March 20, 2017.   First published February 2, 2018.

Abstract:  We connect the discrete logarithm problem over prime fields in the safe prime case to the logarithmic derivative.
Keywords:  discrete logarithm; Hensel lift; group extension
Classification MSC:  11A07, 11T71, 11Y16, 14G50, 68Q25, 94A60
DOI:  10.21136/CMJ.2018.0128-17

PDF available at:  Institute of Mathematics CAS

References:
[1] E. Bach: Discrete Logarithms and Factoring. University of California, Computer Science Division, Berkeley (1984).
[2] A. Buium: Arithmetic analogues of derivations. J. Algebra 198 (1997), 290-299. DOI 10.1006/jabr.1997.7177 | MR 1482984 | Zbl 0892.13008
[3] P. J. Cameron, D. A. Preece: Primitive Lambda-Roots (2014). Available at https://cameron-counts.files.wordpress.com/2014/01/plr1.pdf .
[4] R. D. Carmichael: The Theory of Numbers. Wiley & Sons, New York (1914). JFM 45.0283.10
[5] W. Diffie, M. E. Hellman: New directions in cryptography. IEEE Trans. Inf. Theory 22 (1976), 644-654. DOI 10.1109/TIT.1976.1055638 | MR 0437208 | Zbl 0435.94018
[6] S. Goldwasser: New directions in cryptography: twenty some years later (or cryptography and complexity theory: a match made in heaven). Proc. of the 38th Annual IEEE Symposium on Foundations of Computer Science, Foundations of Computer Science (1997), 314-324. DOI 10.1109/SFCS.1997.646120
[7] H. Gopalakrishna Gadiyar, R. Padma: The discrete logarithm problem over prime fields can be transformed to a linear multivariable Chinese remainder theorem (2016). Available at ArXiv: 1608.07032v1
[8] H. Gopalkrishna Gadiyar, K. M. S Sangeeta Maini, R. Padma: Cryptography, connections, cocycles and crystals: a $p$-adic exploration of the discrete logarithm problem. Progress in Cryptology - INDOCRYPT 2004, 5th International Conf. on Cryptology in India, Chennai, 2004 (A. Canteaut et al.), Lecture Notes in Comput. Sci. 3348, Springer, Berlin (2004), 305-314. DOI 10.1007/978-3-540-30556-9_24 | MR 2147933 | Zbl 1115.94008
[9] D. Hilbert: The Theory of Algebraic Number Fields. Springer, Berlin (1998). DOI 10.1007/978-3-662-03545-0 | MR 1646901 | Zbl 0984.11001
[10] Y. Kawada: On the derivations in number fields. Ann. Math. (2) 54 (1951), 302-314. DOI 10.2307/1969531 | MR 0043830 | Zbl 0044.26702
[11] N. Koblitz: A Course in Number Theory and Cryptography. Graduate Texts in Mathematics 114, Springer, New York (1994). DOI 10.1007/978-1-4419-8592-7 | MR 1302169 | Zbl 0819.11001
[12] M. Kontsevich: The $1\frac12$-logarithm. Appendix to: On poly(ana)logs. I [Compositio Math. 130 (2002), 161-210] by P. Elbaz-Vincent and H. Gangl. Compositio Math. 130 (2002), 211-214. MR 1884238
[13] R. Kumanduri, C. Romero: Number Theory with Computer Applications. Prentice Hall, Upper Saddle River (1998). Zbl 0902.11001
[14] M. Lerch: Zur Theorie des Fermatschen Quotienten $\frac{{a^{p-1}-1}}p=q(a)$. Math. Ann. 60 (1905), 471-490 German. DOI 10.1007/BF01561092 | MR 1511321 | JFM 36.0266.03
[15] K. S. McCurley: The discrete logarithm problem. Cryptology and Computational Number Theory Lect. Notes AMS Short Course 1989, Proc. Symp. Appl. Math. 42 (1990), 49-74. DOI 10.1090/psapm/042/1095551 | MR 1095551 | Zbl 0734.11073
[16] H. Riesel: Some soluble cases of the discrete logarithm problem. BIT 28 (1988), 839-851. DOI 10.1007/BF01954904 | MR 0972809 | Zbl 0665.10002
[17] A. M. Robert: A Course in $p$-adic Analysis. Graduate Texts in Mathematics 198, Springer, New York (2000). DOI 10.1007/978-1-4757-3254-2 | MR 1760253 | Zbl 0947.11035
[18] T. Satoh, K. Araki: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Univ. St. Pauli 47 (1998), 81-92. MR 1624563 | Zbl 1044.11592
[19] I. A. Semaev: Evaluation of discrete logarithms in a group of $p$-torsion points of an elliptic curve in characteristic $p$. Math. Comput. 67 (1998), 353-356. DOI 10.1090/S0025-5718-98-00887-4 | MR 1432133 | Zbl 1016.11021
[20] J. H. Silverman: Lifting and elliptic curve discrete logarithms. Selected Areas in Cryptography. Proc. of 15th International Workshop on Selected Areas in Cryptography, Sackville, 2008 (R. M. Avanzi et al.), Lecture Notes in Computer Science 5381, Springer, Berlin (2009), 82-102. DOI 10.1007/978-3-642-04159-4_6 | Zbl 1256.94065
[21] N. P. Smart: The discrete logarithm problem on elliptic curves of trace one. J. Cryptology 12 (1999), 193-196. DOI 10.1007/s001459900052 | MR 1698180 | Zbl 0963.11068
[22] O. Teichmüller: Diskret bewertete perfekte Körper mit unvollkommenem Restklassenkörper. J. Reine Angew. Math. 176 (1936), 141-152. (In German.) DOI 10.1515/crll.1937.176.141 | MR 1581527 | Zbl 0016.05103
[23] O. Teichmüller: Über die Struktur diskret bewerteter perfekter Körper. Nachr. Ges. Wiss. Göttingen, math.-phys. Kl., FG 1, Neue Folge 1 (1936), 151-161. (In German). JFM 62.0110.01
[24] L. C. Washington: Introduction to Cyclotomic Fields. Graduate Texts in Mathematics 83, Springer, New York (1997). DOI 10.1007/978-1-4612-1934-7 | MR 1421575 | Zbl 0966.11047

Affiliations:   Hejmadi Gopalakrishna Gadiyar, Ramanathan Padma, Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Near Katpadi Road, Vellore 632014, Tamil Nadu, India, e-mail: gadiyar@vit.ac.in, rpadma@vit.ac.in


 
PDF available at: