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.

151 questions
Filter by
Sorted by
Tagged with
36 views

discrete logarithm over finite fields

Computing the discrete logarithm of a general field element $\beta \in \mathbb{F}_q$ with respect to a primitive $\alpha$ is generally an NP-intermediate problem. However, is there any non-trivial ...
• 2,399
12 views

Removing vertices from rooted tree to make it balanced

The question says, what is the least number of vertices that must be deleted from T to yield a balanced tree. The correct answer is 1. But how, i see the graph is already balanced and doesn’t need ...
• 11
1 vote
11 views

• 21
1 vote
74 views

Rewriting logarithms

I am trying to understand the lower bound of a Bloom filter and want to know how this rewriting is possible from this article (page 6-7 (or 490)). If $$m\geq n\mathrm{log}_2(1/\epsilon)$$ is some ...
56 views

Discrete Logarithm Problem used in currently used cryptosystems

Is it incorrect to say "Many important algorithms in public-key cryptosystems used at present have their security based on the assumption that the Discrete Logarithm Problem (DLP) over some ...
• 201
63 views

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

Can you explain this relation between finite fields and circles?

Let $p$ be a prime such that $p \bmod 4 = 1$, so there exists some $i=\sqrt{-1}$ in $\mathbb{F}_p$. Furthermore, let $r \in \mathbb{N}$ be the radius of a circle such that there are $p-1$ lattice ...
• 189
225 views

Definition of minus power in cyclic group

I am trying to understand Schnorr signature scheme, and in the text book there is the following computetion: $$g^s\cdot y^{-r}\stackrel{?}{=}I$$ The context is cyclic groups, and $g$ is a generator of ...
• 125
1 vote
43 views

Semaev's attack - strange step?

Semaev's elliptic curve discrete logarithm calculation algorithm (paper) has such first steps: given P and Q = nP, q - field modulo, E = EllipticCurve(GF(q), [a,b]) # y^2 = x^3 + a*x + b ...
• 11
1 vote
144 views

Unable to understand the final step in Pohlig-Hellman algorithm to solve the Discrete Log Problem

To solve for $x$ $2^x \equiv 41 \mod 211$ $\phi(p) = p - 1 = 210 = 2.3.5.7$ Solving by Pohlig-Hellman, we get to $x \equiv 3 \mod 7$ $x \equiv 2 \mod 5$ $x \equiv 2 \mod 3$ $x \equiv 1 \mod 2$ Then ...
• 508
54 views

1 vote
154 views

Parity of discrete logarithms is independent of base

By "parity" I mean the residue with respect to modulus 2, that is simply even or odd. The problem is stated as follows: "Assume p is an odd prime, suppose $r_1$ and $r_2$ are primitive ...
• 436
1 vote
152 views

• 113
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