Score:0

Get bit i when modulo n

jo flag

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 ?

fgrieu avatar
ng flag
The notation $a≡b\pmod m$ means $b-a$ is a multiple of $m$. Here$\bmod$appears immediately after $($, and there can be only one on the right of a statement like $a≡b≡c≡d\pmod m$, meaning $a≡b\pmod m$ and $b≡c\pmod m$ and $c≡d\pmod m$. That differs from usage in $a\bmod m$ where$\bmod$is an operator appearing immediately after an integer, and it's outcome the uniquely defined integer $x$ with $0\le x<m$ and $x≡a\pmod m$; and in $a^{-1}\bmod m$, which is the uniquely defined integer $x$ with $0\le x<m$ and $a\cdot x\equiv1\pmod m$.
Score:1
ng flag

The question apparently aims to find something like: the bit representation of an integer $a$ when working modulo $m$. This is not well defined. We'll suppose that instead, it's wanted the bit representation of the integer $a\bmod m$.

By definition, the integer $a\bmod m$ is the integer $r$ with $0\le r<m$ and $a-r$ a multiple of $m$. When $a\ge 0$, this $r$ is the remainder of the Euclidean division of dividend $a$ by divisor $m$, yielding integer quotient $q$ and remainder $r$, such that $0\le r<m$ and $a=m\cdot q+r$.

To obtain the representation of a non-negative integer in base $b\ge2$ (with $b=2$ for the bit representation), a standard method is successive Euclidean division by divisor $b$, with first dividend the said non-negative integer, then subsequent dividend(s) the quotient obtained by the previous Euclidean division, repeating until the quotient is $0$. The successive remainders are the desired digits of the representation, with the Least Significant Digit obtained first, and usually written on the right.

So when we want the bit representation of $29\bmod 143$, we first note that $0\le29<143$, thus $29\bmod 143=29$. We no longer need the $143$. We just want the representation of $29$ in base $2$. We write

    29 = 2 * 14 + 1
    14 = 2 *  7 + 0
     7 = 2 *  3 + 1
     3 = 2 *  1 + 1
     1 = 2 *  0 + 1

The remainders obtained are the last integers on each line, and give the binary expression of $29$, that is 11101, with the first obtained on the right.


The bit at index $i$ from the right (starting at index $i=0$, that is the ${i+1}^\text{th}$ bit) of $a\bmod m$ can be obtained as $$\left\lfloor\frac{a\bmod m}{2^i}\right\rfloor\bmod2\tag{1}\label{fgrieueq1}$$

The method in the question instead uses $$\left(a\cdot(2^{-1}\bmod m)^i\bmod m\right)\bmod 2$$ which is defined for odd $m$ only, and when so can be rewritten (with an extension of the$\bmod$notation to cover fractions) $$\left(\frac a{2^i}\bmod m\right)\bmod2$$ which is somewhat similar to \eqref{fgrieueq1}, but does not work reliably beyond $i=0$. For example it fails whenever $i=1$, $m=2^k+1$ with $k>1$, and odd $a$ with $0<a<m$. Since that method comes with no justification, it does not need a refutation beyond a counterexample.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.