密码学中关于整数群Z*p中元素顺序的群论
我被扔进了一个深入浅出的群论中，我对我的密码学课有点迷茫。基本上，我必须在java中实现的一个实用程序是，
阶(素数，p-1的因子列表，任意a)
这应该返回群Z*p中a的顺序，其中f是p-1的素因子列表。当f包含重复项时，确保您的方法有效。例如，考虑p=17的情况
以下是我到目前为止(从我的笔记中采取的步骤)
public static BigInteger order(BigInteger p, List<BigInteger> f, BigInteger a){
//Algorithm starts like this
//Start by setting t equal to p-1 i.e t= p1 p2...pn
BigInteger t = p.subtract(BigInteger.ONE);
for(BigInteger pi : f){
//test if a^t1 = 1 mod p where t1 = t/pi
BigInteger t1 = t.divide(pi);
if(Practical5ExponentiationModMSquareAndMultiply.expm(p, a, t1).equals(BigInteger.ONE)){
t = t1;
System.out.println("t after mod = "+t);
System.out.println("pi after mod = "+pi);
}
}
return t;
}素因子f的列表由另一种方法生成，然后传入
我的笔记很难理解，我想知道是否有人能告诉我，我到底应该归还什么。另外，你能给我一个关于群论的理解，因为它可以帮助我进一步的实践吗？
回答 1
Stack Overflow用户
发布于 2011-04-26 16:42:05
您正在寻找最小的数字o，例如a^o == 1 (mod p)，也就是最小的o，例如p将a^o - 1除以。
你需要的群论结果是，整数的乘法群mod p是p-1阶的循环群。这意味着：
a^o == 1 (mod p)
- The
- 顺序
o除以p-1并满足p-1阶o是满足上述条件的最小数.
因此，您可以通过接受p-1的素数，并重复将p-1除以它们来找到顺序，直到p不再将a^n - 1划分为真的为止。
示例1：P= 13，p-1 = 2*2*3，a= 5。
对于p= 2，5^( 12 /2) == 12 (mod 13)，所以不能按顺序丢失2s。
对于p= 3，5^(12/3) == 1 (mod 13)，您可以按顺序丢失3。
因此，顺序是2*2 = 4。
给你的例子(p = 17)是另一个例子：
示例2：p= 17，p-1 = 2*2*2*2，a=9
9^(16/ 2 ) == 1 (mod 17)，因此您可能会丢失前2。
9^( 16 /4) == 16 (mod 17)，所以你不能丢失第二个2，你可以停止搜索。
因此，顺序是2*2*2 = 8。
希望这足以让你看到算法。
https://stackoverflow.com/questions/5792872
复制相似问题
腾讯云开发者
