この決定問題のための多項式時間アルゴリズムはありますか？

Question

$ m $ の係数は、 $> $ $ 1 $ ですが、 $ <$ $ m $ です。 $ n $ ？

虚偽の結果例

$ n $ = 8

$ m $ = 16

1,2,4,8,16

$ n $ の要因ではない整数はありません。 $> $ < SPAN CLASS="math-container"> $ 1 $ ですが $ m $

真の結果例

$ n $ = 2

$ m $ = 26

1,2,13,26

$ 13 $ があります。これは、 $ n $ の要因ではありません> 1しかし $ m $

質問

私は疑似多項式の解を見つけましたが、入力の長さにこの問題に対する多項式の解はありますか？

Answer 1

これは整数ファクタリングの問題として難しい（単に $ n $ 、または $ m $ ）。ファクタリングのための多項式 - タイムアルゴリズムがあるかどうかは有名なオープン問題ですが、そのようなアルゴリズムがない可能性が高いと広く信じられています。