Числа Мерсенна и Ферма — различия между версиями

Версия 12:40, 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}) - \left[ {\alpha}_j < {\beta}_j \right]$ .

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

$(2^e-1,2^{\beta}-1) = 2^{e,\beta}-1$ . (2)

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

$(2^e-1,2^{\beta}-1) = 1 \Leftrightarrow (e,\beta) = 1$ .

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

${(2^e-1)} \pmod {2^{\beta}-1} = 2^{e \pmod {b}} - 1$ .

Поэтому на компьютере с длиной слова $2^{32}$ можно выбрать

$p_1 = 2^{32} - 1, p_2 = 2^{31} - 1, p_3 = 2^{29} - 1, p_4 = 2^{27} - 1, p_5 = 2^{25} - 1$ ,

что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до $p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 > 2^{143}$ .

@@ Строка 56: / Строка 56: @@
 :<math>{\alpha}_j \ominus {\beta}_j  = ({\alpha}_j - {\beta}_j \pmod{e_j}) - \left[ {\alpha}_j < {\beta}_j \right]</math>.
+Эти операции могут быть эффективно выполнены, даже если <math>2^{e_j}</math> больше машинного слова компьютера, так как совсем просто вычислить остаток положительного числа по модулю степени 2 или разложить число по степеням 2. Для работы с модулями вида <math>2^{e_j}-1</math> необходимо знать, при каких условиях число <math>2^{e_j}-1</math> является взаимно простым с числом <math>2^{\beta}-1</math>. Для этого существует простое правило:
+:<math>(2^e-1,2^{\beta}-1) = 2^{e,\beta}-1</math>. (2)
+Формула (2) утверждает, в частности, что
+:<math>(2^e-1,2^{\beta}-1) = 1 \Leftrightarrow (e,\beta) = 1</math>.
+Уравнение (2) следует из алгоритма Евклида и тождества
+:<math>{(2^e-1)} \pmod {2^{\beta}-1} = 2^{e \pmod {b}} - 1</math>.
+Поэтому на компьютере с длиной слова <math>2^{32}</math> можно выбрать
+<math>p_1 = 2^{32} - 1, p_2 = 2^{31} - 1, p_3 = 2^{29} - 1, p_4 = 2^{27} - 1, p_5 = 2^{25} - 1</math>,
+что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до <math>p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 > 2^{143}</math>.

Числа Мерсенна и Ферма — различия между версиями

Версия 12:40, 25 декабря 2014

Навигация

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

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты