Определение нулевых бит задачи 3-выполнимость, ассоциированной с задачей факторизации
Огородников Ю.Ю., Файзуллин Р.Т.

PDF, 235 kB

DOI: 10.18287/0134-2452-2014-38-3-521-528

Страницы: 521-528.

Аннотация:
В работе приведены два эвристических способа распознавания нулевых бит задачи ВЫПОЛНИМОСТЬ, ассоциированной с задачей факторизации. Первый основывается на сведении задачи ВЫПОЛНИМОСТЬ к эквивалентной задаче минимизации непрерывной гладкой функции методом последовательных приближений. В свою очередь, данный метод расширяется путём изменения порядка вычисления переменных. Другой способ заключается в сведении к системе линейных алгебраических уравнений с симметричной матрицей диагонального преобладания.

Ключевые слова :
ВЫПОЛНИМОСТЬ, метод последовательных приближений, изменение порядка обхода переменных, диагональный способ, факторизация.

Литература:

  1. Cook, S. The complexity of theorem-proving procedures / S. Cook // Proceedings of the Third Annual ACM Symposium on Theory of Computing. – 1971. – P. 151-158.
  2. Дулькейт, В.И. Сведение задач факторизации, дискретного логарифмирования и логарифмирования на эллиптической кривой к решению ассоциированных задач ВЫПОЛНИМОСТЬ / В.И. Дулькейт // Компьютерная оптика. – 2010. – T. 34, №1. – C. 118-123. – ISSN 0134-2452.
  3. Menezes, A. Handbook of applied cryptography / A. Menezes, P. van Oorschot, S. Vanstone. – CRC Press, 2001. – 780 p.
  4. Patsakis, C. RSA private key reconstruction from random bits using SAT solvers [Electronic resource]. – Mode of access: https://eprint.iacr.org/2013/026 . – Access date: 01.03.2013.
  5. Martin, D. A Machine Program for Theorem Proving / D. Martin, G. Logemann, L. Donald // Communications of the ACM. – 1962. – V. 5(7). – P. 394–397. – ISSN: 0001-0782.
  6. Дулькейт, В.И. Непрерывные аппроксимации решения задачи ВЫПОЛНИМОСТЬ применительно к криптографическому анализу асимметричных шифров / В.И. Дулькейт, Р.Т. Файзуллин, И.Г. Хныкин // Компьютерная оптика. – 2009. – T. 33, №1. – С. 68-73. – ISSN 0134-2452.
  7. Дулькейт, В.И. Гибридный метод поиска приближенного решения задачи 3-ВЫПОЛНИМОСТЬ, ассоциированной с задачей факторизации / В.И. Дулькейт, Ю.Ю. Огородников, Р.Т. Файзуллин // Труды института математики и механики УрО РАН. – 2013. – Т. 33, №2. – С. 285-294.
  8. Численные методы / А.А. Самарский, А.В. Гулин. – M.: Физматлит, 1989. – 432 с. – ISSN: 0134-4889.
  9. Липский, В. Комбинаторика для программистов / В. Липский; пер. с польск. – М.: Мир, 1988. – 200 с.
  10. Файзуллин, Р.Т. Задачи линейной алгебры, соотнесенные с задачей ВЫПОЛНИМОСТЬ / Р.Т. Файзуллин // Прикладная дискретная математика. – 2009. – Приложение № 1. – С. 90–91. – ISSN: 2071-0410.
    © 2009, IPSI RAS
    Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; E-mail: ko@smr.ru; Phones: +7 (846) 332-56-22, Fax: +7 (846) 332-56-20