Geodesic
Hybrid method for the approximate solution of the $3$-satisfiability problem associated with the factorization problem
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 2, pp. 285-294 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

We consider a hybrid method for the approximate solution of the $3$-satisfiability problem associated with the factorization problem. The method consists of two stages: a segment genetic algorithm and the method of successive approximations. We propose a method for finding most probable bits of the solution. The method consists of several independent tests and makes it possible to approach the convergence domain of the hybrid method and determine several bits of the factors.
Keywords: satisfiability problem, factorization, segment genetic algorithm, minimization. 
@article{TIMM_2013_19_2_a27,
     author = {R. T. Faizullin and V. I. Dul'keit and Yu. Yu. Ogorodnikov},
     title = {Hybrid method for the approximate solution of the $3$-satisfiability problem associated with the factorization problem},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {285--294},
     year = {2013},
     volume = {19},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a27/}
}
TY  - JOUR
AU  - R. T. Faizullin
AU  - V. I. Dul'keit
AU  - Yu. Yu. Ogorodnikov
TI  - Hybrid method for the approximate solution of the $3$-satisfiability problem associated with the factorization problem
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2013
SP  - 285
EP  - 294
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a27/
LA  - ru
ID  - TIMM_2013_19_2_a27
ER  - 
%0 Journal Article
%A R. T. Faizullin
%A V. I. Dul'keit
%A Yu. Yu. Ogorodnikov
%T Hybrid method for the approximate solution of the $3$-satisfiability problem associated with the factorization problem
%J Trudy Instituta matematiki i mehaniki
%D 2013
%P 285-294
%V 19
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a27/
%G ru
%F TIMM_2013_19_2_a27
R. T. Faizullin; V. I. Dul'keit; Yu. Yu. Ogorodnikov. Hybrid method for the approximate solution of the $3$-satisfiability problem associated with the factorization problem. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 2, pp. 285-294. http://geodesic.mathdoc.fr/item/TIMM_2013_19_2_a27/

[1] Daemon J., Knudsen L., Rijmen V., “The block cipher square”, Proc. of Fast Software Encryption97, Lect. Not. Comput. Sci., 1267, 1997, 149–165 | DOI

[2] Courtois N., Pipzyk J., “Cryptanalysis of block ciphers with overdefined systems of equations”, Proc. Asiacrypt02, Lect. Not. Comput. Sci., 2501, 2002, 267–287 | DOI | MR | Zbl

[3] Koblitz N., Menezes A., Vanstone S., “The state of elliptic curve cryptography”, Des. Codes Cryptogr., 19:2–3 (2000), 173–193 | DOI | MR | Zbl

[4] Cook S. A., Mitchel D. G., “Finding hard instances for the satisfiability problem: A survey”, Proc. Satisfiability problem: theory and applications, DIMACS: Ser. Discrete Math. Theoret. Comput. Sci., 35, Amer. Math. Soc., Providence, 1997, 1–18 | MR

[5] Gu J., Purdom P. W., Franco J., Wah B. W., “Algorithms for the satisfability (SAT) problem”, Proc. Satisfiability problem: theory and applications, DIMACS: Ser. Discrete Math. Theoret. Comput. Sci., 35, Amer. Math. Soc., Providence, 1997, 19–152 | MR

[6] Eremin I. I., Astafev N. N., Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya, Fizmatlit, M., 1976, 192 pp. | MR

[7] Kreinovich V. Ya., “Semantika iterativnogo metoda S. Yu. Maslova”, Vopr. kibernetiki. Problemy sokrascheniya perebora, Izd-vo AN SSSR, M., 1987, 30–62 | MR

[8] Holland J. H., Adaptation in natural and artificial systems, An introductory analysis with applications to biology, control, and artificial intelligence, The University of Michigan Press, Ann Arbor, 1975, 183 pp. | MR

[9] Agrawal M., Kayal N., Saxena N., “PRIMES is in P”, Annal. of Math., 160:2 (2004), 781–793 | DOI | MR | Zbl

[10] Dulkeit V. I., Faizullin R. T., Khnykin I. G., “Algoritm minimizatsii funktsionala, assotsiirovannogo s zadachei 3-SAT i ego prakticheskie primeneniya”, Kompyuternaya optika, 32:1 (2008), 68–73

[11] Faizullin R. T., “Zadachi lineinoi algebry, sootnesennye s zadachei Vypolnimost”, Prikl. diskret. matematika, 2009, Prilozhenie No 1, 90–91

[12] Ogorodnikov Yu. Yu., Faizullin R. T., “Dvukhetapnyi metod poiska priblizhennogo resheniya zadachi Vypolnimost”, Dinamika sistem, mekhanizmov i mashin, Materialy 8-i Mezhdunar. nauch.-tekhn. konf., Omsk, 2012, 367–371