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
0
votes
0
answers
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
0
votes
0
answers
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
0
answers
11
views
Discrete Logarithm Problem with Additional Information
Let $p = 2 m {q^2} + 1$ be a prime, where $m$ is a smooth integr and $q$ be any odd prime, and ${g_1},{g_2},h$ be primitive elements of ${\mathbb{F}_p}$ where are related by
$${g_1}^{{x_1}} = h\,\,...
- 21
0
votes
0
answers
108
views
Seeking for an algebraic proof of a problem of number theory
This is a problem in a test stands as a simulation of the NCEE (the college entrance examination of China), it starts by giving a definition of the discrete log:
Let $p$ be a prime number, and let $X=\...
- 151
1
vote
0
answers
43
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 ...
- 11
1
vote
0
answers
180
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.
- 71
0
votes
0
answers
333
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
82
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^{...
-1
votes
1
answer
58
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
36
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,376
1
vote
0
answers
48
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,376
0
votes
1
answer
52
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
39
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,438
0
votes
0
answers
111
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
246
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
289
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,724
0
votes
1
answer
51
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,942
2
votes
0
answers
121
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
100
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
105
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
154
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 \...
- 679
1
vote
1
answer
155
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,031
1
vote
1
answer
256
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
524
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".
...
- 508
0
votes
0
answers
99
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
108
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
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
0
votes
0
answers
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 ...
- 1
5
votes
0
answers
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
0
votes
1
answer
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
0
answers
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
1
answer
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
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
169
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
69
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
255
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
25
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
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
2
answers
152
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,874
1
vote
1
answer
147
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,649
1
vote
1
answer
468
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
203
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}-\...
- 181
0
votes
1
answer
134
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
99
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
229
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,851
1
vote
1
answer
146
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
28
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
1
vote
1
answer
67
views
Extending "the ring of exponents" from $\Bbb{Z}$ to that which contains a solution to $4^x - 3 = 0 \pmod 5$?
Let $R = \Bbb{Z}/5\Bbb{Z}$ be the ring of integers modulo $5$. Then $4^x = 1, 4, 1, 4, 1, 4, \dots$ as $x$ ranges over $\Bbb{Z}$. Thus $4^x = 3$ and $4^x = 2$ have no solution $x \in \Bbb{Z}$.
...
- 21.9k