Geodesic
On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a~part of variables
Diskretnaya Matematika, Tome 23 (2011) no. 4, pp. 66-79.

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

@article{DM_2011_23_4_a4,
     author = {A. S. Meluzov},
     title = {On construction of efficient algorithms for solving systems of polynomial {Boolean} equations by testing a~part of variables},
     journal = {Diskretnaya Matematika},
     pages = {66--79},
     publisher = {mathdoc},
     volume = {23},
     number = {4},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_4_a4/}
}
TY  - JOUR
AU  - A. S. Meluzov
TI  - On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a~part of variables
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 66
EP  - 79
VL  - 23
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_4_a4/
LA  - ru
ID  - DM_2011_23_4_a4
ER  - 
%0 Journal Article
%A A. S. Meluzov
%T On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a~part of variables
%J Diskretnaya Matematika
%D 2011
%P 66-79
%V 23
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_4_a4/
%G ru
%F DM_2011_23_4_a4
A. S. Meluzov. On construction of efficient algorithms for solving systems of polynomial Boolean equations by testing a~part of variables. Diskretnaya Matematika, Tome 23 (2011) no. 4, pp. 66-79. http://geodesic.mathdoc.fr/item/DM_2011_23_4_a4/

[1] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, Moskva, 1982 | MR

[2] Gorshkov S. P., “Primenenie teorii $NP$-polnykh zadach dlya otsenki slozhnosti resheniya sistem bulevykh uravnenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 2:3 (1995), 325–398 | MR

[3] Smirnov V. G., “Nekotorye klassy klassy effektivno reshaemykh sistem bulevykh uravnenii”, Trudy po diskretnoi matematike, 3, 2000, 269–282

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

[5] Faugère J.-C., “A new efficient algorithm for computation Gröebner bases ($F_4$)”, J. Pure Appl. Algebra, 139 (1999), 61–88 | DOI | MR | Zbl

[6] Faugère J.-C., “A new efficient algorithm for computation Gröebner bases without reduction to zero ($F_5$)”, Proc. ESSAC' 2002, ed. Mora T., ACM Press, New York, 2002, 75–83 | MR | Zbl

[7] Courtois N., Meier W., “Algebraic attacks on stream ciphers with linear feedback”, Lecture Notes Computer Sci., 2656, 2003, 345–359 | MR | Zbl

[8] Meier W., Pasalic E., Carlet C., “Algebraic attacks and decomposition of Boolean functions”, Lecture Notes Computer Sci., 3027, 2004, 474–491 | MR | Zbl

[9] Semaev I., “On solving sparse algebraic equations over finite fields”, Des. Codes Cryptography, 49 (2008), 47–60 | DOI | MR | Zbl

[10] Meluzov A. S., “Ispolzovanie assotsiativnykh printsipov obrabotki informatsii dlya postroeniya algoritmov resheniya sistem bulevykh uravnenii”, Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki, 50:11 (2010), 2028–2044 | MR | Zbl

[11] Bard G., Algebraic cryptanalysis, Springer, New York, 2009 | MR

[12] Lobanov M. S., “Tochnoe sootnoshenie mezhdu nelineinostyu i algebraicheskoi immunnostyu”, Diskretnaya matematika, 18:3 (2006), 152–159 | MR | Zbl

[13] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13 (1969), 354–356 | DOI | MR | Zbl

[14] Logachev O. A., Salnikov A. A., Yaschenko V. V., “Korrelyatsionnaya immunnost i realnaya sekretnost”, Matematika i bezopasnost informatsionnykh tekhnologii, MTsNMO, Moskva, 2004, 176–178

[15] Kolchin V. F., Sluchainye grafy, Nauka, Moskva, 2004

[16] Sachkov V. N., “Sistemy sluchainykh uravnenii nad konechnymi polyami”, Trudy po diskretnoi matematike, 8, 2004, 176–178

[17] Courtois N., Klimov A., Patarin J., Shamir A., “Efficient algorithms for solving overdefined systems of multivariate polynomial equations”, Lecture Notes Computer Sci., 1807, 2000, 392–407 | MR | Zbl

[18] Courtois N., Pieprzyk J., “Cryptanalysis of block ciphers with overdefined systems of equations”, Lecture Notes Computer Sci., 2501, 2002, 267–287 | MR | Zbl

[19] Bardet M. T., Faugère J.-C., Salvy B., Complexity of Gröbner basis computation for semi-regular overdetermined sequences over $GF(2)$ with solutions in $GF(2)$, INRIA Research Report 5049, 2003