Числа Мерсенна и Ферма

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
Строка 43: Строка 43:
 
При таком выборе модулей полезно несколько ослабить условие <math>0 \le {\alpha} < p_i</math> и потребовать только чтобы  
 
При таком выборе модулей полезно несколько ослабить условие <math>0 \le {\alpha} < p_i</math> и потребовать только чтобы  
  
:<math>0 \le {\alpha}_j < 2^{e_j}, a_i \equiv A \pmod{{e_j}-1} </math>.
+
:<math>0 \le {\alpha}_j < 2^{e_j}, a_i \equiv A \pmod{{e_j}-1} </math>. (1)
  
Таким образом, значение <math>{\alpha}_j = p_j = 2^{e_j}-1</math> принимается в качестве оптимального вместо <math>{\alpha}_j = 0</math>, поскольку это, с одной стороны, не влияет на справедливость китайской теоремы об остатках, а с другой означает, что math>{\alpha}_j</math> может быть любым math>{\alpha}_j</math>- битовым двоичным числом. При таком допущении, операции сложения и вычитания по модулю   выполняются следующим образом:
+
Таким образом, значение <math>{\alpha}_j = p_j = 2^{e_j}-1</math> принимается в качестве оптимального вместо <math>{\alpha}_j = 0</math>, поскольку это, с одной стороны, не влияет на справедливость китайской теоремы об остатках, а с другой означает, что math>{\alpha}_j</math> может быть любым math>{\alpha}_j</math>- битовым двоичным числом. При таком допущении, операции сложения и вычитания по модулю <math>p_j</math> выполняются следующим образом:
  
  
Строка 51: Строка 51:
  
 
:<math>{\alpha}_j \otimes {\beta}_j  = ({\alpha}_j \cdot {\beta}_j \pmod{e_j}) \oplus \lfloor ({\alpha}_j \cdot {\beta}_j) / 2^{e_j} \rfloor</math>.
 
:<math>{\alpha}_j \otimes {\beta}_j  = ({\alpha}_j \cdot {\beta}_j \pmod{e_j}) \oplus \lfloor ({\alpha}_j \cdot {\beta}_j) / 2^{e_j} \rfloor</math>.
 +
 +
Здесь <math> \oplus </math> и <math> \otimes </math> указывают на действия, которые с учётом условия (1) должны быть выполнены с отдельными компонентами кортежей
 +
<math>{\alpha}_1, {\alpha}_2, \cdots, {\alpha}_n</math> и <math>{\beta}_1, {\beta}_2, \cdots, {\beta}_n</math> при сложении или умножении соответственно. При вычитании можно пользоваться и соотношением:
 +
 +
:<math>{\alpha}_j \ominus {\beta}_j  = ({\alpha}_j - {\beta}_j \pmod{e_j}) \oplus \left[ {\alpha}_j < {\beta}_j \right]</math>.

Версия 13:22, 25 декабря 2014

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


Определение

Числа Мерсенна — числа вида M_n = 2^n - 1, где n — натуральное число. Названы в честь французского математика Марена Мерсенна.

Иногда числами Мерсенна называют только числа M_n с нечетными или простыми индексами n.

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

При простых значениях n = p число может оказаться простым, но может быть составным. Например, при p = 2, 3, 5, 7, 13, 17, 19 мы получаем простые числа Мерсенна: 3, 7, 31, 127, 8191, 131071, а при p = 11, 23, 29 числа 2^p - 1 - составные.

Свойства чисел Мерсенна

  • Если M_n является простым, то число n также простое. Обратное в общем случае неверно, наименьшим контрпримером является M_{11} = 2047 = 23\cdot 89.
  • Любой делитель числа M_p для простого p имеет вид 2pk+1, где k — натуральное число (следствие малой теоремы Ферма).


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


Определение

Числа Ферма — числа вида F_n=2^{2^n}+1, где n — неотрицательное целое число.


При n = 0, 1, 2, 3, 4 числа Ферма простые: 3, 5, 17, 257, 65537.

Все числа Мерсенна и Ферма – взаимно простые.


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


Операции над числами Мерсенна и Ферма

1. Если в качестве модулей p_j выбраны числа Мерсенна, т.е. числа вида p_j = 2^{e_j} - 1, для которых значение модуля на единицу меньше очередной степени двойки, это зачастую упрощает выполнение основных арифметических операций, так как выполнять вычисления с числами в таком представлении несколько проще, чем с числами, представленными в обратном коде.

При таком выборе модулей полезно несколько ослабить условие 0 \le {\alpha} < p_i и потребовать только чтобы

0 \le {\alpha}_j < 2^{e_j}, a_i \equiv A \pmod{{e_j}-1} . (1)

Таким образом, значение {\alpha}_j = p_j = 2^{e_j}-1 принимается в качестве оптимального вместо {\alpha}_j = 0, поскольку это, с одной стороны, не влияет на справедливость китайской теоремы об остатках, а с другой означает, что math>{\alpha}_j</math> может быть любым math>{\alpha}_j</math>- битовым двоичным числом. При таком допущении, операции сложения и вычитания по модулю p_j выполняются следующим образом:


{\alpha}_j \oplus {\beta}_j  = (({\alpha}_j + {\beta}_j) \pmod{e_j}) + \lfloor ({\alpha}_j + {\beta}_j) \ge 2^{e_j} \rfloor,
{\alpha}_j \otimes {\beta}_j  = ({\alpha}_j \cdot {\beta}_j \pmod{e_j}) \oplus \lfloor ({\alpha}_j \cdot {\beta}_j) / 2^{e_j} \rfloor.

Здесь  \oplus и  \otimes указывают на действия, которые с учётом условия (1) должны быть выполнены с отдельными компонентами кортежей {\alpha}_1, {\alpha}_2, \cdots, {\alpha}_n и {\beta}_1, {\beta}_2, \cdots, {\beta}_n при сложении или умножении соответственно. При вычитании можно пользоваться и соотношением:

{\alpha}_j \ominus {\beta}_j  = ({\alpha}_j - {\beta}_j \pmod{e_j}) \oplus \left[ {\alpha}_j < {\beta}_j \right].

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация