Problems with factoring exponents in a prime field
if a, b, m, n ϵ Fp
, with p
is prime
, and
if b = a^m
and c = b^n
, the following should be true:
c == b^n == (a^m)^n == (a^n)^m == a^mn == a^nm
b * c == a^(m + mn) == a^(m * (1+n))
The following code has problems with c == a^mn
, c = a^nm
, b*c == a^(m + mn),
andb*c == a^(m * (1 + n))
.
p = 13
Fp = GF(p)
a = Fp(7)
m = Fp(3)
n = Fp(6)
b = a^m
c = b^n
print("\nGiven b = a^m and c == b^n, in prime field")
print(" Test 1: c == b^n == (a^m)^n == (a^n)^m == a^(m*n) == a^(n*m) ")
print(" where,a: %d, m: %d, n: %d, b: %d, c: %d , a_mn: %d " %(a, m, n, b, c, a^(m* n)))
c == b^n
c == (a^m)^n
c == (a^n)^m
c == a^(m*n)
c == a^(n*m)
a^(m*n) == a^(n*m)
print(" Test 2: b*c == a^m*b^n == a^(m + mn) == a^m(1 + n)")
print(" where, b*c: %d, a^m*b^n: %d, a^(m * ( 1 +n )): %d, a^(m * (1+n)): %d" %( b*c, a^m*b^n, a^(m * ( 1 +n )), a^(m * (1+n
))))
b*c == a^m*b^n
b*c == a^(m + ( m * n ))
b*c == a^(m * (1+n))
a^(m * (1+n)) == a^(m + m*n)
Given b = a^m and c == b^n, in prime field
Test 1: c == b^n == (a^m)^n == (a^n)^m == a^(m*n) == a^(n*m)
where,a: 7, m: 3, n: 6, b: 5, c: 12 , a_mn: 11
True
True
True
False
False
True
Test 2: b*c == a^m*b^n == a^(m + mn) == a^m(1 + n)
where, b*c: 8, a^m*b^n: 8, a^(m * ( 1 +n )): 3, a^(m * (1+n)): 3
True
False
False
True
Have i missed something? Is there a work-around?
m
andn
should be integers or elements ofZmod(p-1)
, but not ofGF(p)
. I'm surprised Sage allowed you raise one element ofGF(p)
to the power of another.