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

I don't know the general answer, however, it appears that Baby-step Giant-step is able to give you the solution in $O(\sqrt{in})$ time (where $n$ is the size of $G$); this is $O(\sqrt{i})$ times longer than it takes the same algorithm to solve a single discrete-log problem. The first observation is that if you know the group order $n$ and a group generator $...


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

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


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


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


2

Suppose we have a point $P$ of order $q$ on an elliptic curve where the prime decomposition of $q$ is $q = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_n^{\alpha_n}$. We also have a point $Q=kP$ and we want to find $k$. Pohlig-Hellman algorithm The idea of Pohlig-Hellman's algorithm is to to compute a discrete logarithm in the subgroups of prime order. Easy case ...


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 answer to the final part of the question about index calculus depends on the finite field you are choosing to construct your group $G$. If the characteristic is large enough, the algorithm to use is the number field sieve. In this case, computation of individual logarithms is much faster than the initial computation that leads to logarithm of the ...


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 1$ $3^{(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 ...


1

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})^*$.


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