Вдосконалення методу нормування в кільці p-адичних чисел

Роман Сергійович Ганзя

Анотація


Аналізуються методи обчислення норми елемента в кільці p-адичних чисел. Пропонується використання альтернативного методу обчислення результанта через детермінант матриці Сильвестра, що може бути застосований для розрахунку норми елемента. Наводиться наша модифікація такого метода обчислення норми через зменшену матрицю Сильвестра. В роботі показано розрахунок теоретичної складності виконання методів, а також представлено порівняння теоретичних та практичних значень обчислення норми. Результати досліджень можуть бути використані при обчислені порядку еліптичних кривих в певних системних рішеннях.


Ключові слова


порядок еліптичної кривої; обчислення норми; матриця Сильвестра; результант.

Повний текст:

PDF

Посилання


Hanzia, R. (2017). Metodolohiia heneruvannia sylnykh kryptohrafichnykh zahalnosystemnykh parametriv eliptychnykh kryvykh. Problemy kiberbezpeky informatsiino-telekomunikatsiinykh system. Kyiv: Kyivskyi natsionalnyi universytet imeni Tarasa Shevchenka, 40–44.

Hanzia, R. S. (2016). Otsinka obchyslyuval'noyi skladnosti metodiv pidrakhunku kil'kosti tochok na eliptychniy kryviy. Systemy obrobky informatsiyi, 8 (145), 92–99.

Gorbenko, I., Hanzia, R. (2017). Examination and implementation of the fast method for computing the order of elliptic curve. Eastern-European Journal of Enterprise Technologies, 2 (9 (86)), 11–21. doi: 10.15587/1729-4061.2017.95194

Gorbenko, I., Hanzia, R. (2014). Analysis of the possibility of quantum computers and quantum computings for cryptanalysis of modern cryptosystems. Eastern-European Journal of Enterprise Technologies, 1 (9 (67)), 8–16. Available at: http://journals.uran.ua/eejet/article/view/19897/18759

Horbenko, I. D., Horbenko, Yu. I. (2012). Prykladna kryptolohiya. Kharkiv: Fort, 868.

Schoof, R. (1995). Counting points on elliptic curves over finite fields. Journal de Théorie Des Nombres de Bordeaux, 7 (1), 219–254. doi: 10.5802/jtnb.142

Vercauteren, F. (2013). Computing zeta functions of curves over finite fields. Katholieke Universiteit Leuven, 195.

Satoh, T., Skjernaa, B., Taguchi, Y. (2003). Fast computation of canonical lifts of elliptic curves and its application to point counting. Finite Fields and Their Applications, 9 (1), 89–101. doi: 10.1016/s1071-5797(02)00013-8

Harley, R. (2002). Asymptotically optimal p-adic point-counting. Listserv. Available at: https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0212&L=NMBRTHRY&F=&S=&P=7824

Skjernaa, B. (2002). Satoh's algorithm in characteristic 2. Mathematics of Computation, 72 (241), 477–488. doi: 10.1090/s0025-5718-02-01434-5

Blake, I. F., Seroussi, G., Smart, N. P. (Eds.) (2005). Advances in Elliptic Curve Cryptography. NY, USA, 281. doi: 10.1017/cbo9780511546570

Satoh, T. (2001). Asymptotically fast algorithm for computing the Frobenius substitution and norms over unramied extension of p-adic number fields. Department of Mathematics, Faculty of Science, Saitame University, 1–21.

Cohen, H., Frey, G. (2006). Elliptic and Hyperelliptic Curve Cryptography. NW.: Chapman & Hall/CRC, 843.

Kedlaya, K. S. (2001). Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology. J. Ramanujan Math. Soc., 16, 323–328.

Moenck, R. T. (1973). Fast computation of GCDs. Proceedings of the Fifth Annual ACM Symposium on Theory of Computing – STOC ’73. doi: 10.1145/800125.804045

Akritas, A. G. (1993). Sylvester's Forgotten Form of the Resultant. Fibonacci Quart, 31 (4), 325–332.

Mahaznykov, L. Mahaznykova, A. (2010). Lyneinaia alhebra. Analytycheskaia heometryia. Tomsk, 176.

Bunch, J. R., Hopcroft, J. E. (1974). Triangular Factorization and Inversion by Fast Matrix Multiplication. Mathematics of Computation, 28 (125), 231. doi: 10.2307/2005828

Bach, E. (1996). Algorithmic Number Theory. Vol. 1: Efficient Algorithms. Massachusetts Institute of Technology, 512.


Пристатейна бібліографія ГОСТ


Ганзя, Р. С. Методологія генерування сильних криптографічних загальносистемних параметрів еліптичних кривих [Текст] / Р. С. Ганзя // Проблеми кібербезпеки інформаційно-телекомунікаційних систем. – Київ: Київський національний університет імені Тараса Шевченка, 2017. – С. 40–44.

