Сильные простые числа

Если n - произведение двух простых чисел, p и q, то может понадобиться использовать в качестве p и q сильные простые числа. Такие простые числа обладают рядом свойств, которые усложняют разложение произведения n определенными методами разложения на множители. Среди таких свойств были предложены [1328, 651]:

Наибольший общий делитель p - 1 и q - 1 должен быть небольшим.

И p - 1, и q - 1 должны иметь среди своих множителей большие простые числа, соответственно p' и q'.

И p' - 1, и q' - 1 должны иметь среди своих множителей большие простые числа.

И p + 1, и q + 1 должны иметь среди своих множителей большие простые числа.

И (p - 1)/2, и (q - 1)/2 должны быть простыми [182). (Обратите внимание, при выполнении этого условия выполняются и два первых.)

Насколько существенно применение именно сильных простых чисел, остается предметом продолжающихся споров. Эти свойства были разработаны, чтобы затруднить выполнение ряда старых алгоритмов разложения на множители. Однако самые быстрые алгоритмы одинаково быстры при разложении на множители любых чисел, как удовлетворяющих приведенным условиям, так и нет [831].

Я против специальной генерации сильных простых чисел. Длина простых чисел гораздо важнее их структуры. Более того, сама структура уменьшает случайность числа и может снизить устойчивость системы.

Но все может измениться. Могут быть созданы новые методы разложения на множители, которые лучше работают с числами, обладающими определенными свойствами. В этом случае снова могут потребоваться сильные простые числа. Заглядывайте в журналы по теоретической математике.