# Multiplication over $F_{2^{31}-1}$ by power of $2$

I'm reading the source code of a stream cypher (zuc): I cannot understand properly why they define the multiplication by power of 2 in this way:

#define MulByPow2(x, k) (   (   ((x) << k)|((x) >> (31 - k))      & 0x7FFFFFFF)


In the example $x$ is the first term of the product and $k$ is the power of $2$. for who don't understand c here's the translation: * ((x) << k) is the binary left shifting operation by k position. This correspond to the usual multiplication by power of 2. * | is the bitwise OR operator * (x) >> (31 - k) is the opopsite operation of <<. * & 0x7FFFFFFF i think this play the role of mod(2^31-1)

I don't get the meaning of "|((x) >> (31 - k)) " in the multiplication.

Thanks for help. :)

-

If you calculate in 64 bits, then $x\ll k$ is $2^kx$. Write this as two 32 bit words as $h\cdot 2^{32}+ (s\cdot 2^{31}+l)$ with high word $h$, low (unsigned) word $l$ und msb $s$. Then $s\equiv 1\pmod{2^{31}-1}$ and $h\cdot 2^{32}\equiv 2h\pmod {2^{31}-1}$. Note that $2h+s$ can be obtained directly by calculating $x\gg (31-k)$. Normally, one should use $+$ instead of $|$, but fortunately the two expressions are always bit-disjoint, provided $x<2^{31}$.
By the way, the macro may be problematic if an expression is fed into $k$. To play safe, each $k$ schould be surrounded by parentheses.