# Tag Info

## Hot answers tagged discrete-logarithms

Accepted

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

Note that since $1 + 3^x > 1$, we have that $y$ is positive. We need that $2^y = 3^x + 1$. If $y \geq 3$, then $3^x + 1$ must be a multiple of $8$. But $3^x + 1$ is always either $2$ more or $4$ ...
• 7,088

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

We know that there is a solution, since $2$ is a primitive root for all powers of $3$. For smallish values of $n$, we could solve this by iterating up the powers of three: solve $\bmod 3$ giving $x_1$...
• 38.6k
Accepted

### I know that 3 is a primitive root of $31$. How can I solve $3^b \equiv 22$?

Hint: $22\equiv -9\pmod{31}$, so it is enough to find $L_3(9)$ and $L_3(-1)$. For $L_3(-1)$, you can use the fact that $-1$ is the unique element of order $2$ in the multiplicative group.
• 302k
Accepted

### Cubic root of a polynomial to modulo of another polynomial

As Lubin pointed out this can be viewed as a discrete logarithm problem. I assume that the polynomial $p(x):=x^{10}+x^3+1$ is known to be primitive, so the coset of $x$ is generator of the ...
• 124k
Accepted

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

Write $$2^a\equiv9\pmod{11}.$$ Rewrite it as $$2^a\equiv-2\pmod{11},$$or $$2^{a-1}\equiv-1\pmod{11}.$$ Squaring both sides, $$2^{2a-2}\equiv1\pmod{11}.$$ By Fermat's little theorem, we know that ...
• 51.8k

### How do I solve this logarithmic equation, which has an answer of 7?

$$10-\log_5(20)-\log_5(25/4)=10-(\log_5(20)+\log_5(25/4))=10-(\log_5(20\cdot25/4))$$ $$=10-\log_5(125)=10-3=7$$ In the first line I used the property that $$\log_b(x)+\log_b(y)=\log_b(xy)$$ In our ...
• 2,800
Accepted

### How to solve $a^x\bmod n=b$

This is known as the discrete logarithm problem, and it is believed to be a hard problem in general. (In fact if it isn't "hard", in an appropriate technical sense, the security of many widely-used ...

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

The Catalan conjecture, that the only perfect powers differing by $1$ are $2^3=8$ and $3^2=9$, was resolved by Preda Mihăilescu in 2002. The question you're asking is equivalent to finding solutions ...
• 30.3k

### Can irreversibility of trapdoor functions generally not be proved?

This is due to the fact that the existence of One-Way Functions (OWF) implies that $P \neq NP$. In other words, with contrapositive, if $P = NP$ then OWF doesn't exit. So if we have one you would know ...
• 1,475
Accepted

### What does "underlying field" mean in the context of groups?

There are a bunch of issues here in what you write. In particular, you have misidentified what "underlying field" refers to (it's not about the group in question, but about the conic in ...
• 363k
Accepted

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

I'm going to nitpick and point out that $\mod{}$ is not an operator. It is not the case that $8 \mod 5$ is the number $3$. Instead the sentence $8\equiv 3 \mod 5$ is a statement about $8$ and $3$. ...
• 120k
Accepted

### About powers in a finite field $\mathbb F_p$

Note that you're seeing the same graph four times because $123^{504}\equiv 1\pmod{1009}$ (so everything repeats itself offset horizontally by half the graph width) and $123^{252}\equiv-1\pmod{1009}$ ...

• 19k

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

This description of the logarithm is reminiscent of that of the cross-ratio, namely a ratio of ratios I'm not sure I'd call this a ratio of ratios. More like the ratio of logarithms of ratios. When ...
• 39.1k

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

$100 = 2^2 \cdot 5^2$. If $2 \equiv 5^{6578} \bmod p$, then $2^2 \cdot 5^2 \equiv 5^{2 \cdot 6578 + 2} \equiv 5^{3152}\bmod p$.
• 420k
Using An Introduction to Mathematical Cryptography, J. Hoffstein, J. Pipher, J. H. Silverman, let's use Shank's Babystep, Giantstep Algorithm: Let $G$ be a group and let $g \in G$ be an element of ...