I'd like to implement the "Franklin-Reiter Related Message Attack" (see section 4.3 of Boneh's paper). As part of the implementation, I require to compute the GCD of two polynomials over $\mathbb{Z}_N[x]$, where $N$ is a composite integer (whose factorization is unknown).
However, Mathematica's built-in PolynomialGCD allows the GCD to be taken over $\mathbb{Z}_p[x]$, where $p$ is a prime.
How can I compute polynomial GCDs over a ring (with composite characteristic)?
I think this question has similarities with one of my earlier questions (regarding the computation of the inverse of a polynomial in a polynomial ring). Unfortunately, I don't have enough math background to solve this question using the answers in the previous one.
Edit: Example, as per @DanielLichtblau's request:
Let $N = 91$ ($=7\times 13$), and consider the following polynomials:
f[x_] := PolynomialMod[(x + 1) (30 x + 40), 91]
g[x_] := PolynomialMod[(x + 1) (50 x + 60), 91]
Since $(x+1)$ divides both polynomials, I expect it to divide their GCD as well. Simply executing:
PolynomialGCD[f[x], g[x]]
will return 1, as it does not compute the GCD over the ring $\mathbb{Z}_{91}[x]$. Furthermore, running:
PolynomialGCD[f[x], g[x], Modulus -> 91]
returns error PolynomialGCD::modp: Value of option Modulus -> 91 should be a prime number or zero, as the ring's characteristic ($ = 91$) is a composite number, not a prime.
So, the question is, how can I actually compute the GCD of f[x] and g[x] over $\mathbb{Z}_{91}[x]$ using Mathematica?
Edit2: As pointed out above, the factorization of $N$ is unknown. Therefore, the algorithm cannot use the factors of $N$. (However, we know that $N$ is an RSA modulus, meaning that it is of the form $p\times q$, where $p$ and $q$ are primes.)
A general strategy is to use the extended Euclidean algorithm. Example:
r0 = g[x]
(* = 60 + 19 x + 50 x^2 *)
r1 = f[x]
(* = 40 + 70 x + 30 x^2 *)
We now find the inverse of the leading coefficient of r1 over $\mathbb{Z}_N$:
PowerMod[30, -1, 91]
which is 88. Using extended Euclidean algorithm:
r2 = PolynomialMod[r0 - 50*88*r1, 91]
(* = 54 + 54 x *)
Next, the inverse of the leading coefficient of r2 over $\mathbb{Z}_N$ is obtained:
PowerMod[54, -1, 91]
which is 59. Using extended Euclidean algorithm:
r3 = PolynomialMod[r1 - 30*59x*r2, 91]
(* = 40 + 40 x *)
The inverse of the leading coefficient of r3 over $\mathbb{Z}_N$ is 66:
PowerMod[40, -1, 91]
Using extended Euclidean algorithm:
r4 = PolynomialMod[r2 - 54*66*r3, 91]
(* = 0 *)
Therefore, the GCD of f[x] and g[x] equals r3 = 40 + 40 x = 40 (1+x).
Notice that if h[x] is the GCD of f[x] and g[x] over $\mathbb{Z}_N$, and if $a \not\mid N$, then a*h[x] is also a GCD of f[x] and g[x] over $\mathbb{Z}_N$. (That is, the GCD is not uniquely defined.) Consequently, 1+x is a valid GCD as well.
Note: If in any step above, the leading coefficient was not coprime to $N$, its inverse would not exist. In such cases, it seems reasonable to say that the GCD does not exist over the ring.
