31 Mar
2016
31 Mar
'16
1:01 p.m.
On Thu, Mar 31, 2016 at 11:31 AM, Warren D Smith <warren.wds@gmail.com> wrote:
Re my conjecture about the hardness of cycle-membership (and cycle cardinality presumably also is hard) here is a specific case. Let x be a 64-bit unsigned integer with arithmetic mod 2^64. What is the cycle length of x := Rotate(3141592653589793239*x mod 2^64, 32); starting from x=1?
If there's a fast way to compute the nth iteration of a function, then a quantum computer can find the cycle length in polynomial time. -- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com