Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

Аналогично строятся тройные и т.д. числа Мерсенна. Например, тройным числом Мерсенна является 127=M₇=MMM₂.

Не для всех чисел Мерсенна существуют двойные и тройные числа. Например, MM₁₃ не является простым.

Первыми простыми числами Мерсенна являются M₂=3, M₃=7, M₅=31, M₇=127, M₁₃=8191, M₁₇, M₁₉, M₃₁.

На данный момент (2007 г.) не доказана конечность или бесконечность количества простых чисел Мерсенна.

7.5. Теорема Диемитко и процедура генерации простых чисел заданной длины ГОСТ Р 34.10-94.

Следующая теорема позволяет строить доказуемо простые числа большего размера на основе простых чисел меньшего размера.

Теорема Диемитко.

Пусть n=qR+1, где q – простое число, R – четное, R<4(q+1).

Если найдется a<n: 1) a^n—1≡1(mod n); 2) 1(mod n), то n – простое число.

■

Итак, если имеем простое число q, то, перебирая четные числа R, строим числа n=qR+1 и испытываем их на простоту согласно теореме Диемитко, пока не получим простое число. По полученному числу можно построить еще одно простое число и т.д.

Приведем алгоритм перехода от меньшего простого числа q: |q|= к большему p: |p|=t, использующийся в ГОСТе. Фигурирующая в процедуре ξ есть равномерно распределенная на (0,1) случайная величина, получаемая с помощью линейного конгруэнтного генератора. Каждый раз на Шаге 1 получают новое значение ξ.

Алгоритм перехода от меньшего простого числа к большему:

Вход: t – требуемая размерность простого числа, q – простое число : |q|= .

Ш.1. Вычисляем N= . Если N – нечетное, то N=N+1.

Ш.2. u=0.

Ш.3. Вычисляем p=(N+u)q+1 – кандидат в простые.

Ш.4. Если p>2^t, возвращаемся на Ш.1.

Ш.5. Если 2^n—1≡1(mod n) и 2^N+u 1(mod n), то идем на Выход.

Ш.6. Вычисляем u=u+2. Возвращаемся на Ш.3.

Выход. p – простое число.

Первое слагаемое в построении числа N обеспечивает минимальный требуемый размер числа p, а второе вносит в процедуру поиска новых простых чисел необходимый элемент случайности.

Проверка на Шаге 4 необходима, чтобы число p не превышало своей верхней границы, а проверка на Шаге 5 есть проверка условия теоремы Диемитко при a=2.

Пример:

Вход: t=4, q=3=[11]₂

1. N= =3. N=N+1=4.

2. u=0.

3. p=4·3+1=13.

4. 13<2⁴=16.

5. 2¹² mod 13 =1, 2⁴ mod 13 = 3.

Выход. р=13=[1011]₂

Замечание

Поскольку на Шаге 5 условие теоремы Диемитко проверяется не для всех a<p, а только для 2, то некоторые простые числа, сгенерированных этим алгоритмом, не опознаются как простые. Но вероятность того, что для простого числа n наугад выбранное число a будет удовлетворять условиям теоремы Диемитко, есть (1—1/q), а q – достаточно большое число. Таким образом, проверки при a=2 вполне достаточно, чтобы не отсеивать слишком много простых чисел. Выбор a=2 обусловлен тем, что возведение числа 2 в степень в двоичном представлении является простой операцией.

ГЛАВА 2. Алгебраические основы теории чисел.

Долгое время арифметика (наука о числах) развивалась как наука о свойствах конкретных чисел. И только Франсуа Виет (1540-1603) ровесник первого Бурбона Генриха IV Наваррского и его жены королевы Марго, систематически стал применять для обозначения произвольных чисел буквы. (В России в это время правил Иван Грозный и было не до алгебры). С помощью таких обозначений уже можно было формулировать утверждения о числах вообще, поэтому Виета называют отцом алгебры.

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

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

Образно говоря, не стоит отдельно развивать науку о столах, отдельно о табуретках, отдельно о тумбочках. Лучше изучать предмет из дерева на четырех ножках, с несущей поверхностью и дополнительными отделами. Если налагать некоторые дополнительные условия, то будет получаться стол, стул или шкаф соответственно. Ведь с точки зрения математики спагетти и блины почти неразличимы – это цилиндры, у которых разное отношение высоты цилиндра к радиусу основания: у спагетти 100:1, а у блина 1:100.

