Questions tagged [discrete-logarithms]

For questions related to the discrete logarithm problem; modulo $p$, in finite fields, over elliptic curves, or in an abstract group.

For a cyclic group $G$ with generator $g$, a discrete logarithm of $b \in G$ to the base $g$ is an integer $k$ such that $g^k = b$.

Finding a discrete logarithm is (believed to be) a computationally hard problem, and various cryptographic protocols are built around it.

The underlying cyclic group is often the multiplicative group of $\mathbb{Z}/p\mathbb{Z}$ for some prime $p$, more generally a multiplicative subgroup of a finite field, or a cyclic group of points on an elliptic curve.

The intended usage of this tag is for questions on or related to the discrete logarithm problem (theoretic as well as algorithmic) and its applications.

Related tags include:

150 questions
2
votes
1 answer

Can't understand trivial discrete logarithm problem for $Z_{11}$

I have a seemingly trivial problem with description: Find all discrete logarithms of base 2 of all non-zero elements in $Z_{11}$ field. I'm basing my learning on the notes I managed to grab from other groups and for that problem, there's a…
Straightfw
  • 1,558
1
vote
1 answer

Mistake in pollard rho method for discrete logarithm

I'm reading about pollard rho's algorithm for computating the discrete log. To comprehend the algorithm, I do a concrete example, but obviously I'm making a mistake. In general: Let $G = \langle g \rangle$ be a cyclic group of order $m$, let $x \in…
ATW
  • 689
1
vote
1 answer

Is generator order the only factor in the hardness of DLP?

We are studying discrete logarithms and how they are used in cryptography. When working in $\mathbb{Z}_{p}^*$ I understand the importance of using a safe prime as the modulus so as to avoid being able to break the discrete logarithm into smaller sub…
XRBtoTheMOON
  • 1,031
1
vote
2 answers

What is the significance of using the term "discrete" in discrete logarithm?

I'm trying to clear up my confusion in using the term "discrete" in discrete logarithm. I'm focusing on why the word "discrete" is used to differentiate it from a logarithm. Wikipedia defines a discrete logarithm as follows: in any group $G$,…
JohnGalt
  • 189
0
votes
1 answer

Find $g^y$ in discrete log problem

If I have g = primitive root and p = prime number such that: X = $g^x$ mod p Y = $X^y$ mod p I know the values of g, p, X, Y. Can I calculate $g^y$ without knowing x? How do I do that? For example: Let us say I know that g = 5; p = 23; X = $g^x$ mod…
user1104548
0
votes
0 answers

Baby-Step-Giant-Step transformation Question

In most texts, the BSGS Algorithm solves $$g^x = b \bmod p$$ for x by rewriting the expression to $$g^{jm+i} = b \bmod p$$ then do: $$g^i = b(g^{-m})^j \bmod p$$ This requires to compute the inverse of $g$. Whats wrong if I transform it this way?:…
taomii
  • 1
0
votes
0 answers

Discrete logarithm for a range

Are there any efficient algorithms for solving the following problem? Let $b \leq m < n$, what is the smallest value for $k \geq 1$ such that $m^k$ mod $n$ is in the range $[0,b)$. A variant on this which would also be of interest is what is the…
MotiNK
  • 292
0
votes
0 answers

Discrete logarithm/ solving Diffie Hellman?

First, apologies. I'm decent at math, but i don't have a degree in it. Please excuse any ignorance on my part. And if any of my math is wrong, please correct me! So, for anyone not familiar with the diffie-hellman problem it is: given the…
0
votes
2 answers

Conversion to discrete logarithm

Given that $13^2 \equiv 2^3 \times 3^2 \pmod{97} $. How to derive to the form of discrete logarithm $$2 \equiv 3 \log_{13}{2} + 2\log_{13}{3} \pmod{96}?$$ I cannot figure this out. The only thing I know is the following definition $$a \equiv g^\mu…
0
votes
1 answer

Shanks Algorithm for composite orders

Can the Shanks algorithm for discrete logarithm problem (baby-step/giant-step) be used for composite orders? According to Wiki, "Usually the baby-step giant-step algorithm is used for groups whose order is prime. If the order of the group is…
-1
votes
1 answer

how would I solve $22$ ≡ $5^a$ mod $23$ for $ a$?

I need to solve $22$ ≡ $5^a$ mod $23$ for $a$. I am new to discrete logarithms, and I'm confused how to go about this. I tried using the baby step giant step algorithm approach but I'm still unsure
boxcut
  • 1