证明2^k mod n,k=0,1,2,...的循环长度是phi(n)的约数吧。n是奇数的情况比较好处理，
直接套Lagrange定理就完了。n是偶数的情况则考虑n除掉所有2因子剩下的那个奇数n'，
然后利用phi(n')是phi(n)的约数和前面关于奇数的结论。

把这个结论结合离散对数的东西利用起来，快不快不知道，我觉得至少是一种办法吧。

> 我是枚举phi(n)的所有约数的。 有没有更确切的结论呢？

• Re:如果phi(n) 不是满足 2^x mod n == 1 的最小的x (75) Iamjw 2007-08-27 00:42:49
  • 我没记错的话 初等数论上说 是不能直接求的。。当然不排除可能真能。。。。。。 (83) ACM06060 2007-08-27 01:56:47
    • “直接求”这个不好定义吧…… (0) frkstyc 2007-08-27 13:24:30
      • 这个大家理解是什么意思就可以了。。 (0) ACM06060 2007-08-27 14:14:41