| Title:
|
The discrete logarithm problem over prime fields: the safe prime case. The Smart attack, non-canonical lifts and logarithmic derivatives (English) |
| Author:
|
Gadiyar, Gopalakrishna Hejmadi |
| Author:
|
Padma, Ramanathan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
68 |
| Issue:
|
4 |
| Year:
|
2018 |
| Pages:
|
1115-1124 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
We connect the discrete logarithm problem over prime fields in the safe prime case to the logarithmic derivative. (English) |
| Keyword:
|
discrete logarithm |
| Keyword:
|
Hensel lift |
| Keyword:
|
group extension |
| MSC:
|
11A07 |
| MSC:
|
11T71 |
| MSC:
|
11Y16 |
| MSC:
|
14G50 |
| MSC:
|
68Q25 |
| MSC:
|
94A60 |
| idZBL:
|
Zbl 07031702 |
| idMR:
|
MR3881901 |
| DOI:
|
10.21136/CMJ.2018.0128-17 |
| . |
| Date available:
|
2018-12-07T06:24:18Z |
| Last updated:
|
2021-01-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147526 |
| . |
| Reference:
|
[1] Bach, E.: Discrete Logarithms and Factoring.University of California, Computer Science Division, Berkeley (1984). |
| Reference:
|
[2] Buium, A.: Arithmetic analogues of derivations.J. Algebra 198 (1997), 290-299. Zbl 0892.13008, MR 1482984, 10.1006/jabr.1997.7177 |
| Reference:
|
[3] Cameron, P. J., Preece, D. A.: Primitive Lambda-Roots.Available at\ https://cameroncounts.files.wordpress.com/2014/01/plr1.pdf (2014). |
| Reference:
|
[4] Carmichael, R. D.: The Theory of Numbers.Wiley & Sons, New York (1914),\99999JFM99999 45.0283.10. MR 0105381 |
| Reference:
|
[5] Diffie, W., Hellman, M. E.: New directions in cryptography.IEEE Trans. Inf. Theory 22 (1976), 644-654. Zbl 0435.94018, MR 0437208, 10.1109/TIT.1976.1055638 |
| Reference:
|
[6] Goldwasser, S.: 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. 10.1109/SFCS.1997.646120 |
| Reference:
|
[7] Gadiyar, H. Gopalakrishna, Padma, R.: The discrete logarithm problem over prime fields can be transformed to a linear multivariable Chinese remainder theorem.Available at ArXiv: 1608.07032v1 [math.NT] (2016). MR 3881901 |
| Reference:
|
[8] Gadiyar, H. Gopalkrishna, Maini, K. M. S Sangeeta, Padma, R.: 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, Lecture Notes in Comput. Sci. 3348 Springer, Berlin A. Canteaut et al. (2004), 305-314. Zbl 1115.94008, MR 2147933, 10.1007/978-3-540-30556-9_24 |
| Reference:
|
[9] Hilbert, D.: The Theory of Algebraic Number Fields.Springer, Berlin (1998). Zbl 0984.11001, MR 1646901, 10.1007/978-3-662-03545-0 |
| Reference:
|
[10] Kawada, Y.: On the derivations in number fields.Ann. Math. (2) 54 (1951), 302-314. Zbl 0044.26702, MR 0043830, 10.2307/1969531 |
| Reference:
|
[11] Koblitz, N.: A Course in Number Theory and Cryptography.Graduate Texts in Mathematics 114, Springer, New York (1994). Zbl 0819.11001, MR 1302169, 10.1007/978-1-4419-8592-7 |
| Reference:
|
[12] Kontsevich, M.: On poly(ana)logs. I. (With an appendix by Maxim Kontsevich: The $1\frac{1}{2}$-logarithm).Compositio Math. (2002), 130 161-210, 211-214. Zbl 1062.11042, MR 1884238, 10.1023/A:1013757217319 |
| Reference:
|
[13] Kumanduri, R., Romero, C.: Number Theory with Computer Applications.Prentice Hall, Upper Saddle River (1998). Zbl 0902.11001 |
| Reference:
|
[14] Lerch, M.: Zur Theorie des Fermatschen Quotienten $\frac{{a^{p-1}-1}}p=q(a)$.Math. Ann. 60 (1905), 471-490 German \99999JFM99999 36.0266.03. MR 1511321, 10.1007/BF01561092 |
| Reference:
|
[15] McCurley, K. S.: The discrete logarithm problem.Cryptology and Computational Number Theory Lect. Notes AMS Short Course 1989, Proc. Symp. Appl. Math. 42 (1990), 49-74. Zbl 0734.11073, MR 1095551, 10.1090/psapm/042/1095551 |
| Reference:
|
[16] Riesel, H.: Some soluble cases of the discrete logarithm problem.BIT 28 (1988), 839-851. Zbl 0665.10002, MR 0972809, 10.1007/BF01954904 |
| Reference:
|
[17] Robert, A. M.: A Course in $p$-adic Analysis.Graduate Texts in Mathematics 198, Springer, New York (2000). Zbl 0947.11035, MR 1760253, 10.1007/978-1-4757-3254-2 |
| Reference:
|
[18] Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves.Comment. Math. Univ. St. Pauli 47 (1998), 81-92. Zbl 1044.11592, MR 1624563 |
| Reference:
|
[19] Semaev, I. A.: Evaluation of discrete logarithms in a group of $p$-torsion points of an elliptic curve in characteristic $p$.Math. Comput. 67 (1998), 353-356. Zbl 1016.11021, MR 1432133, 10.1090/S0025-5718-98-00887-4 |
| Reference:
|
[20] Silverman, J. H.: Lifting and elliptic curve discrete logarithms.Selected Areas in Cryptography. Proc. of 15th International Workshop on Selected Areas in Cryptography, Sackville, 2008, Lecture Notes in Computer Science 5381 Springer, Berlin R. M. Avanzi et al. (2009), 82-102. Zbl 1256.94065, MR 2054769, 10.1007/978-3-642-04159-4_6 |
| Reference:
|
[21] Smart, N. P.: The discrete logarithm problem on elliptic curves of trace one.J. Cryptology 12 (1999), 193-196. Zbl 0963.11068, MR 1698180, 10.1007/s001459900052 |
| Reference:
|
[22] Teichmüller, O.: Diskret bewertete perfekte Körper mit unvollkommenem Restklassenkörper.J. Reine Angew. Math. 176 (1936), 141-152 German. Zbl 0016.05103, MR 1581527, 10.1515/crll.1937.176.141 |
| Reference:
|
[23] Teichmüller, O.: Über die Struktur diskret bewerteter perfekter Körper.Nachr. Ges. Wiss. Göttingen, math.-phys. Kl., FG 1, Neue Folge 1 (1936), 151-161 German \99999JFM99999 62.0110.01. |
| Reference:
|
[24] Washington, L. C.: Introduction to Cyclotomic Fields.Graduate Texts in Mathematics 83, Springer, New York (1997). Zbl 0966.11047, MR 1421575, 10.1007/978-1-4612-1934-7 |
| . |
