The method add mod 2^512

Question

It's add modulo 2^512. Could you explain me why we doing here >>8 and then &oxFF? I know i'm bad in math.

int AddModulo512(int []a, int []b)
{
    int i = 0, t = 0;
    int [] result = new int [a.length];
    for(i = 63; i >= 0; i--)
    {
        t = (a[i]) + (int) (b[i]) + (t >> 8);
        result[i] = (t & 0xFF);    //?
    }
    return result;
}

Answer 1

The mathematical effect of a bitwise shift right (>>) on an integer is to divide by two (truncating any remainder). By shifting right 8 times, you divide by 2^8, or 256.

The bitwise & with 0xFF means that the result will be limited to the first byte, or a range of 0-255.

Not sure why it references modulo 512 when it actually divides by 256.

Answer 2

It looks like you have 64 ints in each array, but your math is modulo 2^512. 512 divided by 64 is 8, so you are only using the least significant 8 bits in each int.

Here, t is used to store an intermediate result that may be more than 8 bits long.

In the first loop, t is 0, so it doesn't figure in the addition in the first statement. There's nothing to carry yet. But the addition may result in a value that needs more than 8 bits to store. So, the second line masks out the least significant 8 bits to store in the current result array. The result is left intact to the next loop.

What does the previous value of t do in the next iteration? It functions as a carry in the addition. Bit-shifting it to the right 8 positions makes any bits beyond 8 in the previous loop's result into a carry into the current position.

Example, with just 2-element arrays, to illustrate the carrying:

[1, 255] + [1, 255]

First loop:

t = 255 + 255 + (0) = 510;     // 1 11111110
result[i] = 510 & 0xFF = 254;  //   11111110

The & 0xFF here takes only the least significant 8 bits. In the analogy with normal math, 9 + 9 = 18, but in an addition problem with many digits, we say "8 carry the 1". The bitmask here performs the same function as extracting the "8" out of 18.

Second loop:

// 1 11111110 >> 8 yields 0 00000001
t = 1 + 1 + (510 >> 8) = 1 + 1 + 1 = 3; // The 1 from above is carried here.
result[i] = 3 & 0xFF = 3;

The >> 8 extracts the possible carry amount. In the analogy with normal math, 9 + 9 = 18, but in an addition problem with many digits, we say "8 carry the 1". The bit shift here performs the same function as extracting the "1" out of 18.

The result is [3, 254].

Notice how any carry leftover from the last iteration (i == 0) is ignored. This implements the modulo 2^512. Any carryover from the last iteration represents 2^512 and is ignored.