1
$\begingroup$

I am stuck on a problem involving numbers being reduced by two different moduli. Assume I have the following two numbers $g_1$ and $g_2$:

$g_1 = (2^{1024} \mod(p)) \mod(q)\\ g_2 = (2^{1234} \mod(p)) \mod(q)$

Now if I multiply them and reduce by $q$:

$g_1 * g_2 \mod(q) = ((2^{1024} \mod(p)) * (2^{1234} \mod(p))) \mod(q)$

So far it's quite logical, however now it gets weird. From the above equation I would have deduced:

$g_1 * g_2 \mod(q) = (2^{1024 + 1234} \mod(p)) \mod(q)$

However, this equality does not hold. Can somebody explain to me why this is? I thought I got the modular arithmetic laws down quite alright, but apparently not...

edit: Just some additional information if it is relevant: $p$ and $q$ are primes and $p = 2*q + 1$

$\endgroup$

1 Answer 1

1
$\begingroup$

The problem comes from the fact that you (supposedly) don't write (mod $p$) to signify that you are doing arithmetic modulo $p$, but that you want to compute the rest in the euclidean division by $p$ (which is $<p$).

That is why operations used when doing modular arithmetic don't work here, you have to always explicit euclidean divisions.

Nesting modular arithmetic like you are trying to do is not really defined, and if it was, in your case there would be only one element ($0$), because any number can be written as $ap+bq$ when $p$ and $q$ are coprimes.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .