Skip to main content
1 of 4

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 \textbf{1}(mod(2))$

$29* inv(2,143) \equiv 29*72 mod(143)\equiv86\equiv\textbf{0}(mod2)$

$29* inv(2,143) \equiv 29*72^2 mod(143)\equiv43\equiv\textbf{1}(mod2)$

$29* inv(2,143) \equiv 29*72^3 mod(143)\equiv93\equiv\textbf{1}(mod2)$

$29* inv(2,143) \equiv 29*72^4 mod(143)\equiv118\equiv\textbf{0}(mod2)$

we can see that the sequence I obtain is correct until the fifth bit, which should be 1. What am I misunderstanding here ?