RSA for polynomials in MAGMA

Pick two irreducible polynomials $p,q$ over a finite field $F$ and let $n = pq$. Form the quotient ring $R:=F[x]/nF[x]$.

> F:=GF(3);
> P<x> := PolynomialRing(F);
> p:=ConwayPolynomial(3,5);
> q:=ConwayPolynomial(3,4);
> n:=p*q;
> n;
x^9 + 2*x^8 + x^5 + 2*x^4 + 2*x^3 + x + 2
> I:=ideal<P|n>;
> R:=quo<P|I>;
> IsFinite(R);
true 19683

Next, we need to find out how many elements are in the group $(F[x]/nF[x])^\times$. Denote this number by $N$. Note that this is not the Euler phi function value of the integer $\vert F[x]/nF[x]\vert$.

> f:=x^12+x+1;
> f:=R!f;
> IsUnit(f);
true
> L:=[f:f in R];
> U:=[f:f in R|IsUnit(f)];
> #U;
19360
> #R;
19683
> EulerPhi(#R);
13122
> Factorization(#U);
[ <2, 5>, <5, 1>, <11, 2> ]
>

Now, as with RSA, pick a secret encryption exponent, $e$. Let $d$ denote its inverse mod $N$. This is the secret decryption exponent. Pick a message for Alice to send to Bob, say $x^4+x+1 \in R=F[x]/nF[x]$. (The message must have degree less than that of $n$.) MAGMA uses a capital $X$ to distinguish elements of $F[x]$ and those of its quotient $R$.

Alice sends $c=m^e$ to Bob. Bob decrypts Alice's cipher-text by using that fact that

$$c^d=(m^e)^d=m^{ed}=m^{1+kN}=m(m^{N})^k=m.$$

> e:=7;
> R<X>:=quo<P|I>;
> 
> m:=X^4+X+1;
> m in R;
true
> c:=m^e;
> c;
X^8 + 2*X^6 + 2*X^5 + 2*X^4 + 2*X
> Z_N:=ResidueClassRing(#U);
> 
> E:=Z_N!e;
>  d:=E^-1;
> d;
11063
> D:=Integers()!d;
> D;
11063
> c^D;
X^4 + X + 1
> m;
X^4 + X + 1

Exercise 2.14.5 (RSA for polynomials)   Using $m=x^5+x^3+2$ and the same $e$, find $d$ and $c$ as above and check that $c^d=m$.

Exercise 2.14.6   Using R<x>:=PolynomialRing(Integers(),1);, p:=x^8-1, and Factorization(p);, find the factorization over the integers of $p$.

Exercise 2.14.7   Using R<x>:=PolynomialRing(GF(2),1);, p:=x^8-1, and Factorization(p);, find the factorization over the integers of $p$.

To evaluate $f(x)=x^2-1$ at $x=12$ in MAGMA, use the Evaluate(f,x0); command. For example, Using R<x>:=PolynomialRing(Integers(),1);, p:=x^8-1, and Evaluate(f,3); evaluates $3^8-1$ in MAGMA.

In MAGMA, type R<x>:=PolynomialRing(Integers());, a(x)^n mod m(x); to compute $a(x)^n \ {\rm mod}\ m(x)$. For example, R<x>:=PolynomialRing(Integers());

x^17 mod (x^2+1);

returns $x$.

Exercise 2.14.8   Verify Example 2.5.4.

In MAGMA, R<x>:=PolynomialRing(Integers(),1); and the command C:=CompanionMatrix(p); gives, for a monic polynomial $p$ of degree $n$ over a ring $R$, the companion matrix $C$ for $p$ as an element of $M_n(R)$.

Exercise 2.14.9   Verify the multiplication table in Example 2.7.5.

In MAGMA, first type R<x,y,z>:=PolynomialRing(Integers(),3);. The leading monomial can be computed using the LeadingTerm command. For example,

p:=320*x*y^2+9*x*y^4-96*x*y^4*z^2;

and LeadingTerm(p); returns $-96xy^4z^2$.

> L:=[x^i*y^j : i in [0..4],j in [0..4]];
> R<x,y>:=PolynomialRing(GF(5),2);       
> L:=[x^i*y^j : i in [0..4],j in [0..4]];
> f:=function(a,b)
function> if a lt b then return -1; end if;
function> if a eq b then return 0; end if;
function> if a gt b then return 1; end if;
function> end function;
> L;        
[
    1,
    x,
    x^2,
    x^3,
    x^4,
    y,
    x*y,
    x^2*y,
    x^3*y,
    x^4*y,
    y^2,
    x*y^2,
    x^2*y^2,
    x^3*y^2,
    x^4*y^2,
    y^3,
    x*y^3,
    x^2*y^3,
    x^3*y^3,
    x^4*y^3,
    y^4,
    x*y^4,
    x^2*y^4,
    x^3*y^4,
    x^4*y^4
]
> Sort(L,f);
[
    1,
    y,
    y^2,
    y^3,
    y^4,
    x,
    x*y,
    x*y^2,
    x*y^3,
    x*y^4,
    x^2,
    x^2*y,
    x^2*y^2,
    x^2*y^3,
    x^2*y^4,
    x^3,
    x^3*y,
    x^3*y^2,
    x^3*y^3,
    x^3*y^4,
    x^4,
    x^4*y,
    x^4*y^2,
    x^4*y^3,
    x^4*y^4
]
(2, 6)(3, 11)(4, 16)(5, 21)(8, 12)(9, 17)(10, 22)(14, 18)(15, 23)(20, 24)
>

Exercise 2.14.10   Rewrite the following polynomial, ordering its terms according to the lex, grlex and grevlex ordering and give $LM(f)$, $LT(f)$ and multideg$(f)$ in each case.

$$f(x,y,z)=2x^2y^8-3x^5yz^4+xyz^3-xy^4.$$

Exercise 2.14.11   Find the leading terms of some polynomials of your own choosing.

Exercise 2.14.12   Let $B=(x^2y-z,xy-1)$ and $f=x^3-x^2y-x^2z+x$. a) Compute the remainder of dividing $f$ by $B$ for both the lex and the grlex ordering.
b) Repeat part a) with the order of the pair $B$ reversed.

Exercise 2.14.13   Compute the S-polynomial for $x^4y-z^2$ and $3xz^2-y$ with respect to the lex ordering with $x>y>z$ and for $z>y>x$.

Exercise 2.14.14   Let $F$ be a field and let $R=F[x,y]$. Let $<$ denote the lexicographical order with $x >y$. Let $f(x,y)=x^2y+xy^2+y^2$, $f_1(x,y)=xy-1$, and $f_2(x,y)=y^2-1$. Find the normal form of $f$ mod $F=\{f_1,f_2\}$. (Use NormalForm.)

Exercise 2.14.15   Find equations of the curve parameterized by $(t^2,t,1+t)$ using Grobner bases.

R<x>:=PolynomialRing(Integers(),1); and the command C:=CompanionMatrix(p); gives, for a monic polynomial $p$ of degree $n$ over a ring $R$, the companion matrix $C$ for $p$ as an element of $M_n(R)$.

Exercise 2.14.16   Verify the multiplication table in Example 2.7.5.

Exercise 2.14.17   Let $I=(x^5+y^4+z^3-1,x^3+y^2+z^2-1)$. Compute a Gröbner basis for $I$ with respect to the lex, grlex, and grevlex orderings. Compare.
Repeat the calculations for $I=(x^5+y^4+z^3-1,x^3+y^3+z^2-1)$ (only one exponent changed!)