# How to solve raising a polynomial to the power of a number mod something

I want to raise the polynomial vec1 to the power of a number mod x

(vec1)^Binv, however when I do that, I receive the following message:

unsupported operand type(s) for &: 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp' and 'int'

When I change Binv to be an integer, everything works fine, however, this is not what I want to achieve. Is there any workaround to this?

Z3 = Integers(2^(e*m)-1);
B = matrix(ZZ,2,2);
F11 = 50;
F12 = 24;
F21 = 7;
F22 = 88;
B[0,0] = 2^F11;
B[0,1] = 2^F12;
B[1,0] = 2^F21;
B[1,1] = 2^F22;

#print B
B_mod = B.mod(2^(e*m)-1)
#print B_mod

Binv = matrix(Z3,2,2);
Binv = B_mod.inverse();

R = PolynomialRing(K,'X');
R.inject_variables();
#Find irreducible polynomial of degree 3
while True:
c = K.random_element();
d = K.random_element();
f = K.random_element();

IP3 = X^3 + c*X^2 + d*X + f;
if IP3.is_irreducible():
break;
RRR = R.quotient(IP3,'Y')
RRR.inject_variables()
vec1 = X^2 * x + X * x + x

result1 = RRR(vec1)^Binv

edit retag close merge delete

Could you please provide the code for constructing vec1 and Binv ?

Edited with the code. Sorry for my code being very messy

What is K, x? Also, please format your code by selecting it and pressing the 'code' (101010) button.

Sort by » oldest newest most voted Maybe what you are looking for is

(vec1)^Binv.lift()


which lifts Binv to an integer before exponentiating.

more

It doesn't help, I want to be able to keep the exponent modulo such that it reduces when I multiply it with its inverse, as in Diffie Helman

The only way I know in which $x^{a \text{ mod } n}$ makes sense is if $x$ has multiplicative order dividing $n$ (so that $x^n = 1$ and hence $x^{a + kn} = x^{a}x^{kn} = x^{a}(x^n)^k = x^{a}\cdot 1 = x^a$, meaning that the "mod" notation in the exponent is well-defined), so in that case you don't have to worry about "keeping the exponent modulo $n$". If $x \in GF(2^{48})$ then exponents modulo $2^{48} - 1$ are well-defined in this way, so there is no harm in lifting to integers (and in Sage it is necessary, to avoid type errors).

It is not this: (x^n)^k that I am afraid of. I want a and b to be of the following form: a*b = 1 mod 2^96-1 such that when i do (x^a)^b, it will give me x. But if I do the lift on b, then it wont maintain the property that it is the inverse of a in mod 2^96-1

1

What you want to do in your latest comment makes mathematical sense only if the multiplicative order of x divides $2^{96} - 1$ (so that there is no harm in lifting). If this is not the case then you are doing something very strange, redefining exponentiation in an inconsistent way. More likely you are misunderstanding whatever source material you are trying to implement.

Thanks for letting me know, solved it :) made my understand that I should look a bit more at my logic. I will mark this as the solution, however, the inverse was not the issue here.