Теория групп в криптографии относительно порядка элементов в группе целых чисел Z * p - PullRequest
Новая
       17

Теория групп в криптографии относительно порядка элементов в группе целых чисел Z * p

1 голос
/ 26 апреля 2011

Я был как бы глубоко погружен в теорию групп, и я немного потерян для класса криптографии, который у меня есть.В принципе, я должен реализовать в java порядок

(простое число, список факторов p-1, любой 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 генерируется другимметод, а затем передал

Заметки, которые у меня есть, довольно сложны для понимания, и мне было интересно, может ли кто-нибудь сказать мне, что я на самом деле должен возвращать.Также вы могли бы дать мне возможное понимание этого фрагмента теории групп, поскольку он может помочь в моих дальнейших практических занятиях

1 Ответ

3 голосов
/ 26 апреля 2011

Вы ищете наименьшее число 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 делит a^n - 1.

Пример 1 : p = 13, p-1 = 2 * 2 * 3, a = 5.

Для p = 2, 5 ^ (12/2) == 12 (мод 13), поэтому вы не можете потерять 2 в порядке.

Для p = 3, 5 ^ (12/3) == 1 (мод 13), поэтому вы можете потерять 3 вorder.

Таким образом, порядок равен 2 * 2 = 4.

Данный пример (p = 17) является еще одним иллюстративным случаем:

Пример 2: p = 17, p-1 = 2 * 2 * 2 * 2, a = 9

9 ^ (16/2) == 1 (мод 17), поэтому вы можете проиграть первый2.

9 ^ (16/4) == 16 (мод 17), поэтому вы не можете потерять 2 секунды и можете прекратить поиск.

Таким образом, порядок равен 2* 2 * 2 = 8.

Надеюсь, чтоЭто должно быть достаточно для вас, чтобы увидеть алгоритм.

...