Ask Your Question

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

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

Lujmina gravatar image

updated 2018-11-01 09:56:36 -0600

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');
#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():
RRR = R.quotient(IP3,'Y')
vec1 = X^2 * x[0] + X * x[1] + x[2]

result1 = RRR(vec1[0])^Binv[0][0]
edit retag flag offensive close merge delete


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

tmonteil gravatar imagetmonteil ( 2018-11-01 08:48:48 -0600 )edit

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

Lujmina gravatar imageLujmina ( 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.

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

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

Lujmina gravatar imageLujmina ( 2018-11-01 09:56:09 -0600 )edit

1 answer

Sort by ยป oldest newest most voted

answered 2018-11-01 12:27:53 -0600

Maybe what you are looking for is


which lifts Binv[0][0] to an integer before exponentiating.

edit flag offensive delete link 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

Lujmina gravatar imageLujmina ( 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).

rburing gravatar imagerburing ( 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

Lujmina gravatar imageLujmina ( 2018-11-02 06:54:08 -0600 )edit

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.

rburing gravatar imagerburing ( 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.

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

Your Answer

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

Add Answer

Question Tools

1 follower


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

Seen: 64 times

Last updated: Nov 01