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

Help me out with this algorithm I came across [closed]

I saw this question on my email sent by my colleague to check out. I am still confused with this question; $\begin{cases}20^6 \mod 12 = 4\\ 33^2 \mod 10 = 9\end{cases}$. The question can be seen like ...
1
vote
1answer
49 views

The Discrete Logarithm

Can someone help me out with explaining the discrete logarithm in lay man's term. here's the Wikipedia article: https://en.wikipedia.org/wiki/Discrete_logarithm
0
votes
1answer
55 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
20 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
69 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
29 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 (...
0
votes
1answer
23 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
23 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
14 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
51 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
38 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
38 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
31 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 = ...
0
votes
0answers
41 views

Why the Discrete Logarithm Problem in under a prime modulo

The Discrete Logarithm problem is formulated as: $\beta \equiv \alpha ^{x} \quad mod \,\, p$ where $\beta$,$\alpha$ are integers and $p$ is a prime number. Why is important that $p$ is a prime ...
0
votes
1answer
20 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
71 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
41 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
81 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
56 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
62 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
74 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
60 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 ...
0
votes
1answer
112 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
109 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
520 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
28 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}$?
-1
votes
3answers
108 views

Index Calculus with factor base {2,3} to solve $ 3^x \equiv 11 \pmod{37}$ [closed]

I'm not sure how to start this, I know I'm supposed to use log to help me out..But my textbook isn't very clear
3
votes
2answers
93 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
193 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.
0
votes
1answer
128 views

discrete logarithm and calculating with modulo

I have the following scenario: Let $p' = 3, q' = 5, p = 7, q = 11, n=pq = 77$. Then $\mathbb{Z}_{77}^* = \{a \in \mathbb{N} \ \big\vert\ 1\leq a \leq 77, gcd(a, 77) = 1\}$. Furthermore $QR_{77} = \...
1
vote
0answers
19 views

Distribution of elements of a particular order in $(\mathbb{Z}/m\mathbb{Z})^*$

Consider the group $G = (\mathbb{Z}/m\mathbb{Z})^*$, where $m$ is such that $G$ is cyclic. Let $g\in G$ be some fixed generator, and let $a_1,\dots,a_{\varphi(m)}$ be an enumeration of the elements of ...
14
votes
2answers
549 views

Geometric interpretation of the Logarithm (in $\mathbb{R}$)

(Note: limited to $\mathbb{R}$) (Note: Geometric here means with straightedge and compass) Standard approaches to introducing the concept of Logarithm rely on a previous exposition of the ...
0
votes
1answer
105 views

Solve for $b$ in the equation $2^b \equiv 893 \pmod{1373}$

The question asks to solve for $b$ in the following equation: $2^b \equiv 893 \pmod{1373}$ However I am not sure how to solve this, as I only know how to solve for integers on the left hand side. The ...
4
votes
2answers
394 views

How can I solve this problem : $2^{x} \equiv{2070442609 \cdots 226509} \pmod {6561}$

I want to solve this discrete logarithm problem with Pohlig–Hellman algorithm: $$2^{x} \equiv{ 2070442609353644988500364779751625112994538364565830646055667805\\ ...
1
vote
0answers
23 views

How to do the shortcut function in ECC when N (Private Key) is Known

When N or private key is known, we don't have to iterate through all the process just to get the final location given the two initial points. How is that shortcut function implemented given the ...
2
votes
1answer
153 views

In Mathematics is there a discrete logarithm function?

I find it difficult to understand this part in this book. Because, as far as I know, there is no unique function or formula for discrete logarithms. I cann't understand what this formula does. Is ...
2
votes
1answer
109 views

Is wikipedia Pollard's rho algorithm for logarithms wrong?

https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms I am confused. It seems that algorithms's step x ← r−1(a2i - ai) mod p should be mod ...
1
vote
2answers
106 views

Unable to solve this exponential equation - Diffie-Hellman key exchange

By looking at it, I can deduce that $a = 6$, and $b = 5$, but how do I can solve for $a$ and $b$ without guessing? $$2^a = 11b + 9$$
0
votes
1answer
121 views

In the finite field $\mathbb{F}_{101}$ ,where discrete logarithms are $L_2(3)=69$ and $L_2(5)=24$. Compute the discrete logarithm $ L_2(60)$?

Now, I have that $L_2(60)=L_2(4*3*5)=L_2(4)+L_2(3)+L_2(5)=2+69+24=95$. So from my work $L_2(60)$ is $95$, but the answer on some other website gives $14$. I just don't see where I went wrong.
0
votes
1answer
31 views

Log Power Rule (Substituting a 2^X)

Always approach Logarithms with uncertainty. a bit confused by Log of power rule. Hope to receive some simple clarifications. Found this post very interesting. Where we basically have $T(n) = \Theta(n^...
0
votes
0answers
36 views

Discrete logarithm for a range

Are there any efficient algorithms for solving the following problem? Let $b \leq m < n$, what is the smallest value for $k \geq 1$ such that $m^k$ mod $n$ is in the range $[0,b)$. A variant on ...
0
votes
1answer
59 views

Is security of the modulus needed to maintain the “discrete logarithm problem”?

After a serious google search, I have been unable to find a definite yes/no answer to the following question. Assume I have c, e and m, and I compute $r = c ^ e \mod m$ This is with regard to the ...
0
votes
4answers
1k views

The sum of logarithmic series

I will be very grateful for help and suggestions how to calculate the sum $$\sum\limits_{n=2}^{\infty}\frac{\log(n)}{n(n-1)}$$
0
votes
2answers
83 views

Is it possible to find such a $n\in \mathbb {Z^{+}}$, for given value of $\lambda;$ $\frac {2^{10+\lambda+n}-2^{10+\lambda}-144759}{3^{10}}<349525$

I'm trying to solve a mathematical problem. I expressed the point where I was stuck with the modular arithmetic. Here is my problem; Is it possible to find such a $n\in \mathbb {Z^{+}}$, for given ...
0
votes
0answers
18 views

Finding a probabalistic algorithm for the discrete logarithm problem

I am working on the following exercise: $1)$ Fix $x \in \mathbb{Z}_n$ and randomly (u.i.d.) chosse $r_1,r_2,\ldots,r_q \in \mathbb{Z}_n$. Show that when $q$ is chosen as $q = \lfloor \sqrt{2n} \...
1
vote
0answers
149 views

Discrete first and second fundamental forms

I want to calculate first and second fundamental coefficients for some points in a point cloud (sampled surface), I used this method (https://arxiv.org/abs/1601.07272) but in this, only three closest ...
3
votes
2answers
77 views

Do there exist any integer solutions for $y=\log_2(1+3^x)$?

I was working on this problem and came to a standstill. I'm not exactly sure how to go about this problem, to find if any integer pairs of $(x,y)$ satisfy this equation. Any guidance would be ...
0
votes
1answer
44 views

Group Isomorphism unique element representation

Consider the finite fields GF$(168485857)$ which has $168485856$ elements not counting the zero element. $g=5$ is a primitive root. Let $C$ be the cyclic group which contains all elements $e$ that ...
1
vote
0answers
33 views

Research in the Discrete Logarithm Problem

I have already taken a course on Abstract algebra and tis implementation in the criprography, among other topics the course focused on the discrete logarithm problem in finite fields. Now, I would ...
0
votes
0answers
85 views

Discrete logarithm problem - Pohlig Hellman $GF(2^{60})$

I would like to ask how to modify Pohlig Hellman algorithm if I need to work with polynomials $GF(2^{60})$ I know how this algorithm works with numbers, but I am not able to imagine how to do some ...