multiplicative inverse of a polynomial in a ring

[vpv]

Hello,

I am trying to solve the following equation for y in SAGE:

x*y = 1 (mod z^8+z^4+z^3+z+1)

where

x = x0+x1*z^1+x2*z^2+x3*z^3+x4*z^4+x5*z^5+x6*z^6+x7*z^7
y = ?

x0,...,x7 are elements of GF(2). I do not know their values. I am
searching for y in parametric form i.e. as a polynomial of z of degree
7 with coefficients - some functions of x0,...,x7.

I define in SAGE:

P.<x0,x1,x2,x3,x4,x5,x6,x7> = BooleanPolynomialRing(8, order='lex')
Z.<z> = PolynomialRing(P)

I try to do the following in SAGE

y = inverse_mod(x0+x1*z^1+x2*z^2+x3*z^3+x4*z^4+x5*z^5+x6*z^6+x7*z^7,
z^8+z^4+z^3+z+1)

but it does not work.

Alternatively, I try to define a ring of univariate polynomials of z
with coeffients in P, every element of which is reduced (mod
z^8+z^4+z^3+z+1), but I am not able to get the right syntax to do this
in SAGE.

Any help is appreciated.

Thanks!

[David Joyner]

It seems you should be able to represent multiplication by y as a
matrix equation,
which you might have luck inverting.

[John Cremona]

You could define GF(2^8) using your polynomial as modulus, then define
the polynomial ring S in 8 variables x0,...,x7 over that, write x as
an element in that ring. The inverse of x is also x^254, but you
want to evaluate this with the side conditions xi^2=xi. So take the
quotient of S by those 8 relations first. This might be better
handled by the PlyBori package, but I am not familiar with that.

I tried this and it worked. The output (your y) starts like this,
where xibar is your xi and a is your z.

(a^6 + a^4 + a)*x0bar*x1bar*x2bar*x3bar*x4bar*x5bar*x6bar + (a^7 + a^5
+ a^2)*x0bar*x1bar*x2bar*x3bar*x4bar*x5bar*x7bar + (a^6 + a^4 + a +
1)*x0bar*x1bar*x2bar*x3bar*x4bar*x6bar*x7bar + (a^7 + a^5 + a^2 +
a)*x0bar*x1bar*x2bar*x3bar*x5bar*x6bar*x7bar + (a^2 +
1)*x0bar*x1bar*x2bar*x4bar*x5bar*x6bar*x7bar + (a^6 + a^4 +
a^3)*x0bar*x1bar*x3bar*x4bar*x5bar*x6bar*x7bar + (a^7 + a^5 +
a^4)*x0bar*x2bar*x3bar*x4bar*x5bar*x6bar*x7bar + (a^5 + a^3 +
1)*x1bar*x2bar*x3bar*x4bar*x5bar*x6bar*x7bar + (a^7 + a^6 +
a^2)*x0bar*x1bar*x2bar*x3bar*x4bar*x5bar + (a^7 + a^5 + a^2 +
1)*x0bar*x1bar*x2bar*x3bar*x4bar*x6bar + (a^7 +
a^4)*x0bar*x1bar*x2bar*x3bar*x5bar*x6bar + (a^6 + a^4 + a^2 +
a)*x0bar*x1bar*x2bar*x4bar*x5bar*x6bar + (a^7 + a^5 +
a)*x0bar*x1bar*x3bar*x4bar*x5bar*x6bar + (a^7 + a^6 + a^4 +
a)*x0bar*x2bar*x3bar*x4bar*x5bar*x6bar + (a^6 + a^5 +
a)*x1bar*x2bar*x3bar*x4bar*x5bar*x6bar + (a^7 + a^4 + a +
1)*x0bar*x1bar*x2bar*x3bar*x4bar*x7bar + (a^6 + a^4 +
1)*x0bar*x1bar*x2bar*x3bar*x5bar*x7bar + (a^6 + a^4 + a^3 + a +
1)*x0bar*x1bar*x2bar*x4bar*x5bar*x7bar + (a^7 + a^6 + a^3 +
a^2)*x0bar*x1bar*x3bar*x4bar*x5bar*x7bar + (a^6 + a^4 + a^3 + a^2 + a
+ 1)*x0bar*x2bar*x3bar*x4bar*x5bar*x7bar + (a^7 + a^6 + a^4 + a^3 +
a^2 + a + 1)*x1bar*x2bar*x3bar*x4bar*x5bar*x7bar + (a^5 + a^4 + a^3 +
a^2 + 1)*x0bar*x1bar*x2bar*x3bar*x6bar*x7bar + (a^6 + a^4 +
a^2)*x0bar*x1bar*x2bar*x4bar*x6bar*x7bar +
(a^6)*x0bar*x1bar*x3bar*x4bar*x6bar*x7bar + (a^7 + a +
1)*x0bar*x2bar*x3bar*x4bar*x6bar*x7bar + (a^6 +
a^3)*x1bar*x2bar*x3bar*x4bar*x6bar*x7bar +

