java - 密码学中关于一组整数 Z*p 中元素顺序的群论

Question

我有点陷入了群论的深渊，我对我的密码学课有点迷茫。 基本上我必须在 Java 中实现的一个实用的是，

order(prime number, list of factors of p-1 , any a)

这应该返回组 Z*p 中 a 的阶数，其中 f 是 p-1 的素因子列表。确保您的方法在 f 包含重复项时有效。例如，考虑 p=17

的情况

这是我目前所掌握的，(取 self 笔记中的步骤)

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通过另一种方法生成然后传入

我的笔记很难理解，我想知道是否有人可以告诉我我实际上应该归还什么。 你也可以让我对这个群论片段有一个可能的理解，因为它可以帮助我进一步的实践

Answer 1

您正在寻找满足 a^o == 1 (mod p) 的最小数 o，即最小的 o 使得 p 除 a^o - 1。

您需要的群论结果是整数模 p 的乘法群是 p-1 阶循环。这意味着:

• 顺序o除p-1并满足a^o == 1 (mod p)
• 顺序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。

希望这足以让您了解算法。