Диффи-Хеллман - Примитивный корневой мод n - вопрос криптографии - PullRequest
Новая
       16

Диффи-Хеллман - Примитивный корневой мод n - вопрос криптографии

0 голосов
/ 14 мая 2010

В следующем фрагменте, пожалуйста, объясните, начиная с первого цикла "for", что происходит и почему. Почему 0 добавлено, почему 1 добавлено во второй цикл. Что происходит в заявлении «если» под bigi. Наконец, объясните метод modPow. Заранее благодарю за содержательные ответы. 

public static boolean isPrimitive(BigInteger m, BigInteger n) {

    BigInteger bigi, vectorint;
    Vector<BigInteger> v = new Vector<BigInteger>(m.intValue());
    int i;

    for (i=0;i<m.intValue();i++)
        v.add(new BigInteger("0"));

    for (i=1;i<m.intValue();i++)
    {
        bigi = new BigInteger("" + i);

        if (m.gcd(bigi).intValue() == 1)
            v.setElementAt(new BigInteger("1"), n.modPow(bigi,m).intValue());
    }

    for (i=0;i<m.intValue();i++)
    {
        bigi = new BigInteger("" + i);

        if (m.gcd(bigi).intValue() == 1)
        {
            vectorint = v.elementAt(bigi.intValue());
            if ( vectorint.intValue() == 0)
                i = m.intValue() + 1;
        }
    }

    if (i == m.intValue() + 2)
        return false;
    else
        return true;

}

1 Ответ

1 голос
/ 15 мая 2010

  • Обрабатывать вектор как список логических значений, с одним логическим значением для каждого числа от 0 до m. Когда вы смотрите таким образом, становится очевидным, что для каждого значения установлено значение 0, чтобы инициализировать его как false, а затем для 1 устанавливается значение true, чтобы установить его в значение true.

  • Последний цикл for проверяет все логические значения. Если какой-либо из них равен 0 (указывает на ложь), то функция возвращает ложь. Если все true, то функция возвращает true.

  • Для объяснения оператора if, о котором вы спрашивали, потребовалось бы объяснить, что такое примитивный корень mod n, в чем весь смысл функции. Я думаю, если ваша цель - понять эту программу, вы должны сначала понять, что она реализует. Если вы прочитаете статью Википедии , вы увидите это в первом абзаце:

В модульной арифметике ветвь теория чисел, первообразный корень по модулю n - любое число g со свойством что любое число взаимно просто соответствует степени g (mod n). То есть, если g является примитивным корнем (мод n), то для каждого целого числа a, которое имеет gcd (a, n) = 1, есть целое число k такой, что gk ≡ a (mod n). к называется индекс а. То есть г является генератор мультипликативной группы целых чисел по модулю n.

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

Бонусная ссылка: Эта статья имеет хороший фон, в том числе, как проверить примитивные корни в конце.

...