X 2^k 2^k mod M X X mod 2^j 1

— = ( ⌊—⌋ + ———— ) × ( ⌊—⌋ + ———— ) × ————

M M M 2^j 2^j 2^{k - j}