这就是primitive root的问题。如果是mod 2N-1的话,因为限定在奇数范围内,有primitive root的充要条件是2N-1等于一个奇素数的方幂。所以2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime。充分条件不清楚,但很多情况下2都是primitive root mod p^n。等看大家的回答。
YWY 写了: 2023年 1月 23日 18:12
这就是primitive root的问题。如果是mod 2N-1的话,因为限定在奇数范围内,有primitive root的充要条件是2N-1等于一个奇素数的方幂。所以2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime。充分条件不清楚,但很多情况下2都是primitive root mod p^n。等看大家的回答。
需要最少洗2N-2次才能还原的必要条件是N = (p+1)/2 where p is an odd prime,因为2N-1必须等于一个奇素数。
YWY 写了: 2023年 1月 23日 18:12
这就是primitive root的问题。如果是mod 2N-1的话,因为限定在奇数范围内,有primitive root的充要条件是2N-1等于一个奇素数的方幂。所以2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime。充分条件不清楚,但很多情况下2都是primitive root mod p^n。等看大家的回答。
有一个反例
p = 7, n = 1, N = 4, 2N-1 = 7
2不是primitive root mod 7
2 is NOT primitive root modulo 7
2 is NOT primitive root modulo 17
2 is NOT primitive root modulo 23
2 is NOT primitive root modulo 31
2 is NOT primitive root modulo 41
2 is NOT primitive root modulo 43
2 is NOT primitive root modulo 47
2 is NOT primitive root modulo 71
2 is NOT primitive root modulo 73
2 is NOT primitive root modulo 79
2 is NOT primitive root modulo 89
2 is NOT primitive root modulo 97
2 is NOT primitive root modulo 7
2 is NOT primitive root modulo 17
2 is NOT primitive root modulo 23
2 is NOT primitive root modulo 31
2 is NOT primitive root modulo 41
2 is NOT primitive root modulo 43
2 is NOT primitive root modulo 47
2 is NOT primitive root modulo 71
2 is NOT primitive root modulo 73
2 is NOT primitive root modulo 79
2 is NOT primitive root modulo 89
2 is NOT primitive root modulo 97
1. "2是primitive root mod 2N-1的必要条件是N = (p^n+1)/2 where p is an odd prime"这是正确的,但是没想通跟"requires 2N-2 shuffles to reset deck"有什么关系
对于任意N,都存在k 使得2^k = 1 mod 2N - 1
2. "需要最少洗2N-2次才能还原的必要条件是N = (p+1)/2 where p is an odd prime,因为2N-1必须等于一个奇素数。"
这个是怎么得到?
没有直接关系但又间接关系。“2是primitive root mod 2N-1”是说需要至少phi(2N-1)次(欧拉数)才能还原。注意phi(2N-1)小于等于2N-2。所以,“需要最少洗2N-2次才能还原”的充要条件是“phi(2N-1) = 2N-2而且2是primitive root mod 2N-1”。但phi(2N-1) = 2N-2当且仅当2N-1等于一个奇素数。所以“需要最少洗2N-2次才能还原”的充要条件是“2N-1是奇素数而且2是primitive root mod 2N-1”。这样,“N = (p+1)/2 where p is an odd prime”是必要条件,“2是primitive root mod 2N-1”也是必要条件。还有,通过考虑二次剩余,“2是primitive root mod p”的必要条件是“p = 3 or 5 mod 8”。所以“需要最少洗2N-2次才能还原”的必要条件是“N = (p+1)/2 where p is an odd prime and p = 3 or 5 mod 8”。
YWY 写了: 2023年 1月 24日 00:54
没有直接关系但又间接关系。“2是primitive root mod 2N-1”是说需要至少phi(2N-1)次(欧拉数)才能还原。注意phi(2N-1)小于等于2N-2。所以,“需要最少洗2N-2次才能还原”的充要条件是“phi(2N-1) = 2N-2而且2是primitive root mod 2N-1”。但phi(2N-1) = 2N-2当且仅当2N-1等于一个奇素数。所以“需要最少洗2N-2次才能还原”的充要条件是“2N-1是奇素数而且2是primitive root mod 2N-1”。这样,“N = (p+1)/2 where p is an odd prime”是必要条件,“2是primitive root mod 2N-1”也是必要条件。还有,通过考虑二次剩余,“2是primitive root mod p”的必要条件是“p = 3 or 5 mod 8”。所以“需要最少洗2N-2次才能还原”的必要条件是“N = (p+1)/2 where p is an odd prime and p = 3 or 5 mod 8”。
我还是不明白“2是primitive root mod 2N-1”是说需要至少phi(2N-1)次(欧拉数)才能还原“的原因