АЛГОРИТМИ ФАКТОРИЗАЦІЇ ТА ПЕРЕВІРКИ НЕЗВІДНОСТІ ПОЛІНОМІВ З ВИКОРИСТАННЯМ АПАРАТУ ЕЛІПТИЧНИХ КРИВИХ
DOI:
https://doi.org/10.20535/2074-9481.1(33).2017.169701Ключові слова:
Незвідні поліноми, еліптичні криві, теорема ЛєнстриАнотація
У цій роботі сформульовані та обґрунтовані критерії незвідності поліномів та алгоритми їх факторізації, які є узагальненнями аналогічних критеріїв та алгоритмів для чисел. Особливий цікавим є узагальнення теореми Лєнстра, що забезпечує правильне обчислення кратних точок на еліптичній кривій, які використовуються у алгоритмі Лєнстра. Зазначимо, що доведення узагальнення цієї теореми у випадку поліномів над полем характеристики 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.
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2017 Олексій Беспалов
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори, які публікуються у цьому збірнику, погоджуються з такими умовами:
1 Автори залишають за собою право на авторство своєї роботи та передають цьому збірнику право першої публікації своєї роботи, яка після публікації друкованої версії збірника автоматично стає доступною на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому збірнику.2 Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи у тому вигляді, в якому вона була опублікована цим збірником (наприклад, розміщувати роботу в електронному сховищі установи або публікувати у складі монографії), за умови збереження посилання на першу публікацію роботи у цьому збірнику.
3 Політика збірника дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи, як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи.
