Recognition of zero bits of 3-sat problem by applying linear algebra’s methods

Y.Y. Ogorodnikov, R.T. Faizullin

Omsk State Technical University

PDF, 235 kB

Full text of article: Russian language.

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

Pages: 521-528.

Abstract:
The paper presents two heuristic methods of recognizing zero bits satisfiability problem. The first is based on the reduction of the satisfiability problem to an equivalent problem of minimizing a continuous smooth function by method of successive approximations, extended by changing the order of calculation of variables. Another way is to reduce to a system of linear algebraic equations with symmetric diagonally dominant matrix.

Key words:
satisfiability, method of successive approximations, the order of calculation of variables, diagonal methods, factorization.

References:

  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. Dulkeit, V.I. Reduction of factorization, discrete logarithm and elliptic curve logarithm problems to solving associated satisfiability problems / V.I.Dulkeit // Computer Optics. – 2010. – V.34(1). – P. 118-123. – ISSN 0134-2452. – (In Russian).
  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. Dulkeit, V.I. Continuous approximation of SAT decision as applied to cryptographic analysis of asymmetric ciphers /V.I. Dulkeit, I.G.Hnikin, R.T.Faizullin // Computer Optics. – 2009. – V. 33(1). – P. 86–91. – ISSN 0134-2452. – (In Russian).
  7. Dulkeit, V.I. A hybrid method of searching the approximate solution of 3-SAT, associated with factorization problem / V.I. Dulkeit, R.T. Faizullin, Y.Y. Ogorodnikov // Proceedings of the Institute of Mathematics and Mechanics URAN. – 2013. – V. 19(2). – P. 285-294. – ISSN: 0134-4889. – (In Russian).
  8. Numerical methods / A.A. Samarski, A.V. Gulin. – M.: “Fismatlit” Publisher, 1989. – 432 p. – (In Russian).
  9. Witold Lipski. Kombinatoryka dla programistow. – “Warszawa” Publisher, 1982.
  10. Faizullin, R.T. Problems of linear algebra, correlated with the satisfiability problem / R.T. Faizullin //Applied Discrete Mathematics. – 2009. – Application № 1. – P. 90-91. – ISSN: 2071-0410. – (In Russian).
    © 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 2) 332-56-22, Fax: +7 (846 2) 332-56-20