Числа Мерсенна и Ферма
При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах специального вида, таких, например, как числа Мерсенна или числа Ферма.
Определение
Числа Мерсенна — числа вида , где
— натуральное число.
Названы в честь французского математика Марена Мерсенна.
Иногда числами Мерсенна называют только числа с нечетными или простыми индексами n.
Множества простых чисел в этих последовательностях совпадают, а потому понятие простого числа Мерсенна не зависит от того, как именно определяются числа Мерсенна.
При простых значениях n = p число может оказаться простым, но может быть составным.
Например, при мы получаем простые числа Мерсенна:
, а при
числа
- составные.
Свойства чисел Мерсенна
- Если
является простым, то число n также простое. Обратное в общем случае неверно, наименьшим контрпримером является
.
- Любой делитель числа
для простого p имеет вид 2pk+1, где k — натуральное число (следствие малой теоремы Ферма).
Числа Мерсенна получили известность в связи с эффективным тестом простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа.
Определение
Числа Ферма — числа вида , где n — неотрицательное целое число.
При числа Ферма простые:
.
Все числа Мерсенна и Ферма – взаимно простые.
Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет ограничиться только такими числами в качестве модулей СОК.
Операции над числами Мерсенна и Ферма
1. Если в качестве модулей выбраны числа Мерсенна, т.е. числа вида
, для которых значение модуля на единицу меньше очередной степени двойки, это зачастую упрощает выполнение основных арифметических операций, так как выполнять вычисления с числами в таком представлении несколько проще, чем с числами, представленными в обратном коде.
При таком выборе модулей полезно несколько ослабить условие и потребовать только чтобы
. (1)
Таким образом, значение принимается в качестве оптимального вместо
, поскольку это, с одной стороны, не влияет на справедливость китайской теоремы об остатках, а с другой означает, что math>{\alpha}_j</math> может быть любым math>{\alpha}_j</math>- битовым двоичным числом. При таком допущении, операции сложения и вычитания по модулю
выполняются следующим образом:
,
.
Здесь и
указывают на действия, которые с учётом условия (1) должны быть выполнены с отдельными компонентами кортежей
и
при сложении или умножении соответственно. При вычитании можно пользоваться и соотношением:
.
Эти операции могут быть эффективно выполнены, даже если больше машинного слова компьютера, так как совсем просто вычислить остаток положительного числа по модулю степени 2 или разложить число по степеням 2. Для работы с модулями вида
необходимо знать, при каких условиях число
является взаимно простым с числом
. Для этого существует простое правило:
. (2)
Формула (2) утверждает, в частности, что
.
Уравнение (2) следует из алгоритма Евклида и тождества
.
Поэтому на компьютере с длиной слова можно выбрать
,
что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до .
2. Прямое преобразование для чисел Мерсенна
Модулярное представление для заданного числа
может быть получено посредством деления
на
с запоминанием остатков. В случае, когда
, возможно применение более подходящего способа, который состоит в том, чтобы, используя СОК, вычислить полином
.
Если основание и модули
имеют вид
, оба подхода сводятся к совсем простому способу.
Рассмотрим двоичные представления числа с блоками по
бит:
,
где и
при
.
Тогда , поскольку
.
Поэтому вычисляются путём сложения
-битовых чисел
.
3. Обратное преобразование для чисел Мерсенна. Алгоритм Гарнера.
Обратный переход от СОК к позиционной системе счисления несколько сложнее. Алгоритм, основанный на китайской теореме об остатках требует вычисления значение функции Эйлера для вычислении обратных мультипликативных элементов, что в общем случае требует факторизации, т.е. разложения чисел на простые множители. Даже это показывает, что обратное преобразование чисел из СОК в позиционную систему счисления в соответствии с этим алгоритмом требует большого числа вычислительных операций с высокой точностью.
Алгоритм перехода от
к
, пригодный для практического применения, основан на доказательстве китайской теоремы об остатках, предложенном в 1958 г. Х. Л. Гарнером. Оно основано на использовании
констант
, где
, (3)
, т.е.
.
Алгоритм Гарнера
Рассмотрим набор модулей , удовлетворяющих условию китайской теоремы об остатках. Любое число
однозначно представимо в виде
.
Вычислив по порядку все коэффициенты для
, можно подставить их в формулу и найти искомое решение:
Рассмотрим выражение для по модулю
, где
, получим:
;
;
;
;
и так далее.
Основное преимущество алгоритма Гарнера заключается в том, что вычисления производятся с числами, не превышающими величину модуля M.
Константы можно вычислить заранее с помощью расширенного алгоритма Евклида, который по заданным
и
позволяет определить числа
и
такие, что
, и можно положить
. В частности, для величины, обратной к
по модулю
, легко получить сравнительно простую формулу
,
где и
.
Действительно, если , то
.
Поэтому при имеем
; а так как эти последние величины расположены между нулём и
, должно выполняться
.
Тогда
.