Quel est l'algorithme le plus rapide pour représenter une prime comme somme de deux carrés?

Question

Je pourrais utiliser deux boucles pour vérifier toutes les combinaisons de deux entiers que moins de prime p, mais il est très inefficace. Y at-il un meilleur algorithme pour aborder ce problème? Une idée?

Où p mod 4 = 1.

Merci,

Answer 1

Vous pouvez essayer d'utiliser le Hermite-Serret algorithme .

Vous pouvez aussi trouver une bonne liste d'algorithmes sur cette page math.se: https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime

Voir en particulier, la réponse de Robin Chapman:

Answer 2

Vous n'avez pas besoin de chercher toutes les combinaisons. Une ébauche d'une implémentation simple naïve serait:

• examiner chaque nombre entier i dans l'intervalle [1..trunc (sqrt (p))].
• Calculer sqrt (p-i ^ 2) et vérifier si elle est un nombre entier. Si oui, vous avez terminé.
• Sinon passez à la suivante i.

Serait-ce pour suffire à vos besoins? Il fonctionne très bien pour les futurs p relativement faible, mais évidemment lent pour le genre de grands nombres premiers utilisés en cryptographie.

Eh bien je pourrais vous 4n + 1 de Fermat Théorème .

Si les ingénieurs logiciels utilisent des outils pour le travail, ton ont des solutions simples. Fonction Mon Mathematica:

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

Exemples:

trouver des solutions pour les quelques premiers nombres premiers p qui sont 1 ou 2 (mod 4).

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

Answer 3

Vous n'avez pas besoin de chercher toutes les combinaisons. Une ébauche d'une implémentation simple naïve serait:

• examiner chaque nombre entier i dans l'intervalle [1..trunc (sqrt (p))].
• Calculer sqrt (p-i ^ 2) et vérifier si elle est un nombre entier. Si oui, vous avez terminé.
• Sinon passez à la suivante i.

Serait-ce pour suffire à vos besoins? Il fonctionne très bien pour les futurs p relativement faible, mais évidemment lent pour le genre de grands nombres premiers utilisés en cryptographie.

Answer 4

Eh bien je pourrais vous 4n + 1 de Fermat Théorème .

Si les ingénieurs logiciels utilisent des outils pour le travail, ton ont des solutions simples. Fonction Mon Mathematica:

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

Exemples:

trouver des solutions pour les quelques premiers nombres premiers p qui sont 1 ou 2 (mod 4).

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