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

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

(vec1[0])^Binv[0][0], 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[0][0] 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[0][0]
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[0] + X * x[1] + x[2]

result1 = RRR(vec1[0])^Binv[0][0]

edit retag close merge delete

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

( 2018-11-01 08:48:48 -0600 )edit

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

( 2018-11-01 08:56:30 -0600 )edit

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

( 2018-11-01 09:25:04 -0600 )edit

K is GF(2^48) and x is a vector of K elements

( 2018-11-01 09:56:09 -0600 )edit

Sort by » oldest newest most voted

Maybe what you are looking for is

(vec1[0])^Binv[0][0].lift()


which lifts Binv[0][0] 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

( 2018-11-01 12:35:30 -0600 )edit

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).

( 2018-11-01 13:06:09 -0600 )edit

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

( 2018-11-02 06:54:08 -0600 )edit
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.

( 2018-11-02 08:46:12 -0600 )edit

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.

( 2018-11-02 09:56:31 -0600 )edit

Please start posting anonymously - your entry will be published after you log in or create a new account.

## Stats

Asked: 2018-11-01 08:46:34 -0600

Seen: 68 times

Last updated: Nov 01 '18