Введение
Концепция модульной арифметики
В модульной арифметике число g является примитивным корнем по модулю n, если каждое число, взаимно простое с n, сравнимо со степенью g по модулю n. То есть, g является примитивным корнем по модулю n, если для каждого целого числа, взаимно простого с n, существует целое число k, такое что g^k ≡ a (mod n). Такое значение k называется индексом или дискретным логарифмом числа a по основанию g по модулю n. Следовательно, g является примитивным корнем по модулю n тогда и только тогда, когда g является образующим элементом мультипликативной группы целых чисел по модулю n.
Гаусс определил примитивные корни в статье 57 работы «Disquisitiones Arithmeticae» (1801), где он указал, что Эйлер придумал этот термин. В статье 56 он отметил, что Ламберт и Эйлер были знакомы с ними, но он был первым, кто строго доказал существование примитивных корней для простого числа n. Фактически, в «Disquisitiones» содержится два доказательства: одно в статье 54 является неконструктивным доказательством существования, а доказательство в статье 55 — конструктивным. Примитивный корень существует тогда и только тогда, когда n равно 1, 2, 4, pk или 2pk, где p — нечетное простое число и k > 0. Для всех остальных значений n мультипликативная группа целых чисел по модулю n не является циклической. Это было впервые доказано Гауссом.
Определение
Если n – положительное целое число, то целые числа от 1 до n, взаимно простые с n (или, эквивалентно, классы вычетов, взаимно простые с n), образуют группу, где операцией является умножение по модулю n; она обозначается как U(n) и называется группой единиц по модулю n или группой примитивных классов по модулю n. Как объяснено в статье «Мультипликативная группа целых чисел по модулю n», эта мультипликативная группа U(n) является циклической тогда и только тогда, когда n равно 2, 4, p<sup>k</sup> или 2p<sup>k</sup>, где p – нечетное простое число, а k – целое неотрицательное число. Когда (и только когда) эта группа U(n) циклична, генератор этой циклической группы называется примитивным корнем по модулю n (или, более точно, примитивным корнем из единицы по модулю n, подчеркивая его роль как фундаментального решения уравнений X<sup>φ(n)</sup> – 1 = 0 в кольце Z/nZ), или просто примитивным элементом по модулю n.
When is non cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub primitive roots (see 15 in the examples below). For any n (whether or not is cyclic), the order of is given by Euler's totient function φ(n) And then, Euler's theorem says that for every a coprime to n; the lowest power of a that is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, has to be the smallest power of a that is congruent to 1 modulo n.
Когда U(n) не является циклической, таких примитивных элементов по модулю n не существует. Вместо этого, каждый простой делитель n имеет свои собственные субпримитивные корни (см. пример 15 ниже). Для любого n (независимо от того, является ли U(n) циклической или нет), порядок U(n) задается функцией Эйлера φ(n). И тогда теорема Эйлера утверждает, что a<sup>φ(n)</sup> ≡ 1 (mod n) для любого a, взаимно простого с n; наименьшая степень a, сравнимая с 1 по модулю n, называется мультипликативным порядком a по модулю n. В частности, чтобы a было примитивным корнем по модулю n, φ(n) должно быть наименьшей степенью a, сравнимой с 1 по модулю n.
When is non cyclic, such primitive elements mod n do not exist. Instead, each prime component of n has its own sub primitive roots (see 15 in the examples below). For any n (whether or not is cyclic), the order of is given by Euler's totient function φ(n) And then, Euler's theorem says that for every a coprime to n; the lowest power of a that is congruent to 1 modulo n is called the multiplicative order of a modulo n. In particular, for a to be a primitive root modulo n, has to be the smallest power of a that is congruent to 1 modulo n.
Нижняя граница
Фридландер (1949) и Салье (1950) доказали теоремы, имеющие значение для криптографии, включая схему обмена ключами Диффи — Хеллмана. Звуковые диффузоры были основаны на концепциях теории чисел, таких как примитивные корни и квадратичные остатки.