Как получить вектор коэффициентов многочлена PolyBoRi в Sage - PullRequest
Новая
       12

Как получить вектор коэффициентов многочлена PolyBoRi в Sage

0 голосов
/ 18 ноября 2018

Я пытаюсь использовать SageMath для чего-то, что включает в себя много манипуляций с логическими полиномами.

Вот несколько примеров того, что такое вектор коэффициентов: 

 x0*x1*x2 + 1 has coefficient vector 10000001
  x1 + x0 + 1 has coefficient vector 11100000  
      x1 + x0 has coefficient vector 01100000

(x0 - младший значащий бит.)

Проблема в том, что API Sage, похоже, не поощряет прямое манипулирование мономами или векторами коэффициентов, возможно, потому что структуры данных, которые он использует внутри, являются ZDD вместо битовых массивов. 

sage: P
x0*x1*x2 + x0*x1 + x0*x2 + x0 + x1*x2 + x1 + x2 + 1
sage: list(P.set())
[x0*x1*x2, x0*x1, x0*x2, x0, x1*x2, x1, x2, 1]
sage: P.terms()
[x0*x1*x2, x0*x1, x0*x2, x0, x1*x2, x1, x2, 1]

В этом коде, похоже, проблема в том, что порядковый номер противоположен тому, что можно ожидать; что будет с х0, являющимся наименее значимым битом.

Проблема на самом деле больше, чем это. Например: 

#!/usr/bin/env python
from sage.all import *
from sage.crypto.boolean_function import BooleanFunction

# "input_str" is a truth table. 
# Returns a polynomial that has that truth table.
def truth_str_to_poly(input_str):
    # assumes that the length of input_str is a power of two
    num_vars = int(log(len(input_str),2))
    truth_table = []
    # convert string to list of ints expected by BooleanFunction 
    for i in list(input_str):
        truth_table.append(int(i))
    B = BooleanFunction(truth_table)
    P = B.algebraic_normal_form()
    return P

# Return the polynomial with coefficient vector 1,1,...,1.
# (This is neccessary because we can't directly manipulate coef. vectors.)
def super_poly(num_vars):
    input_str = ["0"]*(2**num_vars)
    input_str[0] = "1"
    input_str = "".join(input_str)
    return truth_str_to_poly(input_str)

# Return the coefficient vector of P.
# This is the function that is broken.
def poly_to_coef_str(P, num_vars):
    res = ""
    #for i in super_poly(num_vars).terms():
    for i in list(super_poly(num_vars).set()):
        res += str(P.monomial_coefficient(i))
    return res

num_vars = 3
print(super_poly(num_vars).monomials())

# This should have coefficient vector "01000000" = x0
input_poly = "01010101"
P = truth_str_to_poly(input_poly) # Gives correct result
res = poly_to_coef_str(P, 3)
print(" in:"+input_poly)
print("out:"+res)

Выход: 

[x0*x1*x2, x0*x1, x0*x2, x0, x1*x2, x1, x2, 1]
 in:01010101
out:00010000

Это означает, что это не просто неправильный порядок байтов, это как-то непоследовательно обрабатывает начальное значение переменных.

Есть ли лучший способ сделать это?

...