АЛГОРИТМИ ФАКТОРИЗАЦІЇ ТА ПЕРЕВІРКИ НЕЗВІДНОСТІ ПОЛІНОМІВ З ВИКОРИСТАННЯМ АПАРАТУ ЕЛІПТИЧНИХ КРИВИХ

Олексій Беспалов

Анотація


У цій роботі сформульовані та обґрунтовані критерії незвідності поліномів та алгоритми їх  факторізації, які є узагальненнями  аналогічних критеріїв та алгоритмів для чисел. Особливий цікавим  є узагальнення теореми Лєнстра, що забезпечує правильне  обчислення кратних точок на еліптичній кривій, які використовуються у алгоритмі Лєнстра. Зазначимо, що доведення узагальнення цієї теореми у випадку поліномів над полем  характеристики 2 повністю відрізняється від її доведення у класичному випадку і є дуже нетривіальним. Використовуючи  побудовані критерії, розроблено ряд алгоритмів факторизації та
перевірки незвідності поліномів над скінченним полем. Слід  зазначити, що основною перевагою даних алгоритмів є не їх швидкодія,  а  використання  в  їх  структурі абелевих  груп,  які  побудовані  на  еліптичних кривих. Тому у випадку невдачі можна просто перевибрати еліптичну криву над відповідним полем  і  повторити  алгоритм  ще  раз. Хоча ці алгоритми і не  дають  суттєвої  переваги у швидкодії, як і їх прообрази – аналогічні
алгоритми для чисел, але вони демонструють нові підходи до вирішення давно існуючої та актуальної задачі перевірки незвідності поліномів, а також є досить цікавими з точки зору математики.

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


Незвідні поліноми; еліптичні криві; теорема Лєнстри

Посилання


М. Глухов, И. Круглов. А. Пичкур, А. Черёмушкин, "Введение в теоретико-числовые методы криптографии" // СПб.: Изд-во "Лань", 2011г., 400с.

Завадская Л. А. Потоковые системы шифрования, ocнованные на регистрах сдвига // Безопасность информации. – 1995. – Ν 3. – С. 12-17.

A. Canteaut, M. Trabbia. Improved fast correlation attacks using parity-check equations of weight 4 and 5, Advances in Cryptology–EUROCRYPT’2000, Lecture Notes in Computer Science, vol. 1807, Springer-Verlag, 2000 – P. 573–588.

V. Chepyzhov, T. Johansson, B. Smeets, A simple algorithm for fast correlation attacks on stream ciphers, Fast Software Encryption, FSE’2000, Lecture Notes in Computer Science, Springer-Verlag, 2000. – P. 313–324.

M. P. C. Fossorier, M. J. Mihaljevic, H. Imai. Reduced complexity iterative decoding of Low Density Parity Check codes based on Belief Propagation, IEEE Transactions on Communications, vol. 47, 1999. – P. 673-680.

Lidl R., Niederrieter H. Finite fields. – London: Addison-Wesley Publishing Company, 1983. - 819p.

Ковальчук Л. Псевдонеприводимые полиномы. Вероятностное тестирование неприводимости // Кибернетика и системный анализ. – 2004. – №4 – С. 168-176.

Вербицький О. В. Вступ до криптології./ Львів: Видавництво науково-технічної літератури, 1998. – 247с.

Schneier B. Applied cryptography, 2nd Edition, John Wiley & Sons (1996). [Имеется перевод: Шнайер Б. Прикладная криптография. - М.: "Триумф". – 2002. – 816с., Режим доступу: http://www.ssl.stu.neva.ru/psw/crypto/html – Заголовок з екрану.].

Koblitz N. A. Course of Number Theory and Cryptography. - Berlin: Springer, 1994.-231p.

Скрыпник Л.В., Ковальчук Л.В. Тест Ферма-Лукаса распознавания полиномов Галуа над кольцами Галуа // Вісник Східноукраїнського національного університету імені Володимира Даля – 2006. – №2 (103), частина 1. – С. 13-16.

Нечаев А.А. Код Кирдока в циклической форме // Дискретная математика: – 1989. – т.1, вып. 4. – C. 123-139.

Алексейчук А. Н., Волошин А. Л., Скрыпник Л. В. Совершенная схема множественного разделения секрета на основе линейных преобразований над конечным цепным коммутативным кольцом // Математика и безопасность информационных технологий. Материалы международной научной конференции по безопасности и противодействия терроризму. Интеллектуальный Центр МГУ. 2 – 3 ноября 2005 г. М.: МЦНМО, 2006. – С. 149 – 154.

Pocklington H. The determination of the prime and composite nature of large numbers by Fermat's theorem.- Proc. Cambridge Phil. Soc, 1914-16, v. 18, p. 29-30.

Goldwasser S., Kilian J. Almost all primes can be quickly certified. - In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, p. 316-329.

Schoof R. Elliptic curves over finite fields and the computation of square roots mod p. - Math. Сотр., 1985, v. 44, p. 483-494.

Pollard J. M. Theorems on factorization and primality testing. - Proc. Cambridge Phil. Soc, 1974, v. 76, p. 521-528.

Lenstra A.K., Lenstra H. W.,Jr. Algorithms in number theory. - Technical Report 87-008. Chicago: University of Chicago, 1987.

Lenstra H. W., Jr. Elliptic curves and number-theoretic algorithms. - Report 86-19. Amsterdam: Mathematisch Instituut, Universiteit van Amsterdam, 1986.

Lenstra Н. W., Jr. Factoring integers with elliptic curves. - Ann. Math., 1987, v. 126, p. 649-673.




Copyright (c) 2017 Олексій Беспалов

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