Числа Мерсенна и Ферма — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
| Строка 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>. | ||
Версия 10:22, 25 декабря 2014
При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах специального вида, например, числа Мерсенна или числа Ферма.
Определение
Числа Мерсенна — числа вида 
, где 
— натуральное число.
Названы в честь французского математика Марена Мерсенна.
Иногда числами Мерсенна называют только числа 
с нечетными или простыми индексами n.
Множества простых чисел в этих последовательностях совпадают, а потому понятие простого числа Мерсенна не зависит от того, как именно определяются числа Мерсенна.
При простых значениях n = p число может оказаться простым, но может быть составным.
Например, при 
мы получаем простые числа Мерсенна: 
, а при 
числа 
- составные.
Свойства чисел Мерсенна
- Если является простым, то число n также простое. Обратное в общем случае неверно, наименьшим контрпримером является
.
- Любой делитель числа
для простого p имеет вид 2pk+1, где k — натуральное число (следствие малой теоремы Ферма).
Числа Мерсенна получили известность в связи с эффективным тестом простоты Люка — Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа.
Определение
Числа Ферма — числа вида 
, где n — неотрицательное целое число.
При 
числа Ферма простые: 
.
Все числа Мерсенна и Ферма – взаимно простые.
Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет только такими числами в качестве модулей СОК.
Операции над числами Мерсенна и Ферма
1. Если в качестве модулей 
выбраны числа Мерсенна, т.е. числа вида 
, для которых значение модуля на единицу меньше очередной степени двойки, это зачастую упрощает выполнение основных арифметических операций, так как выполнять вычисления с числами в таком представлении несколько проще, чем с числами, представленными в обратном коде.
При таком выборе модулей полезно несколько ослабить условие 
и потребовать только чтобы
. (1)
Таким образом, значение 
принимается в качестве оптимального вместо 
, поскольку это, с одной стороны, не влияет на справедливость китайской теоремы об остатках, а с другой означает, что math>{\alpha}_j</math> может быть любым math>{\alpha}_j</math>- битовым двоичным числом. При таком допущении, операции сложения и вычитания по модулю выполняются следующим образом:
,
.
Здесь 
и 
указывают на действия, которые с учётом условия (1) должны быть выполнены с отдельными компонентами кортежей
и 
при сложении или умножении соответственно. При вычитании можно пользоваться и соотношением:
![{\alpha}_j \ominus {\beta}_j = ({\alpha}_j - {\beta}_j \pmod{e_j}) \oplus \left[ {\alpha}_j < {\beta}_j \right]](/w/images/math/f/7/1/f713c6a53e9a7adc10da2a5274060da0.png)
.
