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.

Filter by
Sorted by
Tagged with
-2
votes
0answers
21 views

prove that (A/p) =1 <=> index of A relative to G is even [closed]

I'm studying about number theory but I cannot do it... please help me.. p is a odd prime, G is primitive root modulo p, A is interger, gcd(A,p) = 1 is given. Question is Prove that (A/p) =1 <=> ...
0
votes
1answer
60 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.
1
vote
1answer
33 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 \...
1
vote
1answer
60 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
1answer
38 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 $\...
1
vote
1answer
182 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". ...
0
votes
0answers
69 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}$ ...
-1
votes
2answers
98 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},...
1
vote
1answer
66 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 ...
0
votes
0answers
42 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 ...
0
votes
0answers
45 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 ...
6
votes
0answers
199 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 ...
0
votes
1answer
47 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 ...
1
vote
0answers
29 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 ...
1
vote
1answer
79 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 ...
0
votes
0answers
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))= ...
-2
votes
1answer
58 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
0answers
54 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 ...
0
votes
2answers
106 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
0answers
23 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
1answer
55 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 ...
1
vote
2answers
84 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
vote
1answer
84 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
vote
1answer
141 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
0
votes
1answer
83 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}-\...
0
votes
1answer
55 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
2answers
77 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 ...
0
votes
1answer
84 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 (...
1
vote
1answer
38 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}\ ...
-1
votes
1answer
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
vote
0answers
17 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 \...
1
vote
1answer
54 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}$. ...
0
votes
0answers
44 views

Elliptic Curve - Prime Generator

This question is in regards to the prime generator for an elliptic curve. I have taken the prime curve $\mathbb Z_p$ and have the $5$ prime number factors for the prime curve using Euler's Totient. Is ...
1
vote
0answers
43 views

Is there an upper bound for $2^x \bmod P$ in range again?

Is there an upper bound for $x \in \mathbb{N}_+$ in $$ v \cdot 2^x \equiv m \mod P $$ to get a remainder $m$ with $$N\le m <2N$$ given a random initial value $v$ with: $$N\le v <2N$$ $P$ is a ...
1
vote
1answer
35 views

Discrete Logarithm Variation

Given a positive integer $x$, is there an efficient method to determine integers $k$, $a$ and $b$ such that $kx+1=a^b$? Examples: $x=17$, $15(17)+1=2^8$ $x=13$, $2(13)+1 = 3^3$ $x=12$, $2(12)+1 = ...
1
vote
2answers
123 views

Find an exponent $b$ such that $4^b \equiv 34\pmod{107}$

Find a b such that: $4^b \mod 107 = 34$ My first thought is to use F.L.T. $$4^{106} \mod 107 \equiv 1 \mod 107$$ $$34*(4^{106}) \mod 107$$ but seems a little unnessicary... Any thoughts on ...
0
votes
1answer
42 views

A general expression for $\ln i$

Is there a general expression for $\ln i$, that can give all different values of $\ln i$, depending upon an input value? I know of them is $i\pi/2$, so is there a formula to find others too?
6
votes
2answers
99 views

Can irreversibility of trapdoor functions generally not be proved?

The German Wikipedia article on asymmetric cryptography states that asymmetric cryptography is always based on assumptions which can not be proven: Die Sicherheit aller asymmetrischen Kryptosysteme ...
0
votes
1answer
104 views

Discrete Logarithm is Homomorphic

Recall that $l_g(h) ($mod$ p)$ is the discrete log to base $g$ mod $p$, that is, $g^{l_g(h)} \equiv h($mod$ p)$. Let $p$ be prime, and $g$ a primitive root $($mod$ p)$. Show that: $l_g(h_1h_2)$ = $...
1
vote
2answers
125 views

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 ...
0
votes
1answer
84 views

Formal proofs for $f_p(a \cdot b) = f_p(a) + f_p(b) \mod p $?

Let $ x $ be coprime to an odd prime $p$. Then consider $$ f_p(x) = \frac{x^{p-1} - 1}{p} $$ By Fermat's little we know this is always an integer. In 1850 Eisenstein proved that $$ f_p(a \cdot b)...
0
votes
1answer
65 views

DLP - formulae for length of $G_{list}$ in terms of prime $p$ for $g=2,3,...$

The DLP is defined as: $$g^x \cong h \pmod{p}$$ Using $g=2$ and $g=3$ I've found that the size of list of unique $h$ values (I call the $G_{list}$) for primes from $p=3$ upto $p=19$ are of the form ...
0
votes
5answers
87 views

How do I solve this logarithmic equation, which has an answer of 7? [closed]

$$10 - \log_5{20} - \log_5{25\over4}$$ The $5$'s are the bases and the answer to this equation is $7$, but I don't know how to solve it.
0
votes
1answer
96 views

primitive root of a number

Here in the definition of primitive root, it states: "a to be a primitive root modulo n, φ(n) has to be the smallest power of a which is congruent to 1 modulo n" (taking the set of integers) What my ...
1
vote
1answer
244 views

Finding all solutions of 'Discrete Root'

Ques: $x^k \equiv a \pmod n$, where n is prime. What are the possible values of x? I know how to find a discrete root using both primitive root and discrete logarithm concepts. But I am wondering ...
2
votes
1answer
266 views

Solving DLP using the method of Pohlig-Hellman

I want to solve the DLP for $p=29$, $a=2$ and $b=5$ using the method of Pohlig-Hellman. $$$$ I have done the following: We have that $p-1=28=2^2\cdot 7$. We get \begin{align*}&x_2= x\pmod {...
1
vote
1answer
2k views

Solving DLP by Baby Step, Giant Step

I want to solve the DLP $6\equiv 2^x\pmod {101}$ using Baby Step, Giant Step. $$$$ I have done the following: We have that $n=\phi (101)=100$, since $101$ is prime. $m=\lceil \sqrt{100}\rceil=...
1
vote
0answers
29 views

If the discrete log is easy in $F_p$ is it also easy in $F_{p^2}$?

Given a finite field $F_p$, for some large $p$. If DLOG is easy in $F_p$ is it also easy in $F_{p^2}$?
3
votes
2answers
135 views

Discrete Log solve using Index-Calculus producing incorrect 'r' value.

I have a discrete log that I need to solve to aid in a Cryptography problem, that deals with both programming and mathematics, so I was unsure where to post this problem, feel free to move me if ...
2
votes
0answers
407 views

Is Elliptic Curve Discrete Logarithm Problem NP-Hard or NP-Complete

I have trouble classifying Elliptic Curve Discrete Logarithm Problem as NP-Hard or NP-Complete. Where does ECDLP belong? Any brief comprehensive answer is encouraged. Thanks.