Skip to main content
3 of 4
Polish
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

Get bit i when modulo n

Is there a way to recover the bit sequence of a number ( for example 29 = 0b11101 ) by always dividing it by 2 when in mod 143 for example ?

What I mean by that is recover the number bit by bit by multiplying it by the inverse of 2 mod 143 to simulate the /2 division. for example:

${29 \equiv 1 \pmod 2}$
$29\cdot(2^{-1}\bmod143)^1\bmod143=29\cdot72^1\bmod143=86\equiv0\pmod2$
$29\cdot(2^{-1}\bmod143)^2\bmod143=29\cdot72^2\bmod143=43\equiv1\pmod2$
$29\cdot(2^{-1}\bmod143)^3\bmod143=29\cdot72^3\bmod143=93\equiv1\pmod2$
$29\cdot(2^{-1}\bmod143)^4\bmod143=29\cdot72^4\bmod143=118\equiv0\pmod2$
We can see that the sequence I obtain is correct until the fifth bit, which should be $1$. What am I misunderstanding here ?