Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

-1
votes
3answers
65 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
66 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 ...
1
vote
0answers
37 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
46 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
309 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
76 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
306 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\\ ...
0
votes
0answers
13 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
69 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
66 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 ...
0
votes
0answers
37 views

Is it possible to convert factorization problem into discrete logarithm problem and vice versa?

You can see at this link wiki: Discrete_logarithm#Algorithms that some algorithms for factorization of numbers can be used to solve discrete logarithm problem. Can you give me an explicit example how ...
1
vote
2answers
72 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
76 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
0answers
18 views

Discrete logarithm modulo powers of two

Given an odd integer $x$ and integer $k>1$, what is known about the set $\{x^n \mod 2^k | n \in N\}$, in particular it's size and anything about the series of integers that will appear? I know ...
0
votes
0answers
32 views

Does solving the prime DLP implies solving composite DLP

DLP problem can be solved for $GF(p)$ and $GF(q)$, where $p$ and $q$ are primes, with many different algorithms. Let $n=p \cdot q$ be a composite number. Can we use the factorization of $n$ to ...
0
votes
1answer
29 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
32 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
38 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
273 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
81 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
17 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
109 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
70 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
39 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
25 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
33 views

Adversary game with discrete logarithm

i am studying some cases of the discrete logarith problem that would probably make it a weaker problem to be solved, and i started experimenting by multiplying/adding etc some things to it, i would ...
0
votes
0answers
42 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 ...
1
vote
0answers
42 views

Is elliptic curve suitable for using in ECDLP?

I have elliptic curve $y^2 = x^3 + x + 1$ over $GF(101)$ . I need to find order and decide if it is suitable for using in elliptic curve discrete logarithm problem me. I tried to find order, and I ...
0
votes
1answer
34 views

Validity of ElGamal Signatures

I'm trying this example question, with $g≡5$ mod $p$ being a generator and $p$=$647$ being prime The question says Alice publishes her public key $y ≡ 57$ mod $p$ And the question says Bob receives ...
1
vote
1answer
48 views

For generator $g$ of multiplicative group: if $\log_g (f^3) = 3x$, then $\log_g (f) = x$?

$F_q$ is finite field, $g$ - generating element of multiplicative group. Assume that for some element $f$ from multiplicative group we have $\log_g (f^3) = 3x$. Is it true, that $\log_g (f) = x$?
8
votes
1answer
1k views

Is it possible to find a closed-form expression for $f(n)$?

QUESTİON UPDATED: Here is my problem: $$2^x \equiv a \pmod{3^n}.$$ where, $a\not\equiv 0 \pmod{3}$ and $n\in \mathbb{Z^{+}}$ I want to learn that, If, $x=\left\{ {{3^n-\binom{n}{2}}...
0
votes
1answer
49 views

Is there a direct mathematical function/ formula for calculate this problem?

Is there a direct mathematical function/ formula for calculate this problem? $$a^x \equiv b (\mod n)$$ $$x=\text{ind}_a b (\mod n)$$ I want to learn that; 1) What is "ind" here? 2) Is ...
2
votes
1answer
56 views

Characterizations of the discrete logarithms for algebraic structures more general than groups

For an arbitrary group with elements $a$ and $b$, the discrete logarithm $\log_b a$ is defined as an integer $x$ that solves the equation $b^x = a$. It's straightforward to show that the set of ...
1
vote
1answer
29 views

is it meaningful to calculate $(x+1)^{x+2}$ in $GF(3^2)$, e.g. using discrete logs?

I'm teaching myself about algebra and fields and I've just started playing with discrete logarithms. I constructed GF($3^2$) using the polynomials degree $<2$ and arithmetic modulo the irreducible ...
0
votes
5answers
47 views

Show that if n is a power of 3, then $\sum_{i=0}^{\log_3n} 3^i = \frac{3n-1}{2}$

Show that if n is a power of 3, then $\sum_{i=0}^{\log_3n} 3^i = \frac{3n-1}{2}$ $\sum_{i=0}^{\log_3n} 3^i =3^0+3^1+3^2+3^3...+3^{log_3n}$ This is a geometric sequence, so I used the geometric sum ...
0
votes
0answers
250 views

Pohlig–Hellman/Big step baby step

I had an original question $g^x≡h\pmod p$ where $g=5$ $h=1000$ $p=1000777$ solving for $x$ I calculated $N=p-1=2^3\cdot3\cdot7^2\cdot23\cdot37=1000776$ calculating $g1,...,g5$ and $h1,...,h5$ $g1=5^...
0
votes
1answer
40 views

