Существует ли алгоритм полиномиального времени для решения этой задачи?

Question

Есть ли какой-то фактор в $М$ это $>$ $1$, но $<$ $М$ это НЕ является фактором $N$?

Пример Ложного результата

$N$ = 8

$М$ = 16

1, 2, 4, 8, 16

Не существует целого числа, которое НЕ было бы множителем $N$ это $>$ $1$ но < $М$

Пример Истинного результата

$N$ = 2

$М$ = 26

1, 2, 13, 26

Существует целое число $13$ который НЕ является фактором $N$ это > 1 , но < $М$

Вопрос

Я нашел псевдополиномиальное решение, но существует ли полиномиальное решение для этой задачи по длине входных данных?

Answer 1

Это сложно, так как задача целочисленного факторинга (просто возьмите $N$ равняться 2 или случайному простому числу, не имеющему никакого отношения к $М$).Существует ли алгоритм факторинга с полиномиальным временем - известная открытая проблема, но широко распространено мнение, что такого алгоритма, скорее всего, не существует.