A function over finite rings is a function from a ring E_q~n to a ring E_r, where E_k is ZZ/kZZ. These functions are well used in cryptography: cipher design, hash function design and in theoretical computer science. In this paper, we are especially interested in symmetric functions. We give practical ways of computing their ANF and their Walsh Spectrum in O ( ( _(q-1)~(n+q-1))~2 ) using linear algebra. Thus, we achieve a better complexity both in time and memory than the fast Fourier transform which is in O(q~n n log(q)).
展开▼
机译：有限环上的函数是从环E_q_n到环E_r的函数，其中E_k为ZZ / kZZ。这些函数在密码学中得到了很好的使用：密码设计，哈希函数设计和理论计算机科学。在本文中，我们对对称函数特别感兴趣。我们给出了使用线性代数在O（（_（q-1）〜（n + q-1））〜2）中计算其ANF和沃尔什谱的实用方法。因此，与O（q〜n n log（q））中的快速傅里叶变换相比，我们在时间和内存上都具有更好的复杂性。
展开▼
