# Change order of modulo operation

Given integer $p$ and $q$, where $gcd(p,q)=1$

and integer $r$ with realation: $$(x\; \text{mod}\,p)\;\text{mod}\,q=r$$ How to find the solutions of $s$, which satisfy the relation below ? $$(x\; \text{mod}\,q)\;\text{mod}\,p=s$$

This problem arise from the digital signature algortihm. If someone make a mistake on modulo order when calculate $r\equiv (\alpha^{K_E} \text{mod}\,p)\;\text{mod}\, q\$, I want to know what is the effect on the result. I can find form the equations above, I can get $$x= p\times a+q\times b+r$$ and $$x= p\times a'+q \times b'+s$$ the two equation give me $$-r-s=p \times (a-a')+q\times(b-b')$$ It is a Diophantine equation with solution, but I stuck when to determine the range of the solution. For the same $x$ how to find the possible values of $s$? Thanks to amWhy for reminding me to add the details.

• If you are given $x$ then $s$ is specified (and you don't need to be given $r$). If you are only given $r$ then it is not. – lulu Jun 9 '17 at 14:56
• Thanks for correction, only r is given. I know $s$ is not uniquely determined, but I want to make a systemic way to find multiple $s$. – Rikeijin Jun 9 '17 at 14:57
• That's what I figured. But $r$ does not suffice. To take a random example, let $p=5, q=8, r=2$. Then $x=2$ gives the correct $r$ and yields $s=2$. But $x=17$ also gives the correct $r$ and it yields $s=1$. – lulu Jun 9 '17 at 14:58
• I believe you can get any value for $s$. Take my example, with $p=5,q=8,r=2$. Then let $x\in \{2,7,12,17,22,27,32,37\}$ It is easy to see that we get $s\in \{2,7,4,1,6,3,0,5\}$ which is every possible $s$. – lulu Jun 9 '17 at 15:11
• $x$ is not determined by $r$ so it makes no sense to talk about "the same $x$". My example shows (I think) that for a specific $p,q,r$ we can get all possible $s$. – lulu Jun 9 '17 at 15:27

I prefer to use $\%$ for the mod operator, and reserve mod for finite fields.

Suppose that $p<q$, $\gcd(p,q)=1$ and that we have $(x\%p)\%q=r$.

Obviously $x\%p<p<q$, so then $x\%p=r$.
So $x=r+b*p$ satisfies the requirements for any value of $b$ we like.

From $\gcd(p,q)=1$ we know that there are positive $m,n$ such that $mp-nq=1$. Let's choose our value of $b$ to be a multiple of $m$, i.e. $b=km$ where we are still free to choose $k$.

Now we have: $x\%q = (r+bp)\%q = (r+kmp)\%q = (r+k(1+nq)))\%q = (r+k+knq)\%q = (r+k)\%q$

As we are free to choose $k$, we can make $x\%q$ become any value we like (between $0$ and $q-1$). Therefore $x\%q\%p$ can also take on any value we like (between $0$ and $p-1<q-1$).

In other words, I have shown that for any pair of values $r,s$ we can find a value of $x$ that works.