Open Ruanxingzhi opened 4 years ago
例题的n其实可以直接分解,分解之后会发现其实解出来的pq=p,应该是出题人的问题
根据拉格朗日定理,2生成的子群的阶应该是群pq阶的因数,如何得出是(p-1)(q-1)因数的? 群的阶为pq时,元素的阶为p的个数有(p-1)个,阶为q的个数有(q-1)个,阶为pq的个数有(p-1)(q-1)个。 因此任取一个元素(这里为2)的阶为pq的概率极大。反而说明2^lcm(p-1,q-1)=1 (mod pq)很难成立。
@FinallyKiKi 根据拉格朗日定理,2生成的子群的阶应该是群pq阶的因数,如何得出是(p-1)(q-1)因数的? 群的阶为pq时,元素的阶为p的个数有(p-1)个,阶为q的个数有(q-1)个,阶为pq的个数有(p-1)(q-1)个。 因此任取一个元素(这里为2)的阶为pq的概率极大。反而说明2^lcm(p-1,q-1)=1 (mod pq)很难成立。
n=pq,则模 n 群的元素个数是 phi(n) = phi(p)*phi(q) = (p-1)(q-1)。
@Ruanxingzhi n=pq,则模 n 群的元素个数是 phi(n) = phi(p)*phi(q) = (p-1)(q-1)。
但是这与您文中的论述相反。如果任取一元素生成的子群大概率为模n群,则无法满足2^lcm(p-1,q-1)=1 (mod pq)
https://ruanx.net/schmidt-samoa/