NIST PRIMES - cryptography

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.

• Ok, three squared is nine, so (in Latex notation) 3^2 = 9. – Vadym Fedyukovych Jan 3 '16 at 9:29
• What is it that you don't understand exactly? – Maarten Bodewes Jan 3 '16 at 13:17
• 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. – fgrieu Jan 3 '16 at 17:43

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$).

• 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) – Mr. Zacarias Satrustegui Jan 3 '16 at 20:08
• 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. – Ruggero Jan 3 '16 at 23:24
• 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. – Mr. Zacarias Satrustegui Jan 4 '16 at 22:26