Математические основы системы остаточных классов

дипломная работа

§ 5. Числа Мерсенна, Ферма и операции над ними

При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах вида , где m - нечётное, именуемые числами Мерсенна. При простых значениях m = p число может оказаться простым, но может быть составным.

Например, при р = 2, 3, 5, 7, 13, 17, 19 мы получаем простые числа Мерсенна: 3, 7, 31, 127, 8191, 131071, а при р = 11, 23, 29 числа - составные.

Числа вида , где k - положительное, обычно называют числами Ферма. При k = 0, 1, 2, 3, 4 числа Ферма простые: 3, 5, 17, 257, 65537. Все остальные числа Ферма - составные. Все числа Мерсенна и Ферма - взаимно простые.

Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет использовать лишь их в качестве модуле СОК.

При работе же на двоичных компьютерах, иногда желательно выбирать модули в виде чисел Мерсенна

. (5.1)

Другими словами, значение каждого модуля на единицу меньше очередной степени 2. Такой выбор значения модуля зачастую упрощает выполнение основных арифметических операций, так как выполнять вычисления с числами, представленными по модулю , несколько проще, чем с числами, представленными в обратном коде. После того как значения модулей таким образом выбраны, полезно несколько ослабить условие и потребовать чтобы только

, . (5.2)

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

,

.

Здесь и указывают на действия, которые с учётом условия (5.2) должны быть выполнены с отдельными компонентами кортежей и при сложении или умножении соответственно. При вычитании можно пользоваться и соотношением:

.

Эти операции могут быть эффективно выполнены, даже если больше машинного слова компьютера, так как совсем просто вычислить остаток положительного числа по модулю степени 2 или разложить число по степеням 2. Для работы с модулями вида необходимо знать, при каких условиях число является взаимно простым с числом . Для этого существует простое правило:

. (5.3)

Формула (5.3) утверждает, в частности, что

.

Уравнение (5.3) следует из алгоритма Евклида и тождества

,

где mod означает операцию нахождения остатка от деления. Поэтому на компьютере с длиной слова 232 можно выбрать

, ,, , ,

что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до .

Как мы уже заметили, операции преобразования чисел в СОК и обратно очень важны. Модулярное представление для заданного числа А может быть получено посредством деления А на с запоминанием остатков. В случае, когда , возможно применение более подходящего способа, который состоит в том, чтобы, используя СОК, вычислить полином

.

Если основание b = 2 и модули имеют вид , оба подхода сводятся к совсем простому способу. Рассмотрим двоичные представления числа А с блоками по бит:

,

где и при .

Тогда ,

Поскольку . Поэтому вычисляются путём сложения битовых чисел .

Обратный переход от СОК к позиционной системе счисления выполняется немного сложнее. Как мы видели при доказательстве китайской теоремы об остатках, при вычислении обратных мультипликативных элементов требуется уметь вычислять значение функции Эйлера, которое в общем случае требует факторизации, т. е. разложения чисел на простые множители. Даже это обстоятельство показывает, что обратное преобразование чисел из СОК в позиционную систему счисления приводит к большому числу вычислительных операций с высокой точностью, а именно этого нам хотелось бы избежать прежде всего. Поэтому, чтобы найти действительно пригодный для практического применения метод перехода от к А, необходимо иметь другое доказательство китайской теоремы об остатках. Такое доказательство предложено в 1958 г. Х. Л. Гарнером. Оно основано на использовании констант , где . (5.4)

Константы можно вычислить с помощью расширенного алгоритма Евклида, который по заданным i и j позволяет определить числа a и b такие, что , и можно положить . В частности, для величины, обратной к по модулю , легко получить сравнительно простую формулу

, где

и . Действительно, если , то . Поэтому при имеем ; а так как эти последние величины расположены между нулём и , должно быть .

Тогда

Вернёмся к общему случаю. Так как , удовлетворяют условиям (5.4), то можно выполнить присваивания

,

,

, (5.5)