Find closed sequences of $y= \lceil log_2 x\rceil$ function

Question regarding the ceiling of a binary logaritm and it's sequences. How to calculate the sequences of the closed form: $y= \lceil log_2 x\rceil$ where $x\in\mathbb{N} ?$ Description I want to ...
0
votes
1answer
110 views

Use pohlig-hellam algorithm to solve discrete log whose modulus is a primorial number

Recently I read a paper in which it use Pohlig-hellman algrithm to solve the follow formular: $$N \equiv 65537^c \pmod M $$ The target is to get c when N is given.The interesting thing is that the ...
2
votes
2answers
61 views

Why does $(g^a \bmod n)^b = (g^b \bmod n)^a = g^{ab} \bmod n $?

The Diffie–Hellman key exchange protocol relies on the fact that one person, Alice, can perform $(g^a \bmod n)^b $ and another person, Bob, can perform $(g^b \bmod n)^a $ and they will both arrive at ...
-1
votes
1answer
71 views

Polig-helman algorithm - if $g$ is a prim root mod $p$ does this mean that in the subproblems that all $A_i$ are prim roots mod $p$? [closed]

I am using the Pohlig-Hellman algorithm to solve a Discrete Log Problem to find $x$ in $$g^x = h \pmod{p}$$ Where $g, h$ are positive integers and p is prime. Now presume g is a primitive root mod ...
0
votes
0answers
25 views

Continuous functions $F(x)$ that satisfy: period of $x$ divides $F(x)$ for all values of $x$

Let $P(x)$ be the period of $x$ base 2, for $x \in \mathbb{N}$, $x > 1$ and $gcd(x, 2) = 1$. i.e: $$2^{P(x)} \equiv 1 \pmod{x}$$ Let $F(x)$ be a continuous function such that $P(x)$ divides $F(x)...
0
votes
0answers
52 views

Is finding “a” given g, g^a, and g^(a^-1) mod p intractable?

Obviously, the discrete logarithm problem is thought to be hard. But what if you are also given $g^\left(a^{-1}\right)$? Does that give enough information to solve for $a$? Or is that also ...
0
votes
0answers
72 views

Polig-helman - solving $3^x = 5 \pmod{113}$ - 2 methods give different values for $x_1$ for $40^x=42$

I am using the Pohlig-Hellman algorithm to solve a Discrete Log Problem to find $x$ in $$3^x = 5 \pmod{113}$$ Using the notation: $$g^x = h \pmod p$$ We have $g = 3$, $h = 5$, $p = 113$, $N = p ...
1
vote
1answer
196 views

Apply Chinese Remainder Theorem to solve Discrete Logarithm Problem

I have to find $\xi$ such that: $$343857231343^\xi \underset{n}{\equiv} 146812954167 $$ with $n = 1022126907089$. $n$ was chosen to ensure that $factor(n) = p * q$. I have computed $\xi_1$ and $\...
2
votes
1answer
512 views

Pohlig-Hellman Algorithm for solving a DLP - can $x_0$ have > 1 solution?

I have taken generator $g=3$, $h=5$, and prime $p=101$ So; $$3^x=5 \mod 101$$ Following steps of Polig-Helman I get; $p-1=100=5^{2}.2^{2}$ Hence largest prime power divisor $q^e=5^2$. Calculate $g^{...
0
votes
1answer
67 views

Question about a proof-of-knowledge for discrete log [closed]

I'm reading a paper about proofs of knowledge for the discrete log problem and I'm having trouble understanding this bit (I'll condense the example to the relevant bits) : We want to prove we know $...
0
votes
0answers
86 views

Compute the discrete log

How can I compute the discrete log of $7$ and $11$ modulo $2311$ with respect to the primitive root $(3, 11)$, using the Pohlig-Hellman method. However, Pohlig-Hellman method is for small prime, so ...
0
votes
1answer
32 views

Given $g^x$ and $g^y$, identify $g^{xy}$ from $g^r$ in an ideal scenario

It is know that given a large prime $p$ and a primitive root of $\mathbb{Z}_p^*$, $g$, and two numbers $g^x$ and $g^y$ (modulo $p$), it's impossible to distinguish $g^{xy}$ from $g^r$ where $x$, $y$ ...
0
votes
1answer
57 views

Understanding Polig-Hellman algorithm for DLP via example

I am trying to follow the working of an example of stated algorithm on following link (http://www-math.ucdenver.edu/~wcherowi/courses/m5410/phexam.html). Let the prime $p = 8101$, and a generator of $...