1

我有点陷入群论的深渊，我对我的密码学课程有点迷茫。基本上我必须在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 的列表由另一种方法生成，然后传入

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

4

1 回答 1

3

您正在寻找最小的数字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不再为真，才能找到顺序。pa^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。

希望这足以让您看到算法。

于 2011-04-26T16:42:05.943 回答