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

Question

我有点陷入群论的深渊，而且我对我上的密码学课有点迷失。 基本上我必须用java实现的一个实用方法是，

阶数（素数，因子列表 p-1 ，任意 a)

这应该返回 a 在群 Z*p 中的阶数，其中 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 的列表是由另一种方法生成的，然后传入

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

Answer 1

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

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

• 阶数 o 整除 p-1 并满足 a^o == 1 (mod p)
• 阶数 o 是满足上述条件的最小数。

因此，您可以通过获取 p-1 的质因数，然后反复将 p-1 除以它们，直到 p 不再成立来求出阶数。 code> 除a^n - 1。

示例 1：p = 13，p-1 = 2*2*3，a = 5。

对于 p = 2，5^(12/2) == 12 (mod 13)，所以您不能丢掉订单中的2。

对于 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。

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