Решето Сундарама и его следствия

[dmd]

freeot в сообщении #621388 писал(а):

Если найдется математический аппарат, с помощью которого можно быстро качественно показать имеет ли решение уравнение $z=2xy+x+y$ для заданного $z$ в натуральных $x$ и $y$, то перед нами - самый простой тест на простоту любого числа

Задача факторизация тоже сводится к задаче разрешимости квадратного диофантова уравнения двух неизвестных. Но скорее всего последняя также NP-сложна, как и первая.

freeot в сообщении #621388 писал(а):

Допустим, мы хотим найти простые числа порядка $10^{10000}$ (или $10^{10^{1000000000}}$ - без разницы)

Важно научиться "чувствовать" запредельную грандиозность чисел такого размера. Нет лучше способа "прочувствовать", чем самостоятельно запрограммировать собственный алгоритм. Для этого более всего подходит программируемый калькулятор pari/gp. Если можете программировать в 1С, то тем более сможете и в pari/gp программировать проверочные алгоритмы для своих изысканий.

[SerjeyMinsk]

venco в сообщении #621532 писал(а):

Это говорит лишь о том, что решето Сундарама ничего особенного не представляет по сравнению с решетом Эратосфена. Эта оптимизация приходит в голову самостоятельно практически любому, кто пользуется решетом для поиска простых чисел.

venco, а метод квадратичных вычетов АССА? Или до сих пор в математических кругах форума алгоритм считается модернизацией решета Эратосфена?

[venco]

SerjeyMinsk в сообщении #622123 писал(а):

venco, а метод квадратичных вычетов АССА? Или до сих пор в математических кругах форума алгоритм считается модернизацией решета Эратосфена?

А он разве изменился с тех пор, как его обсудили?

[SerjeyMinsk]

venco в сообщении #622135 писал(а):

А он разве изменился с тех пор, как его обсудили?

Ему изменятся нет нужды. Он вполне себе самодостаточен и уникален.
Вопрос полиномиальности в этом алгоритме мною признан и понят, но уж никак не модернизация. Это современный детерминированный метод квадратичных вычетов с экспоненциальной сложностью.