.

Тогда число

(5.6)

будет удовлетворять условиям ,

для . (5.5)

Формулы (5.5) можно переписать следующим

,

,

,

Если это сделать, то вместо констант как в (5.5), потребуется только k - 1 констант

Оценим с точки зрения вычислений на компьютере достоинства и недостатки последнего варианта формул (5.5) по сравнению с исходным вариантом этих формул.

Пусть . Тогда для некоторого постоянного числа

с .

Поэтому

. Таким образом,

. (5.6)

Формула (5.6) - это представление числа А по так называемому смешанному основанию, которое можно перевести в двоичный, либо десятичный формат. Если интервал [0; P) не является необходимым (напомним, что ), то после завершения процесса к нему можно добавить (или вычесть из него) соответствующее число, кратное Р. Преимущество метода, представленного формулами (5.5), состоит в том, что для вычисления используется только арифметика по модулю , которая уже встроена в алгоритмы этого класса. Более того, соотношения (5.5) позволяют выполнять вычислении параллельно. Можно начать с присваивания , затем, в момент j при сразу же получить для .

Важно отметить, что представление (5.6) по смешанному основанию пригодно для сравнения величин двух чисел, заданных в СОК. Так, если известно, что , то можно сказать, будет ли , если сначала выполнить переход к и к , затем в соответствии с лексикографическим правилом проверить выполнение неравенств или и и т. д. Более того, нет необходимости переходить к двоичной системе счисления, если нужно всего лишь выяснить, будет ли меньше, чем .

Операции сравнения двух чисел или определения знака числа при представлении в СОК интуитивно понятны и очень просты, поэтому можно было бы ожидать, что удастся найти значительно более лёгкий способ выполнения такого сравнения, чем переход к представлению со смешанным основанием. Однако следующая теорема утверждает, что вопрос этот не простой, поскольку величина числа в СОК существенным образом зависит от всех битов всех остатков .

Теорема. Примитивные корни по модулю р существуют тогда и только тогда, когда:

1) ,

2) ,

3) ,

где р - любое нечётное простое число, .

Таким образом, при всех других р примитивных корней нет. Доказательство теоремы можно найти, например, в книге [ ]. Эта теорема позволяет фактически дать полное описание группы U(Zp) для произвольного модуля р.

Теорема. Пусть - каноническое представление числа Р. Тогда . Группа - циклическая группа порядка , а - циклическая группа порядка 1 или 2 при l = 1 или l = 2 соответственно. Если , то она будет прямым произведением двух циклических групп, одной порядка 2, другой порядка 2l - 2. Кроме того, число р обладает примитивными корнями тогда и только тогда, когда р = 2, р = 4, р = рl или р = 2рl , где р - нечётное простое число.

Как следствие отметим, что для кольцо - поле тогда и только тогда, когда р - простое число, причём - область целостности. По изложенному материалу рассмотрим ряд примеров.

Пример. Пусть b обратно к а по модулю р. Проверить. Что b(2 - ab) обратно к а по модулю р2 и что b2(3 - 2ab) обратно к а2 по модулю р2.

Решение. По условию , следовательно , откуда , то есть . Вторую часть задачи можно решить непосредственным вычислением, учитывая, что (так как в кольце из х2 = 0 следует, что , и можно применить это к х = 1 - ab в .

Пример. Определим последовательность , следующим образом: и .

Проверить, что обратно к а по модулю . Какое число обратно к 11335 по модулю 216?

Решение. Первая часть задачи фактически повторяет рассуждения примера 1.5. Для второй части задачи полагаем p = 2, а = 11335, b0 = 1, k = 4. Тогда числом, обратным к а = 11335 по модулю 216 будет число b4, которое вычисляем последовательно:

Пример. Сколько элементов порядка 10 в следующей группе и каковы они? Z25;

Решение. В группе Z25 элементов порядка 10 нет, так как |Z25| = 25, а 25 не делится на 10.

Делись добром ;)