ABSTRACT. Many problems, including algebraic cryptanalysis, can be transformedto a problem of solving a (large) system of sparse Boolean equations. Inthis article we study 2 algorithms that can be used to remove some redundancyfrom such a system: Agreeing, and Syllogism method. Combined with appropriateguessing strategies, these methods can be used to solve the whole system ofequations. We show that a phase transition occurs in the initial reduction of therandomly generated system of equations. When the number of (partial) solutionsin each equation of the system is binomially distributed with probability of partialsolution p, the number of partial solutions remaining after the initial reductionis very low for p's below some threshold pt, on the other hand for p > pt thereduction only occurs with a quickly diminishing probability.
@article{69,
title = {Phase transition in a system of random sparse boolean equations},
journal = {Tatra Mountains Mathematical Publications},
volume = {45},
year = {2010},
doi = {10.2478/tatra.v45i0.69},
language = {EN},
url = {http://dml.mathdoc.fr/item/69}
}
Schilling, Thorsten; Zajac, Pavol. Phase transition in a system of random sparse boolean equations. Tatra Mountains Mathematical Publications, Tome 45 (2010) . doi : 10.2478/tatra.v45i0.69. http://gdmltest.u-ga.fr/item/69/