Возведение в степень матрицы конечного поля Python

Есть ли простой способ вычисления (особенно степени/возведение в степень) с матрицами, элементы которых являются целыми числами из конечного поля или, по крайней мере, произвольными матрицами целочисленной точности с поддержкой оператора%?

Например, допустим, у нас есть матрица

A = 1 1
    1 0

и хотите вычислить что-то вроде (A**100) % 1000, как этого добиться?

Я пробовал numpy, но проблема в том, что он использует типы данных с фиксированной точностью, поэтому он быстро переполняется... Затем я попробовал sympy, поскольку он поддерживает произвольную целочисленную точность, но, похоже, он не поддерживает операции с конечными полями (кроме обратного) ...


python matrix exponentiation modulo arbitrary-precision
person Community    schedule 17.04.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Это может показаться излишним, но в Sage есть все, что вам нужно (и даже больше). Это программное обеспечение на основе Python, но оно очень большое (~1,2 ГБ загрузки). Вы можете использовать sage --preparse script.sage для создания файла Python.

Существует даже SO-подобный сайт контроля качества https://ask.sagemath.org/questions/, который специализируется на шалфее.

Пример вашего кода может быть:

m = Matrix(GF(5), [[1, 1], [1, 0]])
power = m^100

Я использовал GF(5), поскольку GF(1000) не является конечным полем. Также есть некоторые различия, например, возведение в степень может быть выполнено либо с помощью x**y, либо эквивалентно x^y.

person kyticka    schedule 17.04.2017