Skip to main content
Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

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:
$\begin{array}{} &29\bmod143=&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\\ \end{array}$

${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 We can see that the sequence I obtain is correct until the fifth bit, which should be $1$. What am I misunderstanding here ?

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 ?

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:
$\begin{array}{} &29\bmod143=&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\\ \end{array}$

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

Polish
Source Link
fgrieu
  • 145.6k
  • 12
  • 319
  • 611

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* (2^{-1}$ mod $143)^1$ mod $143$ $ \equiv 29*72^1$ mod $143 =86\equiv\textbf{0}$ (mod $2$)

$29* (2^{-1}$ mod $143)^2$ mod $143$ $ \equiv 29*72^2$ mod $143 =43\equiv\textbf{1}$ (mod $2$)

$29* (2^{-1}$ mod $143)^3$ mod $143$ $ \equiv 29*72^3$ mod $143 =93\equiv\textbf{1}$ (mod $2$)

$29* (2^{-1}$ mod $143)^4$ mod $143$ $ \equiv 29*72^4$ mod $143 =118\equiv\textbf{0}$ (mod $2$)

we${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$1$. What am I misunderstanding here ?

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* (2^{-1}$ mod $143)^1$ mod $143$ $ \equiv 29*72^1$ mod $143 =86\equiv\textbf{0}$ (mod $2$)

$29* (2^{-1}$ mod $143)^2$ mod $143$ $ \equiv 29*72^2$ mod $143 =43\equiv\textbf{1}$ (mod $2$)

$29* (2^{-1}$ mod $143)^3$ mod $143$ $ \equiv 29*72^3$ mod $143 =93\equiv\textbf{1}$ (mod $2$)

$29* (2^{-1}$ mod $143)^4$ mod $143$ $ \equiv 29*72^4$ mod $143 =118\equiv\textbf{0}$ (mod $2$)

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

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 ?

Thank you fgrieu for notation correction.
Source Link

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

$29* inv(2,143) \equiv 29*72 mod(143)\equiv86\equiv\textbf{0}(mod2)$$29* (2^{-1}$ mod $143)^1$ mod $143$ $ \equiv 29*72^1$ mod $143 =86\equiv\textbf{0}$ (mod $2$)

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

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

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

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

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 ?

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* (2^{-1}$ mod $143)^1$ mod $143$ $ \equiv 29*72^1$ mod $143 =86\equiv\textbf{0}$ (mod $2$)

$29* (2^{-1}$ mod $143)^2$ mod $143$ $ \equiv 29*72^2$ mod $143 =43\equiv\textbf{1}$ (mod $2$)

$29* (2^{-1}$ mod $143)^3$ mod $143$ $ \equiv 29*72^3$ mod $143 =93\equiv\textbf{1}$ (mod $2$)

$29* (2^{-1}$ mod $143)^4$ mod $143$ $ \equiv 29*72^4$ mod $143 =118\equiv\textbf{0}$ (mod $2$)

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

Source Link
Loading