John Cremona

2008/5/28 David Joyner <wdjo...@gmail.com>:

[vpv]

Thank you very much for your reply!

The output for y which you sent below is exactly what I am looking
for. Can you please paste also the SAGE definitions which you use to
construct the field GF(2^8) (mod z^8+z^4+z^3+z+1), the polynomial ring
S, and finally the quotient of S by the 8 relations (x0^2=x0,
x1^2=x1, ..., x7^2=x7)?

Here is how I try to define the above constructions, but as my SAGE
programming is not very good I don't seem to get it right:

Z =
IntegerModRing(2^8)
R =
PolynomialRing(F256,'z');
S = R.quotient(z^8+z^4+z^3+z+1,
'x');
P.<x0,x1,x2,x3,x4,x5,x6,x7> =
PolynomialRing(S)

When I try to construct an element of P like this:

b = (x0+x1*z^1+x2*z^2+x3*z^3+x4*z^4+x5*z^5+x6*z^6+x7*z^7)

I get the following error in SAGE:

"TypeError: unsupported operand parent(s) for '*': 'Multivariate
Polynomial Ring in x0, x1, x2, x3, x4, x5, x6, x7 over Univariate
Quotient Polynomial Ring in x over Integer Ring with modulus z^8 + z^4
+ z^3 + z + 1' and 'Univariate Polynomial Ring in z over Boolean
PolynomialRing in x0, x1, x2, x3, x4, x5, x6, x7'"

Thanks for your help!

> 2008/5/28 David Joyner <wdjoy...@gmail.com>:

>
>
>
> > It seems you should be able to represent multiplication by y as a
> > matrix equation,
> > which you might have luck inverting.
>

[John Cremona]

Here is what I was talking about in my first reply. It does not do
exactly what you want, in two ways:
(1) the expression for y output is a polynomial in the xi with
coefficients pollys in z, while I expect you hoped that would be the
other way round;
(2) The expression x*y does not simplify to 1, but it does satisfy (x*y)^2==x*y.

If someone else can suggest how to deal with (2) this might make a
nice worked examples for the documentation.

John

# Define the field with 2 elements and the polynomial ring over it
# with variable Z

F2=GF(2)
R.<Z>=PolynomialRing(F2)

# Define the polynomial f and check that it is irreducible:

f=Z^8+Z^4+Z^3+Z+1
assert f.is_irreducible()

# Define the field GF(2^8) with generator z satisfying f as its
# minimal polynomial:

F256.<z>=GF(256,'z',f)

# Define a polynomial ring in 8 variables over F2

S=PolynomialRing(F256,8,'x')

# Quotient out by the ideal containing xi^2-xi for all 8 generators.
# The variables in the quotient are called x0,x1,...,x7

I=S.ideal([xi^2-xi for xi in S.gens()])
Sbar.<x0,x1,x2,x3,x4,x5,x6,x7>=S.quo(I)

# Define the "generic" element x:

x = x0+x1*z^1+x2*z^2+x3*z^3+x4*z^4+x5*z^5+x6*z^6+x7*z^7

# If all is well this should be true:

assert x^256 == x

#

y = x^254

# ideally, we should have x*y = x^255 = 1, but unfortunately not:

assert not x*y==1
assert not x^255==1

# However

one = x*y
assert one^2==one

2008/5/28 vpv <un3_1...@yahoo.com>:

[vpv]

Thanks a lot for the code and the detailed explanations, John! I got
the code running, and it computes the y-s which I need.

About (1) and (2):

> (1) the expression for y output is a polynomial in the xi with
> coefficients pollys in z, while I expect you hoped that would be the
> other way round;

Yes. Indeed I need the polynomial coefficients to be expressions of xi-
s. Maybe I can try to fix this with some symbolic manipulations. As to
(2):

> (2) The expression x*y does not simplify to 1, but it does satisfy (x*y)^2==x*y.
>

I wonder if this means that the expression I get for y is not in fact
the multiplicative inverse of x mod the polynomial?

Thank you very much for your time and help!

> 2008/5/28 vpv <un3_14ql...@yahoo.com>:

[John Cremona]

I know the answer to (2): the exporession you get from x*y is a
polynomial in the xi which can be expressed as 1-prod(xi-1) which is 1
if not all the xi are nonzero (i.e. if x is nonzero) and 0 if all xi
are zero (i.e. if x=0). Which is exactly right, when you think about
it.

To force x to represent an arbitray nonzero element of the field (as
opposed to just an arbitrary element) you could add the element expr-1
to the generators of the ideal used to define S, where expr is the
above expression.

John

2008/5/30 vpv <un3_1...@yahoo.com>: