# Tag Info

9

Does the factorization of N somehow help me? It sure does. I think I could compute the logarithm modulo each prime and then combine it, but do not know how exactly. Seems similar like problems for Chinese remainder theorem but I cannot find the way how to do it. You're real close; you do recombine them using the Chinese Remainder Theorem; however the ...

6

Is there any better algorithm ? Actually, your second algorithm (select a small set of primes $\{ 2, q_1, q_2, ..., q_n \}$ and check if $\ 2q_1 q_2 ... q_n + 1$ is prime) is quite efficient. You say that it's trial and error (and it is), however it's about as efficient as the traditional algorithms we use to search for primes; if you're looking for an $q$ ...

5

Here is an example curve with smooth order $E/\mathbb{F}_p:y^2=x^3+ax+b$, generated with Magma. \begin{align*} p &= 2^{31}-1 \\ a &= 1456400922 \\ b &= 2005615003 \\ n &= 2^5\cdot 3^7 \cdot 5\cdot 17\cdot 19^2. \end{align*} I'd expect that if you are able to run PH, you should also be able to generate some test vectors yourself. The code is ...

4

Generally speaking, this algorithm uses the Chinese Remainder Theorem to split up the group order, and then uses a Babystep-Giantstep algorithm for each prime factor potency of the group order. If the group order is smooth (all prime factors are small, s.t. all BS-GS algorithms can be done efficiently), this can be done very efficiently. However, the ...

3

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

3

Choice of public modulus $p$ Using for $p$ a large safe prime (that is, a prime $p=2q+1$ with $q$ also prime) is the way to go for the Pohlig-Hellman cipher, because that simplifies the choice of encryption key $k$: a random odd $k$ in range $[1,q-2]$ will do, because that ensures that $\gcd(k,p-1)=1$ (the condition for validity of an exponent in the Pohlig-...

3

Note that $\alpha$ is a primitive element in $GF(p)$ and $\gamma_i$ is a generator of a subgroup $G_i\subseteq GF(p)$ with order $p_i$, i.e., $G_i=\{\alpha^{(p-1)/p_i},\alpha^{2(p-1)/p_i},\ldots,\alpha^{p_i(p-1)/p_i}(=1)\}$. Since $y^{(p-1)/p_i}\in G_i$, there exists a unique value $b_0\in \mathbb{Z}_{p_i}$ such that $y^{(p-1)/p_i}=\gamma_i^{b_{0}}$. To ...

3

Although I was not able to run the scripts (perhaps my fault, my Python skills are mediocre at best), let me try to elaborate (slightly) on fkraiem's comment. You are indeed right that the complexity of Pohlig-Hellman is lower than the complexity of BSGS (for a curve of smooth order). However, your parameters are relatively small. Looking at the definition ...

3

I'm not sure if I understand the question correctly, but let's try anyway. By assumption we have some integer $m$ such that $\varphi(m)=2pq^5r^2$ for primes $p,q,r$. The goal is to solve a discrete logarithm problem in $\mathbb{Z}_m^*$, say we have $g,h\in\mathbb{Z}_m^*$ such that $h=g^\ell$ for some integer $\ell$. We note that $\mathbb{Z}_m^*$ is a ...

3

You forgot step 4: $m$ and $s$ should each be primitive roots mod $p$ and mod $q$ $m$ is not a primitive root mod $p$. We can easily deduce that (without the bother of actually performing any nontrivial math) from the relation you gave: $$s^{e_p} = m \bmod p$$ for $e_p$ even; hence $m$ must be a quadratic residue, and hence cannot be primitive. ...

2

Because $x$ is defined modulo $28$ ($2^{28} = 2^0$ in $(\mathbf{Z}/29\mathbf{Z})^*$), you can view $x$ as an element of $\mathbf{Z}/28\mathbf{Z}$, while $2$ and $3$ are elements of $(\mathbf{Z}/29\mathbf{Z})^*$.

2

Pohlig–Hellman algorithm can't be used as is, but it can be modified to make use of known partial factorization of $n$. Suppose that you need to find such $x$ that $g^x=h$. This can be done as follows: Choose small $k'$ such that $k'\ge k$. If the upper bound on $n$ is $n'$, then $k'=\lfloor\log_pn'\rfloor$ can be used. Set $g'=g^{p^{k'}}$ and $h'=h^{p^{k'}}... 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$...

1

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

1

A field like $GF(2^n)$ is represented by the residue classes of polynomials modulo $f(x)$ where $f \in GF(2)[x]$ is an irreducible polynomial of degree $n$ with binary coefficients. There are $2^n$ such polynomials $$a(x)=a_0+a_1 x+ \cdots+ a_{n-1} x^{n-1}.$$ Addition is by mod 2 addition of coefficients. When you multiply two polynomials, you take the ...

1

So if modulus, n is composite (i.e. non-prime) and the base is NOT a generator of Zn. Actually, if $n$ is has two distinct odd primes as factors, there will never be a generator; that is, there will never be a value $g$ where $g^x \bmod n$ takes on all values in $\mathbb{Z}_n^*$ Will PH algo still work and if so, why? If you know the factorization of $n$...

1

When solving for $x$ in the equation $g^x \equiv h \text{ mod } p$ the idea behind Pohlig Hellman is to solve discrete logs on group elements with smaller orders and then recombine those results to obtain $x$. For each prime factor $q^e$ of $p-1$ you do the following: Find an element with order $q^e$. You can do this via $g' = g^{\frac{n}{q^e}} \text{ mod }... 1 [Isn't this] just as hard as the RSA problem? Oddly enough, no. If we were given a random$p$, and were asked to see if there's a large prime factor$q$of$p-1$, yes, that would be, on average, a hard problem. However, that's not what we actually do. Instead, we get to pick$p$, and so that gives us a lot of flexibility. One way is to pick$q$first (... 1 You are correct in the procedure. You need to express$x$as$x = 2^0x_0+2^1x_1+2^2x_2+...+2^{15}x_{15}$Where the$x_i$are in$GF(2)$First compute:$3^{(0*(p-1)/2)} \pmod p \equiv 13^{(1*(p-1)/2)} \pmod p \equiv 65536$So that when you'll compute$2^{65536/2^{i+1}} \pmod p$you'll get either 1 (corresponding to$x_{i} = 0\$) or 65536 (corresponding ...

Only top voted, non community-wiki answers of a minimum length are eligible