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

152 questions
Filter by
Sorted by
Tagged with
10 views

### Run the depth-first search algorithm on the following graph. Room has been left in the vertices for the discovery and finish times and the predecessor

Run the depth-first search algorithm on the following graph. Room has been left in the vertices for the discovery and finish times (which are required) and the predecessor (which isn't required, but ...
53 views

### Big-Oh notation question

When we have a question like so: What is the smallest integer $n$, such that $f(x) = x^{5.7}(\log x)^{1.2}$ is $O(x^n)$? Would we go about the question as so: round up $x^{5.7}$ to become $x^6$. Since ...
21 views

### Proof that you can solve the discrete logarithm problem given the period of a certain function.

Given $q$ a prime number , $a$ a primitive root modulo $q$ and $b=a^x \pmod q$. The discrete logarithm problem is to find $x$ (specifically the smallest positive integer $x$ for which the previous ...
1 vote
57 views

I want to solve a discrete log problem on elliptic curve using sagemath. Given a basis of E[D], denoted as P and Q. How to solve aP + bQ = R where R is a point of order D.
1 vote
48 views

1 vote
80 views

62 views

### How does Pollard's rho for discret logs work?

I'm trying to understand the wikipedia articel https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms to Pollard's rho for finding discret logs. But I don't understand the very end of ...
32 views

### On Factoring and Discrete Logarithms in $\mathbb{F}_p$

Suppose $n$ is an integer with factorization $n = ab$, and $a, b$ unknown and not necessarily prime. From this point forward, assume that we are free to choose $p$. Let $g$ denote a primitive element ...
1 vote
39 views

### A question on Zech's Logarithm

I was reading the chapter on Discrete logarithms over finite fields in Handbook of Finite fields, specifically this online reference to the chapter on discrete logs. In Remark 11.6.10 (reproduced ...
46 views

### 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: ... 1 vote
37 views

### Why is it said that it's difficult to solve for $k$ in $b^k=a$ as a discrete log problem?

I was looking up a tutorial that talked about the finite field and discrete log problem. It's said that solving for $k$ in $b^k=a$ is a problem that is difficult. The example given was: What power do ...
93 views

### Assuming secp256k1 curve and given fixed (but random) $h$ and $d$ values, is it possible to calculate a $k$ such that $h\equiv(k\,G)_X\,(k-d)\pmod n$?

For generator point $G$ in the secp256k1 curve, I want to find a value $k$ such that: $$h\equiv(k\,G)_X\,(k-d)\pmod n$$ where $n$ is the group order, and $(k\,G)_X$ indicates the x-coordinate (mod n) ...
1 vote
137 views

### How hard the discrete logarithm Problem modulo P is

I actually have two questions related to how hard the discrete logarithm problem is. In the two questions, I will use the following notation for the DLP: $g^x\equiv h \pmod{p}$, where $p$ is a prime, ...
201 views

### Discrete Logarithm Problem as Period finding of a function

The discrete logarithm problem (DLP) : Find $b$ knowing $s,a$ and $p$ such that $$b=a^s\mod p$$ where $p$ is a prime number and $a$ is a generator of the group defined by $p$. It is stated that the ...
49 views

### Discrete logarithm method to send keys.

In my criptography course I was given the following exercise: ElGamal proposed the following digital signature scheme using discrete logarithms over a field $\mathbb{F}_p$, where $p$ is a large prime. ...
106 views

### When can baby-step giant-step algorithm not be used to solve a DLP?

I'm trying to understand when there is a solution to the general DLP: given a, b, and n find ...
99 views

1 vote
115 views

### 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 ...
1 vote
189 views

### 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
(A) Is the following problem hard (i.e. no known solution in polynomial time)? For large values of $N$ and $M$ (e.g. $N \ge 4096$, $M \ge 130$), find values for $g,x,c,p$ and $q$ such that: \$ g^x \...