2
$\begingroup$

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?

$\endgroup$
13
  • $\begingroup$ Sorry misread, 4.3 better math.ucdenver.edu/graduate/thesis/dreiff.pdf $\endgroup$
    – kelalaka
    May 21 at 10:59
  • $\begingroup$ @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}$. $\endgroup$
    – user93353
    May 21 at 12:29
  • $\begingroup$ mod $q$ is a prime power. $\endgroup$
    – kelalaka
    May 21 at 12:51
  • $\begingroup$ 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$. $\endgroup$
    – j.p.
    May 23 at 8:05
  • $\begingroup$ @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$? $\endgroup$
    – user93353
    May 25 at 0:54
3
+50
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – user93353
    May 26 at 6:04
  • $\begingroup$ 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? $\endgroup$
    – user93353
    May 26 at 6:32
  • $\begingroup$ 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? $\endgroup$
    – user93353
    May 26 at 8:23
  • $\begingroup$ @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). $\endgroup$
    – fgrieu
    May 26 at 8:44
  • $\begingroup$ Ok, I guess I got it finally. Thank you very much!! $\endgroup$
    – user93353
    May 26 at 8:54
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Is there any theory or proof about why for the subgroup, it is $g^{x}=g^{x\bmod p_i^{n_i}}\bmod q$? $\endgroup$
    – user93353
    May 25 at 12:55
  • $\begingroup$ 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) $\endgroup$ May 25 at 14:34
  • $\begingroup$ 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$ $\endgroup$
    – user93353
    May 26 at 8:15
  • $\begingroup$ @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$. $\endgroup$
    – fgrieu
    May 26 at 12:17
  • 1
    $\begingroup$ @fgrieu thanks, you are right, now it's called $p$. $\endgroup$ May 26 at 12:42
1
$\begingroup$

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

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

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

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

  • With [2] 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.

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – user93353
    May 26 at 6:50
  • $\begingroup$ @user93353, I've added one more paragraph in my answer at the end. Let me know if you still have doubts. $\endgroup$
    – SSA
    May 27 at 4:16

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.