13 votes
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
9 votes

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
6 votes
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.
5 votes
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 ...
5 votes
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
5 votes

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
4 votes
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 ...
4 votes

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 ...
4 votes

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
4 votes
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 ...
3 votes
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
3 votes
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}$ ...
3 votes

Shank's Baby-Step Giant-Step for $3^x \equiv 2 \pmod{29}$

I found flaw in my calculus for the second expression in second list, it should be $$ 2 \cdot 3^{-12} = 2 \cdot (3^{-6})^2 \equiv 2 \cdot 22^2 = 2 \cdot 484 \equiv 11 \pmod {29}$$ Hence, $x = 5 + 12 ...
  • 199
3 votes

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$

\begin{align} 2^{10+\lambda+n} - 2^{10+\lambda} - 144759 &\equiv 0 \pmod{3^{10}} \\ 1024 \cdot 2^{\lambda+n} - 1024 \cdot 2^{\lambda} - 144759 &\equiv 0 \pmod{3^{10}} \\ 1024 \...
3 votes
Accepted

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

Not an answer "per se" but two illuminating references (see below) about 17th century questionning on the connection between geometry and analysis. These documents address transitions in what could ...
  • 67.1k
3 votes

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

It is called a discrete log because $\,L(xy)\equiv L(x)+L(y)\ \pmod{p\!-\!1},\ $ therefore $$\begin{align} L(2)&\,\equiv\, 6579,\, L(5)\equiv 1\\[.2em] \Rightarrow\, L((2\cdot 5)^2) &\,\...
3 votes
Accepted

Can irreversibility of trapdoor functions generally not be proved?

This seems to be an open research problem. If you look at https://en.wikipedia.org/wiki/One-way_function it says that the existence of one-way functions is currently unproven. So for cryptography ...
  • 5,025
3 votes
Accepted

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

This is an instance of the difficult discrete logarithm problem, but it is small enough that it is amenable to hand computation. Algorithmically let's use Shanks' baby giant step. By below $2$ is a ...
3 votes
Accepted

Definition of finite field with fixed characteristic

The term quasi-polynomial time means quasi-polynomial in...which parameters? What fixed characteristic says is that the problem is quasi-polynomial in the field size as the field size varies, as long ...
  • 61.1k
2 votes

Hardness of discrete log in additive group

It's a matter of how field elements are represented. Elements of large finite fields are usually represented as vectors over a prime field with components in ${\mathbb Z}/(p)$. So addition is easy and ...
  • 81.2k
2 votes
Accepted

Alternative to Pohlig-Hellman with given generator order

The hint seems to just point you to using Pohlig-Hellman. We can use this approach whenever the order of our base element is smooth, in this case $g$ which has smooth order $2\cdot11\cdot19\cdot281$. ...
2 votes

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

It seems that you are thinking of 'mod' as an operation, such as might be found in a programming language. If, instead, you restate the above identity in terms of congruences, it might be clearer: $$(...
2 votes
Accepted

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

If I understand your question, for a given integer $y$, you want the set of integers $x$ such that $$ \left\lceil \frac{\log x}{\log 2} \right\rceil = y. $$ This equation is true exactly when $$ y-1 &...
2 votes

Shank's Baby-Step Giant-Step for $3^x \equiv 2 \pmod{29}$

$$3^x \equiv 2 (\text{ mod } 29)$$ $\varphi(29) = 28$ $m = \lceil \sqrt{28} \rceil = 6$ $\begin{array}{c|ccccc} j& 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 3^j & 1 & 3& 9 &...
2 votes

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$

You can write the first as $$2^n-1\lt \frac {349525\cdot 3^{10}+144759}{2^{10+\lambda}}\\n \lt \log_2\left(349525\cdot 3^{10}+144759\right)-10-\lambda\\n\le24-\lambda $$ so there are very few $n$s to ...
2 votes

The sum of logarithmic series

By Frullani's integral $$\sum_{n\geq 1}\frac{\log(n+1)}{n(n+1)}=-\int_{0}^{+\infty}\frac{(1-e^{-x})\log(1-e^{-x})}{x}\,dx=\int_{0}^{1}\frac{(1-u)\log(1-u)}{u\log u}\,du $$ hence in terms of Gregory ...
2 votes

In Mathematics is there a discrete logarithm function?

The definition of the discrete logarithm used there: if $g$ is a primitive root mod $p$ - that is, it generates the multiplicative group mod $p$ - and $u\not\equiv 0\mod p$ then $\log_g u$ is $\min\{L:...
  • 19k
2 votes

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
2 votes

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$.
2 votes
Accepted

Solving DLP by Baby Step, Giant Step

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 ...
  • 9,860

Only top scored, non community-wiki answers of a minimum length are eligible