[Crypto] Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp

Solution 1:

The question's example asks finding the solutions $x$ of equation $a^x\equiv b\pmod p$ given $p$, $a$, $b$, with $p=8101$, $a=6$, $b=7531$. It's stated $a$ is a generator of $\mathbb Z_{8101}$, but it's meant $\mathbb Z_{8101}^*$, which is the multiplicative group modulo $p$. The $^*$ (or $^\times$) means we use the multiplicative law of the ring of integers modulo $p$, or equivalently that we form the group by keeping the elements of the ring that are invertible, as mandated by a group axiom. In particular, that implies we exclude $0$, and any $c$ with $\gcd(c,p)\ne1$.

That Discrete Logarithm Problem is modulo prime $p$, a simplifying special case¹. The aforementioned group $\mathbb Z_p^*$ is thus² cyclic. It has order $n=p-1$, that is $n$ elements which we can designate by their integer representative in range $[1,n]$. The order of any element $c$ of that group, defined as the smallest integer $\ell>0$ with $c^\ell\equiv1\pmod p$ thus divides the order $n$ of the group. We are told that $a$ is a generator, which means the order of $a$ is $n$, and we can check this³.

We are now in the situation where we can apply the general Pohlig-Hellman algorithm as stated in Wikipedia, with their $\mathbb G$ of order $n$ our $\mathbb Z_p^*$ of order $n=p-1$, their $g$, $h$ and $e_i$ our $a$, $b$, and $n_i$ :

  • The first step in that algorithm is factoring $n$ into $n=\prod{p_i}^{n_i}$, that is $8100=2^2\cdot3^4\cdot5^2$. For each $i$ we'll form a subgroup of $\mathbb Z_p^*$ where we solve a sub-problem.
  • Each of this sub-problems is $\left(a^{n/({p_i}^{n_i})}\right)^{x_{p_i}}\equiv b^{n/({p_i}^{n_i})}\pmod p$ (per the linked example's notation, which uses $x_2$, $x_3$, $x_5$ where Wikipedia uses $x_1$, $x_2$, $x_3$). Each of this sub-problem is in the (cyclic) subgroup of $\mathbb Z_p^*$ generated by $a^{n/({p_i}^{n_i})}\bmod p$, of order ${p_i}^{n_i}$. We solve each separately using Pohlig-Hellman for group of prime-power order. Calculations involving elements of a subgroup are within the main group, thus in $\mathbb Z_p^*$, thus modulo $p$. Calculations involving exponents (in particular, the solution $x_{p_i}$ ) are modulo the subgroup order, that is ${p_i}^{n_i}$.
  • Then we join the solutions $x_{p_i}$ in a Chinese Remainder Theorem step, where the coprime moduli are the ${p_i}^{n_i}$, which product is our $n=p-1$.

In summary, all calculations involving a multiplication by $a$ or $b$ are modulo $p$, so as to be in the group $\mathbb Z_p^*$. Same for raising $a$ or $b$ (or a product of powers thereof) to some power. Only operations involving an exponent (that is the integer defining to which power we raise such combination of $a$ or/and $b$) is made modulo something other than $p$: the group order or a subgroup order, thus modulo $n$ where $n=p-1$, or modulo some divisor of $n$.

why are the 3 congruence equations we get for the 3 subgroups also not $\bmod p$. Why are they $\bmod 4$, $\bmod 81$ & $\bmod 25$?

Because they are congruence modulo the orders ${p_i}^{n_i}$ of the 3 subgroups of $\mathbb Z_p^*$ generated by the 3 elements $a^{n/({p_i}^{n_i})}\bmod p$. Relations (multiplicative) in these subgroups of $\mathbb Z_p^*$ would be modulo $p$.

While multiplication in the subgroup is being done modulo $p$, why are exponents in the subgroup expanded modulo $p_i$?

For any finite group $(\mathbb G,*)$ of order $r$ (that is, with $r$ elements), for any $x\in\mathbb G$, it holds⁴ $\underbrace{x*x\ldots x*x}_{r\text{ terms}}=x^r=1$, where $1$ is the neutral of the group.

Therefore, for any integers $s$ and $t$, $x^s*x^t=x^{s\cdot t\bmod r}$, where $s\cdot t\bmod r$ is computed over integers regardless of the group's nature and it's group law $*$. That's why exponents are computed modulo the group order.

When we consider a subgroup of $\mathbb Z_p^*$ (thus where computations are modulo $p$) that has order $p_i$ (as in this sub-question) or ${p_i}^{n_i}$ (as in the overall problem), that subgroup is a group of order $r=p_i$ or $r={p_i}^{n_i}$. When working in that subgroup, we can thus reduce exponents modulo $r$.

Notice that the order $r$ of a finite subgroup always divides the main group's order, here $n=p-1$.

solve it in subgroups ${p_1}^{n_1}$, ${p_2}^{n_2}$, ${p_3}^{n_3}$ etc

It's important to be precise here: we are solving an equation $a^x\equiv b\pmod p$ in a subgroup of order ${p_i}^{n_i}$ of the main group $\mathbb Z_p^*$. Therefore, equations related to exponents are stated (and solved) in the ring of integers modulo ${p_i}^{n_i}$ noted $\mathbb Z_{{p_i}^{n_i}}$ ; while equations related to exponents in the main group are in the ring of integers modulo $n=p-1$ noted $\mathbb Z_n$.

Picky note on notation:

For integer $m>0$, the notation $u\equiv v\pmod m$ is read as “$u$ (is) congruent to $v$ modulo $m$” or sometime “$u$ equal(s) $v$ ... modulo $m$”, as a shortcut for “(the representative of) $u$ equals (the representative of) $v$ in the ring of integers modulo $m$”. That notation means (equivalently):

  • that $m$ divides $u-v$
  • that $u-v$ is a multiple of $m$
  • that the remainder of the Euclidean division of $\left\lvert u-v\right\rvert$ by $m$ is $0$
  • that exists integer $w$ with $u=(w\cdot m)+v$

The notations $u=v\bmod m$ and $v\bmod m=u$, in which $\bmod$ is an operator combining two integers into an integer, are respectively read as “$u$ equal(s) ... $v$ modulo $m$” and “$v$ modulo $m$ equal(s) $u$”. Both mean (equivalently):

  • that $u\equiv v\pmod m$ as defined above, and $0\le u<m$
  • that $u$ is
    • the remainder in the Euclidean division of $v$ by $m$, when $v\ge0$
    • $m-1-((-u-1)\bmod m)$, otherwise

When hearing ”$u$ equals $v$ modulo $m$” (without a discernible pause), or seeing $u=v\mod m$ (with extra spacing on the left of $\bmod$ due to the use of \mod rather than \pmod or \bmod), there can be an ambiguity about if $0\le u<m$ is meant, and that maters in some crypto applications. When we write $c=m^e\bmod n$ in RSA, we positively assert $0\le c<n$. For consistency, we want to write $\forall k\in\mathbb N,\;2^k\equiv2^{k\bmod 42}\pmod{43}$, rather than $\forall k\in\mathbb N,\;2^k=2^{k\bmod 42}\bmod 43$, which has counterexample $k=6$.

¹ When solving for $a^x\equiv b\pmod m$ in the most general case of a composite $m$, the outer step could be to factor $m$ as $m=\prod{m_j}^{k_j}$ with $m_j$ prime; then solve each of the problems $a^{x_j}\equiv b\pmod{m_j^{k_j}}$; then join the solutions. Here there's a single $m_1$ (one special case), and $k_1=1$ (another special case).

² The converse is not true, see this.

³ The standard technique is ensuring $a^{n/p_i}\not\equiv1\pmod p$ for each prime $p_i$ dividing $n$. Here $n=p-1=8100=2^2\cdot3^4\cdot5^2$ thus $p_i\in\{2,3,5\}$, and neither of $6^{4050}\bmod8101$ , $6^{2700}\bmod8101$ , $6^{1620}\bmod8101$ is $1$, thus $a=6$ indeed is a generator.

⁴ Fermat's little theorem, in the form $a^{p-1}\equiv1\pmod p$ for prime $p$ and $a$ not divisible by $p$, is precisely a restriction of that statement with $(\mathbb G,*)$ the group $\mathbb Z_p^*$ with $p$ is prime.

Solution 2:

The group we are considering is $\mathbb{Z}_p^\times$, so every operation in that group (that includes operations in subgroups of that group) follow the same rule, namely computation mod $p$.

When we look at a subgroup with small order $p_i^{n_i}$, all computations are still in the original group $\mathbb{Z}_p^\times$. But then we know that for each element $g$ in that subgroup, we have $g^{x}=g^{x\bmod p_i^{n_i}}\bmod p$. In other words, operations in the group must abide by the given group structure and are conducted modulo $p$. But, in the exponent, you can now compute modulo $p_i^{n_i}$ (instead of $p-1$).

Tags:

Recent Posts