魔方按照一定的顺序转动,是否必然会回到初始状态? hash 值也同理吗?

查看 83|回复 4
作者:tdjnodj   
对于魔方,重复 R U R' U'、R U R' U 等一定方法转动,最终都会回到初始状态。曾经无聊转了好久的 R U,最终也回到了初始状态。于是我产生了一个猜想:魔方按照一定规律重复转动,最终都会回到初始状态。 可惜本人能力有限,无法证明。
由此,我产生了类似的疑问:对于某个 hash 值( hash1 ),通过同样的 hash 算法得出 hash2 ,再用同样的算法得出 hash3 ...... 最终能回到 hash1 吗?最少需要计算几次?
同理,用某个加密算法重复加密某段信息,每次使用同样的密钥,最终能不能得到原来的信息呢?最少需要加密几次?

Hash, 初始, 魔方, 转动

GuuJiang   
魔方的操作构成置换群
后面两个例子都为伪
ThirdFlame   
一楼已经给出了答案。
ElDanno   
hash function 是有分 N-way independent 的,如果你有足够多的线性方程是可以直接算出来下一个的 hash 结果的。这个可以看看著名红色的算法导论的 hash 部分,需要一些概率基础
yk000123   
求证:给定任意一个魔方操作序列,在经过有限次重复操作该序列后,魔方的状态和初始状态相同。
证:f(x) = y ,表示经过 f 操作序列后,魔方状态由 x 变为 y 。假设魔方初始状态为 a ,那么多次操作后,状态的序列为 abcd…。因为魔方的状态总数是有限的,所以这个序列一定会出现重复,可以理解为单链表里存在环。又因为存在 f 的反向操作 g ,使得 g(y) = x ,不可能存在两个不同的魔方状态在经过同一个魔方变换序列后得到同样的新状态,所以单链表的环不可能在中间形成(那样的话两个不同的节点的 next 指向了同一个节点),只能在单链表的头部形成,所以魔方一定会回到初始状态 a 。
这个证明里有几个前置条件:
1. f(x)=y 中 x 和 y 同属于一个有限的集合。
2. f 是可逆的。
hash 和加密都不满足 f 可逆的条件。即使 hash 和加密的状态集合是有限的(包括原始输入),也只能证明环是存在的,并不能证明单链表的头在环里。
您需要登录后才可以回帖 登录 | 立即注册

返回顶部