已知p是素数,且a与P互质,求最小的x使得:a……x%p=1 ?
发布网友
发布时间：2024-05-08 10:33
共1个回答
热心网友
时间：2024-07-09 00:15
我们知道，模p的剩余类0,1,2,...,p-1（上面都加上一横）构成一个域。而其所有非零元构成一个乘法群。可以证明，这个有p-1个元素的群是一个循环群。其生成元g被称为“原根”。原根不一定是唯一的，但取定原根g后，每个非零元a都可以写成g的方幂的形式g^i，我们称这个i为a关于原根g的“指标”，也可以记为ind a（很显然，由a求其指标i这个过程类似于一种取对数的运算，这样的对数也叫离散对数）。
现在回到题目中来。a与p互质，所以其对应一个非零的剩余类，从而在取定某个原根g后，有一个指标i=ind a。那么a=g^i，a^x=(g^i)^x=g^(i*x)。那么现在问题就变成了求最小的x使得，g^(i*x)=1。而g是原根，p-1是使得g^n=1的最小的n，从而g^n=1当且仅当n是p-1的倍数。所以现在问题就变成了求最小的x，使得i*x为p-1的倍数。说到这我相信你已经会做了吧？
答案是(p-1)/(i,p-1)，其中分母是最大公约数。
不懂可以再问~
