Skip to main content
Theoretical Computer Science

Return to Answer

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1

I believe no polynomial algorithm is known.

According to a paper this is used in at least one cryptosystem:

Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method.

If you can find $pq$ you will break the cryptosystem by computing $\frac{p^k q}{pq}=p^{k-1}$.

This questionquestion shows no polynomial algorithm is known to decide if integer is squarefree (all your $\alpha_i=1$).

I believe no polynomial algorithm is known.

According to a paper this is used in at least one cryptosystem:

Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method.

If you can find $pq$ you will break the cryptosystem by computing $\frac{p^k q}{pq}=p^{k-1}$.

This question shows no polynomial algorithm is known to decide if integer is squarefree (all your $\alpha_i=1$).

I believe no polynomial algorithm is known.

According to a paper this is used in at least one cryptosystem:

Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method.

If you can find $pq$ you will break the cryptosystem by computing $\frac{p^k q}{pq}=p^{k-1}$.

This question shows no polynomial algorithm is known to decide if integer is squarefree (all your $\alpha_i=1$).

added 211 characters in body
Source Link
joro
joro
  • 2k
  • 1
  • 12
  • 22

I believe no polynomial algorithm is known.

According to a paper this is used in at least one cryptosystem:

Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method.

If you can find $pq$ you will break the cryptosystem by computing $\frac{p^k q}{pq}=p^{k-1}$.

This question shows no polynomial algorithm is known to decide if integer is squarefree (all your $\alpha_i=1$).

I believe no polynomial algorithm is known.

According to a paper this is used in at least one cryptosystem:

Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method.

If you can find $pq$ you will break the cryptosystem by computing $\frac{p^k q}{pq}=p^{k-1}$.

I believe no polynomial algorithm is known.

According to a paper this is used in at least one cryptosystem:

Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method.

If you can find $pq$ you will break the cryptosystem by computing $\frac{p^k q}{pq}=p^{k-1}$.

This question shows no polynomial algorithm is known to decide if integer is squarefree (all your $\alpha_i=1$).

Source Link
joro
joro
  • 2k
  • 1
  • 12
  • 22

I believe no polynomial algorithm is known.

According to a paper this is used in at least one cryptosystem:

Abstract. We propose a cryptosystem modulo $p^k q$ based on the RSA cryptosystem. We choose an appropriate modulus $p^ k q$ which resists two of the fastest factoring algorithms, namely the number field sieve and the elliptic curve method.

If you can find $pq$ you will break the cryptosystem by computing $\frac{p^k q}{pq}=p^{k-1}$.