Skip to main content
MathOverflow

Return to Question

Added that we're interested in the general case.
Source Link
Matt Groff
Matt Groff
  • 221
  • 1
  • 7

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have a value of order $p_x$ for all $x$, can we calculate the discrete log efficiently?

Here the interest is in the discrete log of any base, i.e. for the general case. There may be algorithms that work well for a specific base, but here the focus should be on algorithms for all bases.

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have a value of order $p_x$ for all $x$, can we calculate the discrete log efficiently?

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have a value of order $p_x$ for all $x$, can we calculate the discrete log efficiently?

Here the interest is in the discrete log of any base, i.e. for the general case. There may be algorithms that work well for a specific base, but here the focus should be on algorithms for all bases.

Edited that we have the prime factorization of Euler's totient of $n$.
Source Link
Matt Groff
Matt Groff
  • 221
  • 1
  • 7

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $n$$\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have a value of order $p_x$ for all $x$, can we calculate the discrete log efficiently?

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $n$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have a value of order $p_x$ for all $x$, can we calculate the discrete log efficiently?

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $\varphi(n)$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have a value of order $p_x$ for all $x$, can we calculate the discrete log efficiently?

Edited the values that we have.
Source Link
Matt Groff
Matt Groff
  • 221
  • 1
  • 7

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $n$. Assuming that we have the valuesa value of order $e^{2 \pi i/(p_x)^{k_x}} \bmod n$$(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have the valuesa value of order $e^{2 \pi i/p_x} \bmod n$$p_x$ for all $x$, can we calculate the discrete log efficiently?

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $n$. Assuming that we have the values $e^{2 \pi i/(p_x)^{k_x}} \bmod n$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have the values $e^{2 \pi i/p_x} \bmod n$ for all $x$, can we calculate the discrete log efficiently?

Let $(p_1)^{k_1}(p_2)^{k_2}\dots$ be the prime factorization of $n$. Assuming that we have a value of order $(p_x)^{k_x}$ for all $x$, can we calculate the discrete log of any value in $\mathbb{Z}_n^\times$ efficiently? Alternatively, if we have a value of order $p_x$ for all $x$, can we calculate the discrete log efficiently?

Source Link
Matt Groff
Matt Groff
  • 221
  • 1
  • 7