Comment puis-je vérifier si 2 polynômes sont congruents modulo (h(x), n) ?

Question

J'essaie actuellement d'écrire ma propre implémentation de l'algorithme AKS. Le pseudo-code de cet algorithme (tiré directement de l'article "PRIMES is in P") est le suivant ici .

Ce qui me pose problème, c'est le code qui se trouve à l'intérieur de l'élément d'information. if à la ligne 5. Cela nous oblige à vérifier si

(x+a)^n = x^n + a ( mod x^r - 1, n )

Quelqu'un sait-il comment je pourrais faire cela (en python) ? Je crois que cette congruence est équivalente à dire qu'il existe des polynômes q(x) et r(x) tels que

f(x) = g(x) + (x^r - 1) * q(x) + n * r(x)

bien que je n'en sois pas certain.

J'ai essayé de reproduire ceci if en utilisant python et le paquet sympy avec le code suivant

if(sym.div(sym.div(mod_zero, x**r - 1)[1], n)[1] == 0):
     print("Congruent")

Answer 1

Votre interprétation f(x) = g(x) + (x^r - 1) * q(x) + n * r(x) n'est pas incorrect, si g est compris comme étant nul, et si q et r ont des coefficients entiers. Mais il s'agit en fait de deux étapes : prendre le reste de la division d'un polynôme par (x^r - 1) et en appliquant ensuite mod n aux coefficients.

En termes de SymPy, la comparaison est la suivante

trunc(rem((x + a)**n -(x**n + a), x**r - 1), n) == 0

donde rem trouver le reste du polynôme, et trunc prend des coefficients mod n. Exemples :

x = poly("x")  
n = 35
r = 29
a = 7
trunc(rem((x + a)**n - (x**n + a), x**r - 1), n)

sorties Poly(14*x**25 + 7*x**10 - 7*x**5 + 14*x - 14, x, domain='ZZ')

tandis que, en remplaçant 35 par 31, on obtient Poly(0, x, domain='ZZ') qui passe le == 0 test.

Accélération

Une façon d'optimiser est d'appliquer également trunc antes de rem pour rendre les coefficients plus petits avant la division.

trunc(rem(trunc((x + a)**n - (x**n + a), n), x**r - 1), n)

Cela aide un peu. Mais une accélération plus substantielle peut être obtenue en utilisant des routines de bas niveau du module "galoistools". Elles opèrent avec des coefficients sous forme de listes, comme ceci : [1, a] est x + a .

from sympy.polys.galoistools import gf_lshift, gf_sub, gf_add_ground, gf_pow, gf_rem 
n = 35
r = 29
a = 7
f1 = gf_pow([1, a], n, n, ZZ) # (x + a)**n
f2 = gf_add_ground(gf_lshift([1], n, ZZ), a, n, ZZ) # x**n + a
g = gf_add_ground(gf_lshift([1], r, ZZ), -1, n, ZZ) # x**r - 1
print(gf_rem(gf_sub(f1, f2, n, ZZ), g, n, ZZ))

imprime [14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 0, 28, 0, 0, 0, 14, 21] ce qui est en accord (modulo 35) avec le résultat précédent.

Le polynôme zéro est [] dans cette représentation : ainsi, le test pourrait être aussi simple que

if gf_rem(gf_sub(f1, f2, n, ZZ), g, n, ZZ):
    print("Composite")    # [] is falsy, other lists are truthy

Le code de galoistools est moins élégant, mais il est un ordre de grandeur plus rapide.