In this paper, we present an average-case efficient algorithm to resolve the problem of determining whether two Boolean functions in trace representation are identical. Firstly, we introduce a necessary and sufficient condition for null Boolean functions in trace representation, which can be viewed as a generalization of the well-known additive Hilbert-90 theorem. Based on this condition, we propose an algorithmic method with preprocessing to address the original problem. The worst-case complexity of the algorithm is still exponential; its average-case performance, however, can be improved. We prove that the expected complexity of the refined procedure is O (n ), if the coefficients of input functions are chosen i.i.d. according to the uniform distribution over F _(2~(n )); therefore, it performs well in practice.
展开▼
机译：在本文中，我们提出了一种平均情况有效的算法来解决确定跟踪表示中的两个布尔函数是否相同的问题。首先，我们为跟踪表示中的布尔布尔函数引入了充要条件，这可以看作是众所周知的加法Hilbert-90定理的推广。基于这种情况，我们提出了一种带有预处理的算法方法来解决原始问题。该算法在最坏情况下的复杂度仍然是指数级的。但是，可以提高其平均性能。我们证明，如果输入函数的系数为i.i.d，则精炼过程的预期复杂度为 O（ n）。根据 F _（2〜（ n））上的均匀分布;因此，它在实践中表现良好。
展开▼
