The knapsack problem is used in many mathematical models, including in the field of information security. Solving a problem (finding the optimal knapsack load) or even answering the question about the existence of a valid solution is an NP-complete problem. In this regard, the question of finding the power of the set of acceptable solutions or estimates of this power is relevant. The paper analyzes the combinatorial aspects of this problem based on the method of generating functions. Formulas and estimates for the number of solutions and the average number of solutions depending on the coefficients of the constraint vector are obtained. On their basis, computational algorithms for finding these values can be constructed. All this can be used to assess the adequacy and quality of the original mathematical model.
For example, in the works of G.V. Balakin [8] and [9] consider specific classes of systems of Boolean equations (of recurrent type) and their application in cryptography.
In the work of A.M. Zubkov [10] the moment characteristics of the weights of vectors in random binary linear codes are described in terms of the properties of special systems of equations.
Linearization of systems of Boolean equations is a method for solving systems, which consists in replacing all monomials of degree higher than the first with new variables, solving the resulting linear system and then checking the obtained solutions for correctness. This, for example, is the subject of the articles [11], [12].
A group of scientists led by N. Courtois proposed improvements to XL4 and XSL5 of the linearization method for cases when the number of equations in the system is not enough to effectively apply linearization in the classical form [13]. The essence of these methods is to supplement the system with new equations that do not change the set of solutions to the system, but increase the size of the system and the rank of the linearized system. Later N. Courtois and G.V. Bard [14] proposed another method based on the ElimLin linearization method.
As it was said in the annotation, in our work we consider the problem of finding the number of feasible solutions. The results along this path are illustrated by works [15-17]. And in the applied works of A.S. Meluzov [18] and [19], a software package was developed and implemented to solve the above problem.
This article also discusses the problem of parametrization of the system on its right side. The authors are not aware of any analogues of the approach presented here. To some extent, both classical algorithms of parametric linear programming and, for example, work [20], where linear equations of the Boolean type with a “distorted” right-hand side are investigated, are related to it.
The paper proposes a method for constructing a set containing the desired vector with a probability not less than a given one, and estimates the cardinality of this set. Theoretical calculations of the parameters of the method are illustrated by the results of experiments. This approach uses a probabilistic setting, while the combinatorial apparatus is used here.
This work consists of an introduction and three sections. The main lemma is given in the next section. In the third section, we consider the question of the average number of solutions depending on the values of the right-hand side, and then in the section following this we consider the case of a hypercube of bounded volume.
Some definitions, concepts and methods of proof were previously used by the authors in [3-6].
In what follows, we will assume that all the parameters of the problem under consideration, the numbers c1,…,cn; a1,…,an; b - non-negative integers.
The answer to the question about the existence of solutions to the problem under consideration is already an NP-complete problem. Therefore, finding the number of solutions to the knapsack problem is currently carried out either by exhaustive search algorithms, or is estimated from heuristic methods.
In both cases, knowledge of the average number of solutions can be used both for constructing algorithms and for modifying them. In addition, formulas for finding the average number of solutions depending on the parameters of the problem can be used to assess the feasibility of using both exhaustive search and heuristic algorithms.
For example, we need to find at least one solution to an individual problem that lies in a class of problems with a fixed right-hand side. We find the average number of solutions in this class. If it is large, then this can serve as a justification for the expediency of using heuristic or probabilistic methods. Otherwise, the exhaustive search algorithm is most likely more reasonable.
The main method that is used in the work is the method of generating functions.
First, we directly express the volume of feasible solutions using the generating function for Pb ( z1,..., zn ) = ∑ z a1x1 z a2x2 ...znanxn .
1 2 x∈Vb
Lemma 1. The following formula is valid
1 − u Consequence. Let 0 <ρ <1. Then equality holds for the volume of the region of feasible solutions: 1 (1 + ua1 )...(1 + uan ) | Vb |=
Let us now consider the question of the average value of the volume of solutions. Let be
Recall that our variables are Boolean. The number b is fixed, and the dimension n is also fixed.
Therefore, each coefficient of the constraint vector varies from 0 to b, i.e. takes n + 1 values. Hence
(
Of course, the question of the average number of solutions is rather theoretical in nature. However, it sheds light on the combinatorics of the problem when investigating the interdependence of b and n.
Below we give several statements that give various formulas (calculation algorithms) for the average number of solutions. As an illustration of the use of the method of generating functions, their proofs are presented.
Theorem 1. The following formula is valid
1 n | Vb | =1)n∑k=0 (b + CnkCbn−k (b + 2)k .
Proof. Directly from (
. n−k Secondly, (1 − ub )n−k =1 − Cn1−kub + Cn2−ku2b − ... =∑ (−1)i Cni −kuib .
i=0
Therefore, further we have
u
∫
2π i |u|=ρ 1 − u
ub+1
Therefore, from (
i=0
(−1)b+k −n C−bn++kk−−n1 =(−1)b+k −n C−b(+nk−−kn+1) =−n Cbb+k
But now the assertion of the theorem follows from (
The theorem is proved. =n−k. C b Let's look at this expression from the other side.
Theorem 2. The following formula is valid
(b +11)n ∑n0 k =u−b+n−k Cnk (b + 2)k Couef {(1 + u)b −1} =(b +11)n Couef (1u+b−un+)1b ∑n0 k Cnk b +u 2 k = 1 (1 + u)b b + 2 n =Couef (b + 1)n ub−n+1 (1 + u
1 (1 + u)b =Coef (b + 1)n u ub+1
(u + b + 2)n = 1 (1 + u)b =Coef (b + 1)n u ub+1
((1 + u) + (b + 1))n n ∑ Cnk (1 + u)k (b + 1)n−k =Couef (b1+)n k =0 ub+1 (1 + u)b = 1 n (1 + u)b+k =∑ Cnk (b + 1)n−k Coef (1 + u)b (b + 1)n k =0 u ub+1 1 n =∑ CnkCbb+k (b + 1)n−k .
(b + 1)n k =0
(
Directly we get: | Vb | =33 / 9 4. Average number of solutions to the knapsack problem on a hypercube of a fixed size
Let us now consider the question of the average value of the volume of feasible solutions on a hypercube of a fixed size.
Let be tb (a1,..., an ) = 1 ∫ 2π i |u|=ρ (1 + ua1 )...(1 + uan ) =1,..., n and t c is the average value for the volume of feasible solutions on a .
Therefore, we have t c
c + 2 + 1 1 = ∫ (c + 1)n 2π i |u| ρ u − uc+1 n
1 − u 1 1
du =u)ub+1 (1 − =1n 1
∑ Cnk (c + 2)k (c + 1)n k =0 Now we will find the sum of the residues to calculate the integral ((c + 2)(1 − u) + u(1 − uc ))n =(1 (c + 1)n 2π i |u|∫ρ =u)n+1ub+1 − du 1 (1 − u)−n+k −1(1 − uc )n−k 2π i |u|∫=ρ ub+1+k −n du .
n−k Now, note that, (1 − uс )n−k =1 − Cn1−kuс + Cn2−ku2с − ... =∑ (−1)i Cni −kuiс . i=0 Therefore
1 n t c = (c + 1)n ∑k0 Cnk (c + 2)k
1 (1 − u )k −n−1 n−k =i|u|∫=ρ 2π ub+k −n+1 ∑r0 =du (−1)r Cnr−ku rc = = 1 n n−k 1 (1 − u )k −n−1
∑ Cnk (c + 2)k ∑ (−1)r Cnr−k 2π i |u|=ρ ub+k −n+1−rc du .
(c + 1)n k =0 r =0 ∫ Notice, that 1 (1 − u)−n+k −1
∫ 2π i |u|=ρ ub+1+k −n−кс du
0, b − rc ≤ 0 =−n+b−rc (−1)k C−b(−nr−c−k+n1+)k , b − rc ≥ n − k .
In the general case, we obtain
1 n n−k t c = ∑ Cnk (c + 2)k ∑ (−1)r Cnr−k (−1)k −n+b−rc C−b(−nr−c−k+n1+)k (c + 1)n k =0 r =0 1 n n−k = ∑ Cnk (c + 2)k ∑ (−1)r Cnr−kCbn−−rkc .
(c + 1)n k =0 r =0
=1 ∑n Cnk (c + 2)k ∑n−k (−1)r Cnr−kCbb−−rrcc−n+k (c + 1)n k =0 r =0
The method of generating functions can be successfully applied to the analysis of problems of a "combinatorial" nature. In the above study, with its help, new formulas were obtained for the number of olutions and the average number of solutions in the knapsack problem.
They can be improved and refined by considering equations not of a general, but of a special form. It is these problems that arise in specific applied areas, in particular, in mathematical models of information security, taking into account the real features of the original formulations.
Therefore, the results presented here can serve as a basis for further research.
The reliability of the results follows from the correctness of the definitions and proofs of the theorems.
The work was carried out with the support of a grant from the Russian Academy of Sciences: RFBR grant 20-01-00645.
.
[14] N. Courtois, G.V. Bard, Algebraic cryptanalysis of the data encryption standard, IMA International Conference on Cryptography and Coding Theory. Lecture Notes in Computer Science SpringerVerlag, Berlin, 2007, pp. 152-169. doi: https://doi.org/10.1007/3-540-36178-2_17. [15] F. Massacci, L. Marraro, Logical Cryptanalysis as a SAT Problem, Journal of Automated
Reasoning 24 (2000) 165-203. doi:10.1023/A:1006326723002. [16] C. Fiorini, E. Martinelli, F. Massacci, How to fake an RSA signature by encoding modular root nding as a SAT problem, Discrete Applied Mathematics 130 (2003) 101-127. [17] I. Mironov , L. Zhang, Applications of SAT Solvers to Cryptanalysis of Hash Functions, in: A.
Biere , C.P. Gomes (Eds), Theory and Applications of Satisfiability Testing - SAT 2006, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg, Vol. 4121, 2006, pp. 102-115. doi: https://doi.org/10.1007/11814948_13 [18] A.S. Meluzov, Construction of effective algorithms for solving systems of polynomial Boolean equations by testing a part of variables, Discrete Math. Appl., 21 (2011) 381–395. doi: 10.1515/DMA.2011.024. [19] A.S. Meluzov, The use of associative information processing for constructing algorithms for solving systems of Boolean equations, Mathematics and Mathematical Physics 50(2010) 19251940. doi:10.1134/S0965542510110151. [20] E.K. Alekseev, I.V. Oshkin, V.O. Popov, S.V. Smyshlyaev, Solving systems of linear Boolean equations with noisy right-hand sides over the reals, Discrete Math. Appl., 28 (2018) 1-5. doi: 10.1515/dma-2018-0001.