1
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ – lulu Jun 9 '17 at 14:56
  • $\begingroup$ 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$. $\endgroup$ – Rikeijin Jun 9 '17 at 14:57
  • $\begingroup$ 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$. $\endgroup$ – lulu Jun 9 '17 at 14:58
  • 1
    $\begingroup$ 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$. $\endgroup$ – lulu Jun 9 '17 at 15:11
  • 1
    $\begingroup$ $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$. $\endgroup$ – lulu Jun 9 '17 at 15:27
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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