Дата публикации: 2020

Дата публикации в реестре: 2020-10-01T12:54:45Z

Аннотация:

Изучается генерическая сложность проблемы представимости натуральных чисел суммой двух квадратов. Эта проблема, восходящая ещё к Ферма и Эйлеру, тесно связана с проблемами факторизации целых чисел и распознавания квадратичности вычетов по составным модулям, для решения которых не известно эффективных алгоритмов. Доказывается, что, при условии трудноразрешимости этой проблемы в худшем случае и P = BPP, для её решения не существует полиномиального сильно генерического алгоритма. Сильно генерический алгоритм решает проблему не на всём множестве входов, а на подмножестве, последовательность относительных плотностей которого при увеличении размера экспоненциально быстро сходится к 1.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2020. № 13. С. 111-113

Другие версии документа

О генерической сложности проблемы представимости натуральных чисел суммой двух квадратов