Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I wanted to calculate the power of $2$ raised to a number $a$, divided by another number $b$ and then take the modulo $K$ of this quantity.

Meaning, I basically wanted $(2^a/b) \mod K$. Take an example where $a = 4$, $b = 3$ and $K = 98765431$. For this I calculated $3^{-1} \mod K$. Which comes out to be 65843621 *. If this inverse is correct and I now do $(2^4 \cdot 65843621) \mod K$, the answer comes out to be incorrect. I don't know what the problem with my approach is.

*The way I calculated inverse is the following. $3 \cdot x = 98765431 \cdot n + 1$, so I iterated over $n$ to see when $98765431 \cdot n + 1$ is divisible by $3$ and then $x$ is my desired inverse.

share|improve this question
    
What is your result? What do you compare your "incorrect" result to? Where does this number come from? –  Simon Markett Aug 31 '12 at 11:13
1  
I got the same inverse for three that you did. That gives $$2^4\cdot 3^{-1}\equiv 65843626\pmod{K}$$ as the result. Did you get the same? If yes, why do think this would not be correct? You can also calculate this as $$\frac{16}3=5+\frac13\equiv 5+65843621=65843626\pmod{K}.$$ –  Jyrki Lahtonen Aug 31 '12 at 11:13
    
Ok, at the risk of sounding stupid, $2^4 = 16$ and $16/3 = 5$ so I should be getting $5%K = 5$, since $5 < K$. And I did get $65843626$ as the result too. –  n0nChun Aug 31 '12 at 11:17
1  
$\frac {16}{3}=5+3^{-1}$ and $3^{-1}=65843621$ –  Simon Markett Aug 31 '12 at 11:19
3  
Floor doesn't mix with modular arithmetic. Sorry. Integer arithmetic is always precise. –  Jyrki Lahtonen Aug 31 '12 at 11:20

1 Answer 1

up vote 4 down vote accepted

Ok. Comments revealed the source of the confusion. As a general philosophy here I want to mention the following. In the ring $R=\mathbb{Z}_K$ the residue class of $3$ has an inverse, namely the residue class of $65843621$. What this means is that we are replacing "division by $3$" with "multiplication by $65843621$". The result of such a multiplication is another integer (or a residue class modulo $K$ to be precise). What this means is that the result is "accurate". There is no rounding error.

Another way of saying the same thing is that because $3$ is a unit in the ring $R$, every other element of the ring is exactly divisible by $3$.

Another thing that newcomers to modular arithmetic often have problems with is the following. In a ring like $R$ here there is no meaningful$^{*)}$ concept of a size of an element, nor a meaningful way of saying that one element is larger than another. For example, if we assume that $0<1$, then we probably want to accept as a consequence that $1=0+1<1+1=2$, and as another consequence that $0<1<2$, so $0<2$. Continuing in this way we would have to accept as a consequence that $0<K-1$. But here $K-1\equiv -1$, so we end up with $0<-1$. This renders the order relation useless.

The floor function ultimately depends on a sense of "betweenness" (a real number between two consequtive integers), so it, too, becomes meaningless in rings of modular integers.

$^{*)}$ Ok, some meaningful metrics can sometimes be defined, but they follow somewhat different rules than the familiar absolute value.


The problem that OP linked to is about the following. Let $J$ be the all ones $n\times n$ matrix, and let $I$ be the identity matrix with $n$ rows. A calculation by $n$ "cows" is to be carried out $T$ times. A single round of the calculation amounts to multiplying a certain vector with $n$ components, all from the ring $R$, with the matrix $-I+J$ (obviously modulo $K$). Altogether the task at hand is to efficiently compute the matrix power $$ A_T=(-I+J)^T, $$ where $T$ is a large integer.

Here we have the "atomic" rules $I\cdot I$, $I\cdot J=J$ and $J\cdot J=nJ$. As always, when computing large powers in a ring of modular integers, the so called square-and-multiply method works. As a consequence of the above rules we get the formula $$ (aI+bJ)(cI+dJ)=acI+(ad+bc+bdn)J, $$ all the coefficients are to be reduced modulo $K$. That's all we need! By induction we see that for all natural numbers $k$ $$ A_k=f(k)I+g(k)J, $$ and the task at hand is to compute the integers $f(T)$ and $g(T)$. All you need to do is to first compute $A_2$, $A_4$, $A_8$, $\ldots$ by repeated squaring $\log_2(T)$ squarings. Then you need to multiply the appropriate ones together using the above rule. Shouldn't take too long. Edit: Observe that you only need to compute and store the integers $f(k)=(-1)^k$ and $g(k)$ for the relevant integers $k$.

share|improve this answer
    
Thanks kind sir :) –  n0nChun Aug 31 '12 at 11:40
    
@nonChun: I added my take of the cow problem. Didn't double check anything, but it seems to me that this is what is required. –  Jyrki Lahtonen Aug 31 '12 at 11:53
    
I understand this method, and I wanted to use it too, but if n is large say 50000, then the matrix sizes $O(n^2)$ become huge! –  n0nChun Aug 31 '12 at 12:28
    
@nonChun: If I understood correctly, you don't have to store the matrices. Only the numbers $f(k)$ and $g(k)$. You only need the "full" matrix at the end, when computing the cows total output. Also, it seems to me that $f(k)=(-1)^k$, so there is only $g(k)$ to worry about. –  Jyrki Lahtonen Aug 31 '12 at 12:34
    
Hey jyrki, I was able to reduce the problem of finding the coefficients of I and J to finding the exponentiation of a 2x2 matrix and my solution got accepted! Thanks for the pointers :) btw, why did you think of breaking the problem into I - J , and not the original matrix? –  n0nChun Sep 1 '12 at 11:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.