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
0
votes
0
answers
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 ...
- 1
0
votes
2
answers
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 ...
0
votes
0
answers
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
1
vote
0
answers
57
views
discrete_log in elliptic curve torsion basis using sage
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.
- 81
1
vote
0
answers
48
views
Period finding enables solving the Discrete Logarithm Problem
Does being able to find the periods enable us to solve the Discrete Logarithm Problem (DLP)?
This is what I have got so far:
Let $G$ be a finite cyclic group with $G = \langle g \rangle$, i.e. $g \...
- 3,988
0
votes
0
answers
332
views
Given a modulus p, two primitive roots and the two products of the modular exponentiation attained by swapping the exponents: find the exponents.
Given a prime $p$, two of its primitive roots $(h_1, h_2)$, $A_1=(h_1^xh_2^y) \mod p,$ $A_2=(h_1^yh_2^x) \mod p$, find $(x,y)$.
How can it be solved?
Example:
$p=23$, $(h_1=2, h_2=3)$, $A_1=(2^x3^y) \...
- 1
1
vote
0
answers
80
views
Solving Discrete logarithm Problem ($6^x=112\!\!\!\mod\!\!151$) from given equation
I'm trying to solve the discrete logarithm problem $6^x\equiv112\!\!\!\mod\!\!151.$
I am given that
$6^{72}\cdot112^{65}\equiv112^{136} \!\!\!\mod\!\!151$
I then calculate from this equation that
$6^{...
0
votes
0
answers
26
views
To prove non-decidability between two sets is it required to prove non-computability between all elements of two power sets
I am constructing a set of information $Y = \{y_{1}, \dots, y_{n}\}$ and from another set $X = \{x_{1}, \dots, x_{n}\}$, some publicly known information and some secrets.
The construction should ...
- 323
-1
votes
1
answer
53
views
How do you solve a discrete logarithm $𝑎^𝑥≡𝑏\pmod n$ when $\gcd(𝑎,𝑛)≠1$?
I am trying to solve the discrete logarithm using the baby-step giant-step algorithm which requires the computation of $a^{-1}$ by using the set of substitutions to reduce it to a case where $\gcd(a, ...
- 259
0
votes
0
answers
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 ...
0
votes
0
answers
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 ...
- 3,205
1
vote
0
answers
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 ...
- 3,205
0
votes
1
answer
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:
...
user1104548
1
vote
0
answers
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 ...
- 3,418
0
votes
0
answers
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
0
answers
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, ...
0
votes
1
answer
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 ...
- 7,495
0
votes
1
answer
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.
...
- 1,845
2
votes
0
answers
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 ...
- 259
-1
votes
1
answer
99
views
I want to make sure that this is right with respect to the cardinality
Consider the following sets: $A=\{0,1\}$, $B=\{\{0,1\}\}$ and $C=A\cup B$. Enumerate the following sets and report their cardinality:
No. 1: $2^C$
No. 2: $C\times C$ (cross-product)
No. 1: $\{\},\{0\},...
0
votes
1
answer
86
views
Solving for $x$ in discrete logarithm [closed]
$$9 = 2^x \text{ mod } 11$$
How do you use a calculator to obtain this value?
The $x$ is an integer.
Used in Diffie–Hellman key exchange algorithm.
- 103
1
vote
1
answer
141
views
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 \...
- 605
1
vote
1
answer
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,021
1
vote
1
answer
189
views
Discrete logarithm problem: does the base have to be a generator of Z?
$\mathbb{Z}_p$ under multiplication, p=13, Z={1,…12}
I need to find the discrete logarithm of base 5 to 8:
So essentially $5^x \equiv 8 \pmod{13}$
From what I read the base must be a generator of $\...
- 57
1
vote
1
answer
441
views
What does "underlying field" mean in the context of groups?
I read a statement in this answer which said "In conics, the discrete logarithm problem of this group (conics) is no more difficult than the discrete logarithm over the underlying field".
...
- 456
0
votes
0
answers
94
views
Discrete logarithm problem in base 10. When is it of a very special form?
Doing some personal research I just stumbled upon this problem:
Given an integer $m\in \mathbb{Z}$ that is coprime to 10, I am interested in whether or not there exists an integer $n\in\mathbb{Z}$ ...
- 9
-1
votes
2
answers
106
views
A simple congruent equation $3^a\equiv1+b\mod m$ [closed]
I come across a simple congruent equation as follows:
let $m\geq 10$ be an integer.It is not a power of $3$. Then how can we find some $a$ and $b$ (they are integers) such that
$$3^a\equiv1+b\pmod{m},...
- 21
1
vote
1
answer
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 ...
- 97
0
votes
0
answers
52
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
0
votes
0
answers
58
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 ...
- 1
5
votes
0
answers
364
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
0
votes
1
answer
179
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
0
answers
37
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
1
answer
115
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 ...
- 456
0
votes
0
answers
54
views
What is the name of this method?
I have been doing some research into discrete log problem in the form of
$$f(x) = g^{\operatorname{floor}(x)} \; \text{mod } p.$$
Interestingly I found that there is a function $t(x)$ where $t(f(x))= ...
- 35
-2
votes
1
answer
118
views
Domain of function $x^{1/2}$
What different of 2 function: $\sqrt{x}$ and $x^{1/2}$? Why domain of $\sqrt{x}$ is $x \ge 0$ but domain of $x^{1/2}$ is $x>0$?
2
votes
0
answers
64
views
Integrating $\int_0^\infty \frac{\ln t}{t^2+a^2}\,dt$ with residue theorem. [duplicate]
I want to calculate
$$\int_0^\infty \frac{\ln t}{t^2+a^2}\,dt$$
using the Residue Theorem. The contour I want to use is almost the upper half circle of radius $R$, but going around $0$ following a ...
- 29
0
votes
2
answers
231
views
First and second derivative of a function log*(n) ("log star").
I would like to ask what are the derivative values (first and second) of a function "log star": $f(n) = \log^*(n)$?
I want to calculate some limit and use the De'l Hospital property, so that'...
1
vote
0
answers
24
views
In $Z_{p^e}^*$, why is $p$-adic presentation of $x = \sum_{i=0}^{e-1} x_i p^{i}$, why is $g^{p_e(x_1 + \dots + x_{e_1} p^{e-2})} = 1$
During studying for a cryptography course, I encountered the following formula in a section about calculating discrete logarithm in a group $\mathbb{Z}_n^*$. Assume that $n= p^e$ for some prime. Let $...
1
vote
1
answer
124
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 ...
- 426
1
vote
2
answers
146
views
Determine dlog in quotient rings of polynomial rings
Question:
Determine $\operatorname{dlog}_x (x^2 + 1)$ in $\Bbb Z_5[x]/\langle\,x^3 + x + 1\,\rangle$
So I know the elements of $F = \Bbb Z_5[x]/\langle\,x^3 + x + 1\,\rangle $ are of the form $ax^2 +...
- 1,864
1
vote
1
answer
136
views
Definition of finite field with fixed characteristic
In this article Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic the term finite fields of fixed characteristic is not defined and I couldn't find it on the ...
- 1,629
1
vote
1
answer
372
views
What is discrete logarithm?
Can someone help me out with explaining what discrete logarithm is in layman's term. Here's the Wikipedia article: https://en.wikipedia.org/wiki/Discrete_logarithm
- 27
0
votes
1
answer
182
views
How to find this discrete limit?
While proving some discrete Hardy-type inequalities I tried to prove the following limit for non-negative sequence $a(n)$ and $p>1$
$$\lim_{p\rightarrow1}\frac{1}{p-1}\left[\sum_{n=1}^{r}a(n)^{p}-\...
- 89
0
votes
1
answer
114
views
Hardness to solve DL-Problem
I was wondering why some groups provide more security to cryptosystems relying on DL-Problem.
It is not clear to me wether it is just due to the known attacks or if there are some other reasons. So ...
0
votes
2
answers
95
views
Can I find the exponent of a matrix given only a vector and its image?
here is my problem :
Given a $GL(m,2)$ matrix $A$, and $x,y$ two non-zero $F_2$ vectors of length $m$ with the premise that $y = x(A^n)$ for some positive integer $n$. The goal is to find n.
Is it ...
1
vote
1
answer
187
views
Finding discrete logarithm of composite numbers
I started to learn discete logarithm the definition says that:suppose that "p" is a prime number , "r" is a primitive root (modulo p) and "a" is an integer between "1 and p-1" inclusive.If r^e (...
- 5,672
1
vote
1
answer
134
views
When will the random bit sequence start to repeat in pseudo random number generator
Let's say we have the Blum-Micali pseudorandom number generator.
from wikipedia:
Let $p$ be an odd prime, and let $g$ be a primitive root modulo $p$.
Let $x_0$ be a seed, and let $x_{i+1} = g^{x_i}\ ...
- 113
-1
votes
1
answer
27
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
- 1
1
vote
0
answers
19
views
Hard problems that do not require predefined parameters
(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 \...
- 11