-1
$\begingroup$

I have a problem, If I have $p = \text{P-192} = 2^{192} - 2^{64} - 1$ with the base $2^{64}$ so, $2^{192} \equiv 2^{64} + 1 \pmod p$ the same that $(p=\text{P-192})$ or $2^{256} \equiv 2^{128} + 2^{64} \pmod p$

or

$2^{320} \equiv 2^{128} + 2^{64} +1 \pmod p$

Could you help me, please? I don't understand for example like $2^{256} \equiv 2^{128} + 2^{64} \pmod p$

Thank you so much.

$\endgroup$
  • $\begingroup$ Ok, three squared is nine, so (in Latex notation) 3^2 = 9. $\endgroup$ – Vadym Fedyukovych Jan 3 '16 at 9:29
  • 3
    $\begingroup$ What is it that you don't understand exactly? $\endgroup$ – Maarten Bodewes Jan 3 '16 at 13:17
  • 1
    $\begingroup$ The notation $a\equiv b\pmod p$ simply means that $a-b$ is a multiple of $p$. Thus for $p =\text{P-192}=2^{192}-2^{64}-1$, it holds that $2^{192}\equiv2^{64}+1\pmod p$ simply because $2^{192}-(2^{64}+1)$ is that $p$, thus is a multiple of that $p$. To prove that $2^{256}\equiv2^{128}+2^{64}\pmod p$ or $2^{320}\equiv2^{128}+2^{64}+1\pmod p$ you just need to apply that definition, and do simple algebra. $\endgroup$ – fgrieu Jan 3 '16 at 17:43
2
$\begingroup$

I'm not sure I got your question right, but it seems to me you are asking about modular reductions modulo $p=2^{192}-2^{64}-1$.

If so, this answer from poncho, that I should have searched before writing this answer, might interests you.

Note that in the following the choice of the base doesn't matter.

If we have to reduce $2^{192} \mod{p}$ you can just subtract the modulus $p$ and obtain as result $2^{192} - (2^{192} - 2^{64}-1) = 2^{64} + 1$.

Now consider to split the number in two parts, an high part and a low part. The separation line being $2^{192}$, so that you can write your numbers to be reduced as $a*2^{192}+b$.

Now, to perform reduction you can use the fact that: $a*2^{192}+b \mod p = b+a*(2^{64} + 1) \mod p$ and iteratively use this fact if the result is bigger than $2^{192}-1$.

For example, let's take $2^{256}$, which we rewrite as $2^{64}*2^{192}$ and now $2^{64}*2^{192} \mod p = 2^{64}*(2^{64} + 1) = 2^{128}+2^{64}$.

The same applies to $2^320$, rewritten as $2^{128}*2^{192}$ and now $2^{128}*2^{192} \mod p = 2^{128}*(2^{64} + 1) = 2^{192}+2^{128}$ which needs to be reduced again, since it's bigger than $p$, so $2^{192}+2^{128} \mod p = 2^{128}+2^{64}+1$.

Note that further care should be taken to perform reductions of number greater than $p$ but smaller than $2^{192}$. For example the number $\sum^{191}_{i=0}{2^i}$ is greater than $p$ but smaller than $2^{192}$ and can't be correctly reduced by the above trick (unless you rewrite it as $2^{192} -1$).

$\endgroup$
  • $\begingroup$ Thanks you very much, I understood all, but Why do you start by 2^192 instead of 2^128? (I say you that because the base is 2^64 and the nearest above of 2^64 is 2^128) $\endgroup$ – Mr. Zacarias Satrustegui Jan 3 '16 at 20:08
  • $\begingroup$ If you mean why do I put the separation line at $2^{192}$ that's due to the prime. If you mean why my first example is for $2^{192}$, it's just because that was in your question. $\endgroup$ – Ruggero Jan 3 '16 at 23:24
  • $\begingroup$ mmm no, exactly, If I have : c = C5*2^320 + C4*2^256 + C3*2^192 + C2*2^128 + C1*2^64 + C0 with base-2^64 My question is, Why dou you start by 2^192 instead 2^128 or 2^64 because 2^128 or 2^64 is the nearest above of base-2^64. and Thank you very very much. $\endgroup$ – Mr. Zacarias Satrustegui Jan 4 '16 at 22:26

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.