Cryptography Reference
In-Depth Information
Case I: Select m different residue classes from A∪B and choose one y-
value (the equation number) from each of these m residue classes. Now, x of
the m residue classes can be selected from the set A in
n mod l
x
ways and the
l−n mod l
m−x
remaining m−x can be selected from the set B in
ways. Again,
corresponding to each such choice, the first x residue classes would give⌊
l
⌋+1
choices for y (the equation number) and each of the remaining m−x residue
classes would give ⌊
l
⌋ choices for y. Thus, the total number of independent
equations in this case is given by
m
n mod l
x
l−n mod l
m−x
n
l
x
n
l
m−x
+ 1
.
x=0
Case II: Select two y-values from any residue class in A. Then select m−2
other residue classes except [l− 1] and select one y-value from each of those
m−2 residue classes. One can pick one residue class a ∈A in
n mod l
1
ways
⌊
l
⌋+1
2
and subsequently two y-values from a in
ways. Of the remaining m−2
residue classes, x can be selected from A\{a} in
n mod l−1
x
ways and the
l−n mod l−1
m−2−x
remaining m−2−x can be selected from B\{[l−1]} in
ways.
Again, corresponding to each such choice, the first x residue classes would
give ⌊
l
⌋ + 1 choices for y (the equation number) and each of the remaining
m−2−x residue classes would give ⌊
l
⌋ choices for y. Thus, the total number
of independent equations in this case is given by
⌊
l
n mod l
1
⌋+ 1
2
s
m
,
where
m−2
n mod l−1
x
l−n mod l−1
m−2−x
n
l
n
l
x
m−2−x
s
m
=
+ 1
.
x=0
Case III: Select two y-values from any residue class in B\{[l−1]}. Then
select m− 2 other residue classes and select one y-value from each of those
m−2 residue classes. This case is similar to case II, and the total number of
independent equations in this case is given by
⌊
l
l−n mod l−1
1
⌋
s
′
m
,
2
where
m−2
n mod l
x
l−n mod l− 2
m−2−x
n
l
x
n
l
m−2−x
s
′
m
=
+ 1
.
x=0
Adding the counts for the above three cases, we get the result for Part 2.