Ганзя, Р. С. Оцінка обчислювальної складності методів підрахунку кількості точок на еліптичній кривій [Текст] / Р. С. Ганзя // Системи обробки інформації. – 2016. – Вип. 8 (145). – C. 92–99.

Gorbenko, I. Examination and implementation of the fast method for computing the order of elliptic curve [Text] / I. Gorbenko, R. Hanzia // Eestern-European Journal of Enterprise Technologies. – 2017. – Vol. 2, Issue 9 (86). – P. 11–20. doi: 10.15587/1729-4061.2017.95194 

Горбенко, Ю. І. Аналіз можливостей квантових комп’ютерів та квантових обчислень для криптоаналізу сучасних криптосистем [Текст] / Ю. І. Горбенко, Р. С. Ганзя // Восточно-Европейский журнал передових технологий. – 2014. – Т. 1, № 9 (67). – C. 8–16. – Режим доступа: http://journals.uran.ua/eejet/article/view/19897/18759

Горбенко, І. Д. Прикладна криптологія [Текст]: монографія / І. Д. Горбенко, Ю. І. Горбенко; ХНУРЕ. – Х.: Форт, 2012. – 868 с.

Schoof, R. Counting points on elliptic curves over finite fields [Text] / R. Schoof // Journal de Théorie des Nombres de Bordeaux. – 1995. – Vol. 7, Issue 1. – P. 219–254. doi: 10.5802/jtnb.142 

Vercauteren, F. Computing zeta functions of curves over finite fields [Text]: dissertation for the degree of PhD / F. Vercauteren. – Katholieke Universiteit Leuven, 2003. – 195 p.

Satoh, T. Fast computation of canonical lifts of elliptic curves and its application to point counting [Text] / T. Satoh, B. Skjernaa, Y. Taguchi // Finite Fields and Their Applications. – 2003. – Vol. 9, Issue 1. – P. 89–101. doi: 10.1016/s1071-5797(02)00013-8 

Harley, R. Asymptotically optimal p-adic point-counting [Electronic resource] / R. Harley // Listserv. – 2002. – Available at: https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0212&L=NMBRTHRY&F=&S=&P=7824

Skjernaa, B. Satoh's algorithm in characteristic 2 [Text] / B. Skjernaa // Mathematics of Computation. – 2002. – Vol. 72, Issue 241. – P. 477–488. doi: 10.1090/s0025-5718-02-01434-5 

Advances in Elliptic Curve Cryptography [Text] / I. F. Blake, G. Seroussi, N. P. Smart (Eds.). – NY, USA, 2005. – 281 p. doi: 10.1017/cbo9780511546570 

Satoh, T. Asymptotically fast algorithm for computing the Frobenius substitution and norms over unramied extension of p-adic number fields [Text] / T. Satoh. – Department of Mathematics, Faculty of Science, Saitame University, 2001. – P. 1–21.

Cohen, H. Elliptic and Hyperelliptic Curve Cryptography [Text] / H. Cohen, G. Frey. – NW.: Chapman & Hall/CRC, 2006. – 843 p.

Kedlaya, K. S. Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology [Text] / K. S. Kedlaya // J. Ramanujan Math. Soc. – 2001. – Vol. 16. – P. 323–328.

Moenck, R. T. Fast computation of GCDs [Text] / R. T. Moenck // Proceedings of the fifth annual ACM symposium on Theory of computing – STOC '73. – 1973. doi: 10.1145/800125.804045 

Akritas, A. G. Sylvester's Forgotten Form of the Resultant [Text] / A. G. Akritas // Fibonacci Quart. – 1993. – Vol. 31, Issue 4. – P. 325–332.

Магазников, Л. И. Линейная алгебра. Аналитическая геометрия [Текст]: уч. пос. / Л. И. Магазников, А. Л. Магазникова; Томский государственный университет систем управления и радиоэлектроники. – Томск, 2010. – 176 с.

Bunch, J. R. Triangular Factorization and Inversion by Fast Matrix Multiplication [Text] / J. R. Bunch, J. E. Hopcroft // Mathematics of Computation. – 1974. – Vol. 28, Issue 125. – P. 231. doi: 10.2307/2005828 

Bach, E. Algorithmic Number Theory. Vol. 1: Efficient Algorithms [Text] / E. Bach, J. Shalit; Cambridge, Massachusetts. – Massachusetts Institute of Technology, 1996. – 512 p.



Посилання

  • Поки немає зовнішніх посилань.




Copyright (c) 2017 Роман Сергійович Ганзя

Creative Commons License
Ця робота ліцензована Creative Commons Attribution 4.0 International License.

ISSN 2411-2828 (Online), ISSN 2411-2798 (Print)