High/Low Order Bits and Hints
The goal is that when given an arbitrary element and another small element , we would like to be able to recover the higher order bits of without needing to store . We therefore define algorithms that take and produce a 1-bit hint that allows one to compute the higher order bits of just using and . This hint is essentially the "carry" caused by in the addition.
There are two different ways in which we will break up elements in into their "high-order" bits and "low-order" bits.
The first algorithm, , is the straightforward bit-wise way to break up an element where and
For an even (resp. odd) positive integer , we define to be the unique element in the range (resp. such that
:
Notice that if we choose the representatives of to be non-negative integers between 0 and , then the distance (modulo ) between any two and is usually , except for the border case. In particular, the distance modulo between and 0 could be very small. This is problematic in the case that we would like to produce a 1-bit hint, as adding a small number to can actually cause the high-order bits of to change by more than 1 .
We avoid having the high-order bits change by more than 1 with a simple tweak. We select an that is a divisor of and write in the same way as before. For the sake of simplicity, we assume that is even (which is possible, as is odd). The possible 's are now . Note that the distance between and 0 is 1, and so we remove from the set of possible 's, and simply round the corresponding 's to 0 . Because and 0 differ by 1 , all this does is possibly increase the magnitude of the remainder by 1. This procedure is called .
:
:
:
Using this procedure as a sub-routine, we can define the and routines that produce a hint and, respectively, use the hint to recover the high-order bits of the sum.
:
:
Lemma 1: Let with . Then
. The output of is an integer such that and another integer such that . Because , the integer either stays the same as or becomes modulo More precisely, if , then
This implies that is either or . If , then we have In this case, we have or .
The routine checks whether and outputs 0 if this is so, and 1 if The routine uses the "hint" to either output (if ) or, depending on whether or not, output either or .
Lemma 2. Let and let If , then else
. Let . We go through all three cases of the procedure.
Case : We have and
which by definition has absolute value at most .
Case 2 ( and : We have for or 1 . Thus
After centered reduction modulo , the latter has magnitude .
Case 3 ( and : We have for or 1 . Thus
After centered reduction modulo , the latter quantity has magnitude .
Lemma 3. Let and If , then
. Note that and is equal to Since , we have that .
Lemma 4. If and , then
. We prove the lemma for integers, rather than vectors of polynomials, since the function works independently on each coefficient.
If , then where . Then and . Therefore , and thus
Lemma 5. Let , and . Then
. We first prove the forward direction. By the same proof as in Lemma 4 , since , we know that . We can therefore write . Since , we know that
To prove the other direction, write
and therefore .