Возведение в степень с дробной степенью в простом конечном поле

Я пытаюсь возвести в степень конечное поле по простому модулю GF(8191) и не знаю, почему не получаю последовательных результатов.

Я сравниваю эти формулы: k ^((a-1)/a) с k*(1/k)^(1/a) и k*k^ (-1/a), который должен возвращать тот же результат (по крайней мере, в Р)

Код Sage действительно прост:

num, a = 42, 5000

# IN THE REAL DOMAIN:
k = float(num)^(a/(a-1))
print 'k=%f' % k
print 'real (A):', float(k^((a-1)/a)), float(k*((1/k)^(1/a)))
print 'real (B):', float(k^((a-1)/a)), float(k*(1/(k^(1/a))))
print 'real (C):', float(k^((a-1)/a)), float(k*(k^(-1/a)))
print

# NOW IN A FINITE FIELD:
order = 8191 # Field of prime size 2^13-1

# variable inv_a for convenience: 1/a and 1(a-1)
inv_a = inverse_mod(a, order)
inv_a1 = inverse_mod(a-1, order)

k = power_mod(num, a*inv_a1, order) # same "num" as in the Real domain
inv_k = inverse_mod(k, order)       # 1/k

print 'k=%d' % k
print 'finite (A):', power_mod(k, (a-1)*inv_a, order), k*power_mod(inv_k, inv_a, order) % order
print 'finite (C):', power_mod(k, (a-1)*inv_a, order), k*power_mod(k, -inv_a, order) % order

Что выводит:

k=42.031414
real (A): 42.0 42.0
real (B): 42.0 42.0
real (C): 42.0 42.0

k=416
finite (A): 5080 7898
finite (C): 5080 7898

В конечном поле я ожидал, что формулы дадут тот же результат, что и в коммутативном поле действительных чисел, но я получаю 5080 и 7898 вместо 42.

Если вы знаете, почему, спасибо, дайте мне знать. Особенно, если есть проблема с кодом.


exponentiation modular-arithmetic sage
person Eric    schedule 18.11.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Модульная арифметика не применяется к показателям степени, которые представляют собой целые числа, а не конечные элементы поля. Например, в поле GF(3) у нас есть 1 = 4, но 21 ≠ 24 (последний элемент равен 16, то есть 1 по модулю 3). Так что ваша идея получить k1/a путем вычисления обратной величины a в конечном поле и последующего возведения k в эту степень не сработает. Укорениться в конечном поле сложно (если они вообще существуют), что полезно в криптографии.

Sage имеет встроенную функцию для укореняется в конечных полях:

F = GF(8191)
num = F(51)
a = 5000
print num.nth_root(a)

печатает 781. Ваш пример, 42, выдает ошибку, так как это не 5000-я степень любого элемента в этом поле и, следовательно, не имеет 5000-го корня.

Приняв r = num.nth_root(a), теперь мы можем вычислить num(a-1)/a либо путем возведения r в степень (a-1), либо путем деления num на r; то же самое.

print num/r, r^(a-1)

печатает 2643 для обоих.

Корни, вообще говоря, не уникальны. Чтобы получить их все, используйте

print num.nth_root(a, all=True)

который печатает [781, 7997, 1936, 7364, 4453, 7410, 194, 6255, 827, 3738]

person Community    schedule 18.11.2017