Какой самый быстрый алгоритм для представления простого числа в виде суммы двух квадратов?

Question

Я мог бы использовать два цикла для проверки всех комбинаций двух целых чисел, которые меньше p простого числа, но это очень неэффективно.Есть ли лучший алгоритм для решения этой проблемы?Любая идея?

Где p mod 4 = 1.

Спасибо,

Answer 1

Вы можете попробовать использовать алгоритм Эрмита-Серре .

Вы также можете найти хороший список алгоритмов на этой странице math.se: https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime

См. Особенно, ответ Робина Чепмена: https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime/5883#5883

Answer 2

Вам не нужно искать все комбинации.Примерная схема простой наивной реализации будет выглядеть следующим образом:

• Рассмотрим каждое целое число i в диапазоне [1..trunc (sqrt (p))].
• Рассчитать sqrt (pi^ 2) и проверьте, является ли оно целым числом.Если это так, то все готово.
• Если нет, переходите к следующему. I.

Будет ли этого достаточно для ваших нужд?Он будет хорошо работать при относительно малых значениях p, но, очевидно, будет медленным для разновидностей больших простых чисел, используемых в криптографии.

Answer 3

Хорошо, я мог бы порекомендовать вам перечитать Теорема Ферма 4n + 1 .

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

P[p_] := Reduce[-p + x^2 + y^2 == 0, {x, y}, Integers]

Примеры:

Поиск решений для первых нескольких простых чисел p, равных 1 или 2 (мод 4).

P /@ {2, 5, 13, 17, 29, 37, 41, 53, 61}