Все простые числа, кроме 2, нечетные. Однако подавляющее большинство нечетных чисел не являются простыми.
Например, возьмите простые числа 3 и 5, их произведение равно 15 и может использоваться как (небезопасный) модуль RSA. 15 — нечетное составное число.
Составной означает, что он имеет несколько простых множителей.
Все натуральные числа больше 1 являются либо простыми, либо составными.
Для безопасного RSA мы используем гораздо большие простые числа. Но принцип тот же. Мы умножаем на большие нечетные простые числа и получаем большой нечетный составной модуль. $n$.
Найти факторы такого большого композита может быть очень сложно. В некоторых случаях сверх того, что в настоящее время возможно. Но сложность факторизации не означает, что факторизации не существует. А ведь с помощью приватного ключа это даже просто.
Таким образом, невозможность факторизации может означать нецелесообразность даже для национального государства, тратящего миллиард долларов. С этим определением RSA 4096 невозможно разложить на множители.
Но если вы имеете в виду невозможное как невозможное, даже с неограниченными вычислениями или футуристическим квантовым компьютером. Чем все модули RSA являются составными и, следовательно, их можно разложить на множители.
Ps - факторизация может быть определена так, чтобы разрешить «факторизацию» простых чисел, что легко просто определить, что оно простое, используя, например, Миллера-Рабина, и если это так, вернуть список, содержащий только входное число.