§1. Основные понятия алгебры.

1.1. Начальные понятия.

Как начинается любая сказка? В тридевятом царстве в тридесятом государстве жили-были… Не только в сказках, но и в математике и программировании важно окружение, где разворачивается все действие - объемлющий универсум, среда программирования.

Два наших основных объекта - это числа и многочлены. Где же они живут? Как обычно принято в математике, они «живут» в некотором множестве, называемом алгебраической системой.

Алгебраическая система – это непустое множество, в котором задана одна или несколько алгебраических операций.

Что такое алгебраическая операция? Их очень много, нам потребуется бинарная алгебраическая операция.

Бинарной алгебраической операцией на множестве А называется любое отображение, которое каждой паре элементов из множества А ставит в соответствие элемент множества А.

В этом смысле суммы или произведения чисел, многочленов или матриц являются алгебраическими операциями. Бинарные алгебраические операции обычно называют сложением или умножением. Это сокращение для длинной тирады «бинарная алгебраическая операция». Обозначают их тоже по-разному. Приведем наиболее часто используемые обозначения: +, ·, ×, •, , , *.

Если множество А содержит 10 элементов, то пар элементов будет 100. Так как любой паре из 100 можно поставить в соответствие любой из 10 элементов, то общее число различных алгебраических операций на множестве из 10 элементов будет равно 10¹⁰⁰. Как известно атомов в видимой части вселенной примерно 10⁵⁰, поэтому изучать все алгебраические операции нет никакой возможности.

Определение. Алгебраическая операция «+» называется:

Коммутативной на A, если a+b=b+a для всех a, b из A;

ассоциативной, если (a+b)+c=a+(b+c) для всех a, b, c из A;

имеющей нейтральный элемент, если e+a=a+e=a;

имеющей обратимые элементы, если a+b=b+a=e.

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

Пример 1.

На множестве натуральных чисел введем новую алгебраическую операцию (возведение в степень). Поскольку 3² = 9, а 2³ = 8, то операция не коммутативна. Далее, , в то же время , поэтому операция и неассоциативна. Нетрудно видеть, что нет нейтрального элемента, поскольку если , то е = 1, но . Если нет нейтрального, то об обратном нет и речи.

Пример 2. На множестве натуральных чисел с добавленным нулем введем новую операцию (модуль разности). Эта операция обладает свойством коммутативности, нейтральным элементом является ноль, и каждый элемент является сам к себе обратным. А вот ассоциативности нет: , но .

Определение. Если на множестве А задана ассоциативная алгебраическая операция, то такое множество называется полугруппой. Если эта операция коммутативная, то полугруппа называется коммутативной.

Пример 3. Множество натуральных чисел относительно операции обычного сложения является коммутативной полугруппой.

Определение. Если на множестве А задана ассоциативная алгебраическая операция с нейтральным элементом, то такое множество называется полугруппой с единицей или моноидом. Если эта операция коммутативная, то моноида называется коммутативным.

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

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

Определение. Если на множестве А задана ассоциативная операция, имеющая нейтральный элемент и все ее элементы имеют обратные, то множество А называется группой. Если операция к тому же коммутативная, то группа называется коммутативной или абелевой в честь Нильса Хенриха Абеля (1802-1829).

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

Пример 6. Множество ненулевых рациональных чисел относительно операции обычного умножения является коммутативной группой.

Как назвать алгебраическую операцию - сложением или умножением, в том случае, если она одна единственная, совершенно не важно. Но если операций две, то сложением, обычно, называют ту, которая коммутативна.

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

Определение. Пусть на множестве А задано две алгебраические операции. Одна из операций является ассоциативной, коммутативной, имеет нейтральный элемент и все элементы множества А имеют обратные. Назовем ее сложением. Вторая операция, называемая умножением ассоциативна. Между собой операции связаны законом дистрибутивности

(a+b)c=ac+bc, c(a+b)=ca+cb,

В этом случае множество А называется кольцом. Если умножение коммутативно, то кольцо называется коммутативным.

Кстати, коммутативные кольца абелевыми никогда не называют.

Более точно, введенная нами дистрибутивность называется дистрибутивностью сложения, относительно умножения. Операции в этом свойстве неравноправны. Если бы выполнялась и дистрибутивность умножения, относительно сложения, то были бы верны формулы

.

Соединяя вместе обе дистрибутивности, получаем

.

Характеристики

Список файлов книги