# 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

In the Pohlig-Hellman algorithm, we take a Discrete Log Problem (DLP) in a group & solve it in subgroups $$p_1^{n_1}$$, $$p_2^{n_2}$$, $$p_3^{n_3}$$ etc & then combine it with the Chinese Remainder Theorem (CRT).

The original DLP is $$\bmod p$$ & the order $$p -1 = n = p_1^{n_1} * p_2^{n_2} * p_3^{n_3} ....$$

When we are solving for a subgroup $$p_1^{n_1}$$, we frame number of coefficients of $$x$$ based on the max value $$x$$ can take i.e. $$p_1^{n_1} - 1$$

For example, if we are solving for $$3^4$$, then we frame $$x$$ as

$$x = c_0 + 3c_1 + 3^2c_2 + 3^3c_3$$

$$x$$ has 4 coefficients here ($$c_0$$, $$c_1$$, $$c_2$$ & $$c_3$$) because the max value of x is [$$p_1^{n_1} - 1$$] (because it's $$\bmod p_1^{n_1}$$)

However, when we actually solve for finding the coeffs of $$x$$ for subgroup $$p_1^{n_1}$$, we do the calculations with $$\bmod q$$, instead of $$\bmod p_1^{n_1}$$. Why is that?

For e.g. if we take the example here: When they calculate $$8006^{2025} = 1$$ for subgroup $$2^2$$, this is actually calculated as $$8006^{2025} \bmod p$$ rather than $$\bmod p_1^{n_1}$$. It's the same in all the calculations. Why is this? Shouldn't it be done $$\bmod p_1^{n_1}$$

When we are finding $$x = x_1 \bmod {p_i}^{n_i}$$, we are doing calculations $$\bmod q$$ instead of doing them $$\bmod {p_i}^{n_i}$$.

EDIT: Or an alternate question could be this - the operations of the subgroup is always going to be $$\bmod p$$ rather than $$\bmod {p_i}^{n_i}$$. Considering that, then 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$$?

EDIT2: Based on various answers, I have boiled down my question to one line

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

Is there any theory explaining this?

• @kelalaka - I couldn't find anything in 4.3 which talks about why the coeffs of x for $\bmod {p_i}^{n_i}$. are calculated $\bmod q$ instead of calculating them $\bmod {p_i}^{n_i}$. May 21 at 12:29
• mod $q$ is a prime power. May 21 at 12:51
• Taking the example you linked, you have a prime $p=8101$ and $q=p-1=8100$ a product of powers of small primes. $q$ is the order of the multiplicative group mod $p$. The group operation is multiplication mod $p$, and if you want to find the order of an element in this group, you have to use therefore exponentiation mod $p$. Numbers you multiply or take exponents of, you have to reduce modulo $p$, only their exponents you can reduce mod $q$.
– j.p.
May 23 at 8:05
• @j.p. - The operations of the subgroup is always going to be $\mod p$ rather than $\mod {p_i}^{n_i}$. Considering that, then why are the 3 congruence equations we get for the 3 subgroups also not $\mod p$. Why are they $\mod 4$, $\mod 81$ & $\mod 25$? May 25 at 0:54

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
• 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 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. 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.

• No, and the question's issue stems from that confusion. - sorry - this was actually a mistake in writing down my thoughts. I know that the original DLP is $\bmod p$ & order of the group is $q$. I will edit the Q right away, Thank you for pointing this out May 26 at 6:04
• If my question had to shorted to one line, it would be this line from your answer - "Calculations involving exponents are modulo the subgroup order" - why is this? What is the theory behind this? May 26 at 6:32
• Re your edited answer - here the subgroup is of order $p_i^{n_i}$ as you have written in one of the other paras. So shouldn't we be reducing the exponents modulo $p_i^{n_i}$ & not $p_i$ as being done in the solution? May 26 at 8:23
• @user93353: I read this solution as deriving it's $x_2$, $x_3$ and $x_5$ modulo $4$, $81$ and $25$, that is modulo ${p_i}^{n_i}$, not $p_i$; then joining them with the CRT modulo $n=5\cdot81\cdot25$. It's only in the determination of the individual $x_{p_i}$ that arithmetic modulo $p_i$ is used. Specifically, each $x_{p_i}$ is split into $n_i$ components each in $[0,p_i)$, found individually. That's similar to the loop of step 3 of Wikipedia's Pohlig-Hellman for group of prime-power order (link in the question).
– fgrieu
May 26 at 8:44
• Ok, I guess I got it finally. Thank you very much!! May 26 at 8:54

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

• Is there any theory or proof about why for the subgroup, it is $g^{x}=g^{x\bmod p_i^{n_i}}\bmod q$? May 25 at 12:55
• Actually, the definition of the order of a (sub)group says that raising an element of that (sub)group to its order gives you 1 en.wikipedia.org/wiki/Order_(group_theory) For special cases, there is also the following theorems: en.wikipedia.org/wiki/Fermat%27s_little_theorem and en.wikipedia.org/wiki/Euler%27s_theorem (for Pohlig-Hellman we use the fact that $\varphi(q)$ has small factors) May 25 at 14:34
• How do Fermat's Little Theorem or the others show that $g^{x}=g^{x\bmod p_i}\bmod p_i^{n_i}$? Fermat's theorem is $g^{p-1}=1\bmod p$ May 26 at 8:15
• @user93353: see new note 4 in my answer for relation between $\underbrace{x*x\ldots x*x}_{r\text{ terms}}=x^r=1$ where $r$ is the group order and Fermat's little theorem. $g^x\equiv g^{x\bmod p_i}\pmod{{p_i}^{n_i}}$ (with the notation fixed) does not hold, counterexample $p_i=3$, $n_i=2$, $g=2$, $x=4$. We have $2^4\bmod9=7$ when $2^1\bmod9=2$.
– fgrieu
May 26 at 12:17
• @fgrieu thanks, you are right, now it's called $p$. May 26 at 12:42

as we know that DLP is finding x in : $${y \equiv g^x (mod p)}$$, we use pohlig-hellman when order of group G is B smooth, when B is relatively small. We assume that g is a generator. In real cases when order of g is quite large, we use one of the subgroup generated by g. for simplicity we assume g is a generator. so solution for x is available.

• from group theory value of x lies in {1,...,p-1} and this cyclic group(field) is having , it as many cyclic subgroup and if it has subgroup, order of subgroup divides order of Group, (Lagrange's Theorem)

• Now we're trying to find the value of $${y \in G}$$ with base g. i.e, y=gx.

• rather than finding by normal process, we factor p-1 and try to find out if x contains in the subgroup generated by that factor.

• for ex in case of $${6^x \equiv 8 (mod 13)}$$, we have $${p-1=12 = 2^2 \times 3}$$

• Here $${x \equiv x_0+2x_1}$$, and algorithm is to find out if smallest x lies in subgroup generated by 4 as we want to solve it by CRT.

• subgroup generated by 4 is {4,3,12,9,10,1} and 3 is {3,9,1}

• we can see that 3 is the common factor which gives us the answer.

• when we are finding $${g^x}$$ we should obviously work mod p. But when we write the x with base as one of it's factor which is 4 or 3 and apply CRT, we only work to the mod 4 or mod 3 here. i.e, $${x \equiv x_0+x_1q+...+x_{r-1}q^{r-1} (mod q^r)}$$, where q can be {3,4}

• From basic Group Theory we know that there is a Group isomorphism $${\phi(G) \rightarrow C_{q_1^{e_1}} \times...\times C_{q_r^{e_r}}}$$ where $${C_{q^{e}} }$$ is a cyclic group of prime power order $${q^e}$$

• The projection of $${\phi}$$ to the component $${C_{q^{e}} }$$ is given by

• $${\phi_q :G \rightarrow C_{q^{e}} , f \mapsto f^{N/q^e} }$$ here N=p-1.

• Now the map $${\phi_q}$$ is a group homomorphism so if we have $${y = gx}$$ in G then we will have $${\phi_q(y) = \phi_q(g)^x}$$ in $${C_{q^e}}$$ . But the discrete logarithm in $${C_{q^e}}$$ is only determined modulo $${q^e}$$. So if we could solve the discrete logarithm problem in $${C_{q^e}}$$ , then we would determine x modulo $${q^e}$$.

• Doing this for all primes q dividing N would allow us to solve for x using the Chinese Remainder Theorem.

• In summary suppose we had some oracle O(g, y, q, e) which for $${g,y \in C_{q^e}}$$ will output the discrete logarithm of y with respect to g.

• Looking at other's comments, it is better to revisit CRT.

• when we have two relative prime m,n, we have

•  $${f: Z_{mn} \mapsto Z_m \times Z_n}$$ defined by $${f(x)=(x(modm), x(modn)}$$is a ring isomorphism.

•  $${\phi(mn)=\phi(m) \phi(n)}$$

•  $${f^{-1}(a,b)= an(n^{-1} (mod m)) + bm(m^{-1}(mod n)) (mod mn) ) }$$

• With  we can see that final answer is always reduced to (mod mn), due to the closure property of Group.

• We know that for any x, (x mod mn) mod m = x mod m, CRT can be used to compute exponentiation in $${Z_{mn}}$$ faster. Since $${Z_{mn}}$$ is isomorphic to the $${Z_m \times Z_n}$$ product structure, instead of computing $${a^e mod mn}$$, we can compute $${a^e mod m}$$ and $${a^e mod n}$$ which gives $${a^e}$$ in $${Z_m \times Z_n}$$. Then we can use the Chinese Remainder Theorem to recover $${a^e mod mn}$$.

• Since the complexity of exponentiation is cubic in the size of the modulus, assuming that m and n are half of the size of mn, exponentiation in $${Z_m}$$ costs 1/8 of the exponentiation price in $${Z_{mn}}$$, as well as exponentiation in $${Z_n}$$. Since applying the Chinese Remainder Theorem is quadratic, we speed up the exponentiation by a factor of 4.

• But when we write the x with base as one of it's factor which is 4 or 3 and apply CRT, we only work to the mod 4 or mod 3 here. i.e, ${x \equiv x_0+x_1q+...+x_{r-1}q^{r-1} (mod q^r)}$, where q can be {3,4} - why? Why do we write x based on q rather than based on p? while we are calculating the multiplications modulo p, why is q used for x? Is there any theory explaining this - that is the crux of my question May 26 at 6:50
• @user93353, I've added one more paragraph in my answer at the end. Let me know if you still have doubts.
– SSA
May 27 at 4:16