Geodesic
Application of the Monte Carlo method for estimating the total time of solving the SAT problem in parallel
Numerical methods and programming, Tome 15 (2014) no. 1, pp. 22-35.

Voir la notice de l'article provenant de la source Math-Net.Ru

The application of the Monte Carlo method to plan the solving process for hard examples of the Boolean satisfiability problem (SAT) on parallel computing systems is discussed. The parallelization of the SAT problem is reached as a result of choosing the subset of the set of variables of an original CNF (Conjunctive Normal Form). This set is called a decomposition set. For such sets, we can naturally define a number of parameters to measure the “quality” of decomposition. In order to evaluate these parameters, we use the computational scheme based on the Monte Carlo method. In particular, this method is used to search for the decomposition set with minimal predicted time of solving the original problem. Using the implemented parallel MPI-program, it is possible to obtain a prediction of time required to perform the logical cryptanalysis of the Bivium cipher on a computing cluster. We successfully performed the logical cryptanalysis of several weakened versions of the Bivium cipher. The computing cost of such a cryptanalysis is in agreement with the predicted one.
Keywords: MPI, Boolean satisfiability problem (SAT), Monte Carlo method, tabu search, MPI, Bivium cipher.
Mots-clés : cryptanalysis 
@article{VMP_2014_15_1_a2,
     author = {O. S. Zaikin and A. A. Semenov},
     title = {Application of the {Monte} {Carlo} method for estimating the total time of solving the {SAT} problem in parallel},
     journal = {Numerical methods and programming},
     pages = {22--35},
     publisher = {mathdoc},
     volume = {15},
     number = {1},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2014_15_1_a2/}
}
TY  - JOUR
AU  - O. S. Zaikin
AU  - A. A. Semenov
TI  - Application of the Monte Carlo method for estimating the total time of solving the SAT problem in parallel
JO  - Numerical methods and programming
PY  - 2014
SP  - 22
EP  - 35
VL  - 15
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2014_15_1_a2/
LA  - ru
ID  - VMP_2014_15_1_a2
ER  - 
%0 Journal Article
%A O. S. Zaikin
%A A. A. Semenov
%T Application of the Monte Carlo method for estimating the total time of solving the SAT problem in parallel
%J Numerical methods and programming
%D 2014
%P 22-35
%V 15
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2014_15_1_a2/
%G ru
%F VMP_2014_15_1_a2
O. S. Zaikin; A. A. Semenov. Application of the Monte Carlo method for estimating the total time of solving the SAT problem in parallel. Numerical methods and programming, Tome 15 (2014) no. 1, pp. 22-35. http://geodesic.mathdoc.fr/item/VMP_2014_15_1_a2/