algorithm - 如何计算位向量的排列？

Question

给定一个位向量 V = (101101) 和一个置换函数：F(x) = (a*x + b) mod p。其中a和b是随机数，p是素数。如何计算向量 V 的排列？F(x) 是否将 V 作为一个完整的值，或者我应该使用 V 中的每一位作为函数的 ax？

Answer 1

是的，为了置换位向量，然后取每个位并对其应用置换函数。

Answer 2

在该定义中，置换函数为向量中的每个条目提供新位置。例如对于 a=2, b=0, p=7，函数给出 {0,1,2,3,4,5,6}->{0,2,4,6,1,3,5}。

使用此函数，可以置换 7 个元素的任何向量，将 {a,b,c,d,e,f,g} 转换为 {a,c,e,g,b,d,f}。

这仅在向量的大小等于素数 p 时才有效。因此，对于位向量，将位置 n 处的每个元素移动到位置 a*n+b mod p。

这也适用于非素数 p，只要 a 和 b 与 p 互质。