1

I am a student of computer science and I'm doing cryptography; I need to optimise the way I calculate modulus.

What I'am doing is like this:

$$14 \cdot 16 \equiv 3 \bmod 17$$

$$3 \cdot 16 \equiv 1 \bmod 17$$

My question is if that is true for all numbers.

My goal is to know if this is true so that once I calculate $14 \cdot 16 \equiv 3 \bmod 17$, I can derive the result of $3 \cdot 16 \bmod 17$ without doing all the work.

Also, Is this true for "power modulus"? I mean

if $a^d \equiv b \bmod{n}$, is $b^d \equiv a \bmod n $?

you
  • 13
  • The whole point of $\TeX$ is that you can write $14\times16$ or $14\cdot16$ or $14\otimes16$ or even exotic things far beyond those, and the whole point of writing $14*16$ is that you're restricted to the characters on the keyboard and you want the letter x to be used for other things. To use an asterisk that way in $\TeX$ is to eat mashed potatoes with your fingers when silverware is available and you're at a state dinner at Buckingham Palace. I changed it to $14\cdot16$. – Michael Hardy May 05 '13 at 17:03

4 Answers4

0

If $x\equiv a\cdot b\pmod n$

and $x\cdot b\equiv a\pmod n\implies x\equiv b^{-1}\cdot a\pmod n$

$$\implies a\cdot(b-b^{-1})\equiv0\pmod n$$ which is not true in general.

If $(a,n)=1, $ we need $b-b^{-1}\equiv0\pmod n\iff b^2\equiv1\pmod n$ assuming $(b,m)=1$

If $a^d\equiv b\pmod n$ and $b^d\equiv a\pmod n$

$\implies (a^d)^d\equiv a\pmod n\implies a^{d^2}\equiv a\pmod n$

If $(a,n)=1, a^{d^2-1}\equiv\pmod n$

$\implies ord_na$ needs to divide $d^2-1$ which is not true for all $d$

lab bhattacharjee
  • 274,582
0

In more common notation, what you're saying is this:

"Is it true that $ab \equiv x \pmod n$ implies $xb \equiv a \pmod n$?"

This is not true in general. A counter-example is given by letting $n=4$, and $a=b=2$ and $x=0$. Then $ab \equiv 0 \pmod 4$, but $0 \cdot 2 \not \equiv 2 \pmod 4$.

Fredrik Meyer
  • 20,228
  • ok i got it, is there any known methode to make calculation faster ? – you May 05 '13 at 15:41
  • @you: To calculate the product $ab$ modulo $n$, you could first calculate $ab$, then subtract $n$ until you get a number lower than $n$. This is the modulus. Example: $4 \cdot 3 \pmod 7$ gives $12$. Subtract 7, to get 5, which is lower than $7$, meaning that $4 \cdot 3=5$ modulo 7. – Fredrik Meyer May 05 '13 at 15:45
0

No, this is just a coincidence. Have you tried with other values of $a$, $b$ and $x$ to check whether it holds?

First, this only makes sense if $a \lt n$, from the definition of modulo.

But even in that case, if you replace the value of $x = \left (a \cdot b \right ) \, \mathrm{mod} n$ into the second equality, you would get $\left (x \cdot b \right ) \, \mathrm{mod} n = \left (a \cdot b^{2} \right ) \, \mathrm{mod} n = a$ which only holds if $a$ and $b^2$ are multiplicative inverses modulus $n$, which does not generally happen.

ysmartin
  • 103
  • yes i tried with about 13 examples it all worked but taking in consideration those conterexamples given in the answers above this is not true in general – you May 05 '13 at 15:51
0

You probably need to learn a little bit about finite fields to make much progress. What you have written works because $16\equiv-1 \mod{17}$.

What might help you is to find a primitive root. This enables you to do the equivalent of taking logarithms. So mod 17, 3 is a primitive root and we have:

$1\equiv 3^{16}$; $2\equiv 3^{14}$; $3\equiv 3^{1}$; $4\equiv 3^{12}$; $5\equiv 3^{5}$; $6\equiv 3^{15}$; $7\equiv 3^{11}$; $8\equiv 3^{10}$; $9\equiv 3^{2}$; $10\equiv 3^{3}$; $11\equiv 3^{7}$; $12\equiv 3^{13}$; $13\equiv 3^{4}$; $14\equiv 3^{9}$; $15\equiv 3^{6}$; $16\equiv 3^{8}$

It is then possible to use the powers like logarithms, adding them mod 16. The problem of finding a primitive root in the first place is not straightforward.

Mark Bennet
  • 100,194