Geodesic
The use of associative information processing for constructing algorithms for solving systems of Boolean equations
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 11, pp. 2028-2044 
A. S. Meluzov. The use of associative information processing for constructing algorithms for solving systems of Boolean equations. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 11, pp. 2028-2044. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_11_a14/
@article{ZVMMF_2010_50_11_a14,
     author = {A. S. Meluzov},
     title = {The use of associative information processing for constructing algorithms for solving systems of {Boolean} equations},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {2028--2044},
     year = {2010},
     volume = {50},
     number = {11},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_11_a14/}
}
TY  - JOUR
AU  - A. S. Meluzov
TI  - The use of associative information processing for constructing algorithms for solving systems of Boolean equations
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 2028
EP  - 2044
VL  - 50
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_11_a14/
LA  - ru
ID  - ZVMMF_2010_50_11_a14
ER  - 
%0 Journal Article
%A A. S. Meluzov
%T The use of associative information processing for constructing algorithms for solving systems of Boolean equations
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 2028-2044
%V 50
%N 11
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_11_a14/
%G ru
%F ZVMMF_2010_50_11_a14

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

Possibilities of the application of dedicated processors based on the use of associative memory for solving systems of Boolean equations is considered. An algorithm for solving systems of Boolean equations using associative dedicated processors is proposed. Classes of systems of Boolean equations that can be efficiently solved by this algorithm are found. Subexponential estimates of the expectation of the computational complexity of the proposed algorithm for solving systems of equations belonging to these classes are obtained.

[1] O'Shi D., Koks D., Littl D., Idealy, mnogoobraziya i algoritmy, Mir, M., 2000

[2] Bardet M., Faugére J.-C., Salvy B., “On the complexity of Gröebner basis computation of semi-regular overdetermined algebraic equations”, ICPSS, 2004, 71–75

[3] Leontev V. K., Tonoyan G. P., “Priblizhennye resheniya sistem bulevykh uravnenii”, Zh. vychisl. matem. i matem. fiz., 33:9 (1993), 1383–1390 | MR

[4] Raddum H., Semaev I., “New technique for solving sparse”, Equation Systems, 2006 http://eprint.iacr.org/2006/475.pdf | Zbl

[5] Semaev I., “On solving sparse algebraic equations over finite fields, I”, Proc. WCC'07 (16–20 Avril 2007, Versailles, France), INRIA, 361–370 | MR

[6] Semaev I., On solving sparse algebraic equations over finite fields, II, , 2007 http://eprint.iacr.org/2007/280.pdf | MR

[7] Foster K., Assotsiativnye parallelnye protsessory, Energoizdat, M., 1981