Числа Мерсенна и Ферма - История изменений

Isaeva в 14:43, 19 января 2015

2015-01-19T14:43:17Z

Isaeva в 09:37, 19 января 2015

2015-01-19T09:37:01Z

Isaeva в 09:08, 19 января 2015

2015-01-19T09:08:44Z

Isaeva в 13:28, 29 декабря 2014

2014-12-29T13:28:13Z

Isaeva в 12:47, 29 декабря 2014

2014-12-29T12:47:44Z

Isaeva в 14:03, 25 декабря 2014

2014-12-25T14:03:13Z

Isaeva в 13:29, 25 декабря 2014

2014-12-25T13:29:44Z

Isaeva в 12:40, 25 декабря 2014

2014-12-25T12:40:02Z

Isaeva в 10:23, 25 декабря 2014

2014-12-25T10:23:57Z

Isaeva в 10:22, 25 декабря 2014

2014-12-25T10:22:53Z

← Предыдущая		Версия 14:43, 19 января 2015
Строка 143:		Строка 143:
	Тогда		Тогда

−	:	+	:<math>((1+2^d+\ldots +2^{{c-1}\cdot d})\cdot ({2^{\alpha} - 1})) \equiv ((1+2^d+\ldots +2^{{c-1}\cdot d})\cdot (2^{d}-1)) = </math>
		+
		+	:<math>= 2^{cd} - 1 \equiv 2^{c\alpha} - 1 \equiv 2^1 - 1 \equiv 1\pmod {(2^{\beta} - 1)}</math>.

@@ Строка 131: / Строка 131: @@
 Константы <math>c_{ij}</math> можно вычислить заранее с помощью расширенного алгоритма Евклида, который по заданным <math>i</math> и <math>j</math> позволяет определить числа <math>a</math> и <math>b</math> такие, что <math>a\cdot p_i + b\cdot p_j = (p_i, p_j) = 1</math>, и можно положить <math>c_{ij} = a</math>. В частности, для величины, обратной к <math>2^{\alpha} - 1</math> по модулю <math>2^{\beta} - 1</math>, легко получить сравнительно простую формулу
-:<math>((1+2^d+\ldots +2^{{c-1}\cdot d})\pmod {2^{\alpha} - 1}\cdot (2^{\alpha} - 1) = 1</math>,
+:<math>((1+2^d+\ldots +2^{{c-1}\cdot d})\cdot ({2^{\alpha} - 1})) \pmod {(2^{\beta} - 1)} = 1</math>,
-где <math>\alpha \pmod {\beta} = d</math> и <math>c\alpha \pmod {\beta} = 1</math>.
+где <math>\alpha \pmod {\beta} = d</math> и <math>c \alpha \pmod {\beta} = 1</math>.
 Действительно, если <math>\alpha = {\beta} +k\cdot q</math>, то

@@ Строка 1: / Строка 1: @@
-При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах специального вида, например, числа Мерсенна или числа Ферма.
+При рассмотрении отдельных классов простых чисел значительный интерес представляет вопрос о простых числах специального вида, таких, например, как числа Мерсенна или числа Ферма.
@@ Строка 12: / Строка 12: @@
 При простых значениях n = p число   может оказаться простым, но может быть составным.
-Например, при <math>p = 2, 3, 5, 7, 13, 17, 19</math> мы получаем простые числа Мерсенна: <math>3, 7, 31, 127, 8191, 131071</math>, а при <math>p = 11, 23, 29</math> числа <math>2^p - 1</math> - составные.
+Например, при <math>p = 2, 3, 5, 7, 13, 17, 19</math> мы получаем простые числа Мерсенна: <math>3, 7, 31, 127, 8191, 131071, 524287</math>, а при <math>p = 11, 23, 29</math> числа <math>2^p - 1</math> - составные.
 '''Свойства чисел Мерсенна'''
@@ Строка 34: / Строка 34: @@
-Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет только такими числами в качестве модулей СОК.
+Необходимо отметить, что значения чисел Мерсенна и Ферма быстро растут. Это не позволяет ограничиться только такими числами в качестве модулей СОК.
@@ Строка 43: / Строка 43: @@
 При таком выборе модулей полезно несколько ослабить условие <math>0 \le {\alpha} < p_i</math> и потребовать только чтобы
-:<math>0 \le {\alpha}_j < 2^{e_j}, a_i \equiv A \pmod{{e_j}-1} </math>. (1)
+:<math>0 \le {\alpha}_j < 2^{e_j}, a_j \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>p_j</math> выполняются следующим образом:
@@ Строка 55: / Строка 55: @@
 <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}) - \left[ {\alpha}_j < {\beta}_j \right]</math>.
+:<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>. Для этого существует простое правило:

← Предыдущая		Версия 13:28, 29 декабря 2014
Строка 128:		Строка 128:

	Основное преимущество алгоритма Гарнера заключается в том, что вычисления производятся с числами, не превышающими величину модуля M.		Основное преимущество алгоритма Гарнера заключается в том, что вычисления производятся с числами, не превышающими величину модуля M.
		+
		+	Константы <math>c_{ij}</math> можно вычислить заранее с помощью расширенного алгоритма Евклида, который по заданным <math>i</math> и <math>j</math> позволяет определить числа <math>a</math> и <math>b</math> такие, что <math>a\cdot p_i + b\cdot p_j = (p_i, p_j) = 1</math>, и можно положить <math>c_{ij} = a</math>. В частности, для величины, обратной к <math>2^{\alpha} - 1</math> по модулю <math>2^{\beta} - 1</math>, легко получить сравнительно простую формулу
		+
		+	:<math>((1+2^d+\ldots +2^{{c-1}\cdot d})\pmod {2^{\alpha} - 1}\cdot (2^{\alpha} - 1) = 1</math>,
		+
		+	где <math>\alpha \pmod {\beta} = d</math> и <math>c\alpha \pmod {\beta} = 1</math>.
		+
		+	Действительно, если <math>\alpha = {\beta} +k\cdot q</math>, то
		+
		+	:<math>2^{\alpha} = 2^{\beta} \cdot (2^q)^k \equiv 2^{\beta} \cdot 1^k \pmod{2^q - 1}</math>.
		+
		+	Поэтому при <math>2^{\alpha} \equiv 2^{\beta} \pmod{2^q - 1}</math> имеем <math>2^{{\alpha}\pmod{q}} \equiv 2^{{\beta}\pmod{q}} \pmod{2^q - 1}</math>; а так как эти последние величины расположены между нулём и <math>{2^q - 1}</math>, должно выполняться <math>{\alpha}\pmod{q} = {\beta}\pmod{q}</math>.
		+
		+	Тогда
		+
		+	:

@@ Строка 93: / Строка 93: @@
 Поэтому <math>{\alpha}_j</math> вычисляются путём сложения <math>e_j</math>-битовых чисел <math>{a_t \oplus a_{t-1} \oplus \ldots \oplus a_1 \oplus a_0} \pmod{2^{e_j}-1}</math>.
-. Обратное преобразование для чисел Мерсенна. Метод Гарнера.
+. Обратное преобразование для чисел Мерсенна. Алгоритм Гарнера.
-Обратный переход от СОК к позиционной системе счисления несколько сложнее. Как мы видели при доказательстве китайской теоремы об остатках, при вычислении обратных мультипликативных элементов требуется уметь вычислять значение функции Эйлера, которое в общем случае требует факторизации, т.е. разложения чисел <math>p_j</math> на простые множители. Даже это обстоятельство показывает, что обратное преобразование чисел из СОК в позиционную систему счисления в соответствии сэтим алгоритмом требует большого числа вычислительных операций с высокой точностью, а именно этого хотелось бы избежать.
+Обратный переход от СОК к позиционной системе счисления несколько сложнее. Алгоритм, основанный на китайской теореме об остатках требует вычисления значение функции Эйлера для вычислении обратных мультипликативных элементов, что в общем случае требует факторизации, т.е. разложения чисел <math>p_j</math> на простые множители. Даже это показывает, что обратное преобразование чисел из СОК в позиционную систему счисления в соответствии с этим алгоритмом требует большого числа вычислительных операций с высокой точностью.
-Метод перехода от <math>{\alpha}_1, {\alpha}_2, \cdots, {\alpha}_n</math> к <math>A</math>, пригодный для практического применения, основан на другом доказательстве китайской теоремы об остатках. Такое доказательство предложено в 1958 г. Х. Л. Гарнером. Оно основано на использовании <math>{C_n}_k</math> констант <math>c_{i,j} (1 \le i \le j \le k)</math>, где
+Алгоритм перехода от <math>{\alpha}_1, {\alpha}_2, \cdots, {\alpha}_n</math> к <math>A</math>, пригодный для практического применения, основан на доказательстве китайской теоремы об остатках, предложенном в 1958 г. Х. Л. Гарнером. Оно основано на использовании <math>{C}_n^k</math> констант <math>c_{ij} (1 \le i \le j \le k)</math>, где
-:<math>c_{i,j} \equiv 1 \pmod{p_j}</math>. (3)

← Предыдущая		Версия 14:03, 25 декабря 2014
Строка 88:		Строка 88:

	где <math>N = 2^{e_j}</math> и <math>0 \le a_j < 2^{e_j}</math> при <math>0 \le k \le t </math>.		где <math>N = 2^{e_j}</math> и <math>0 \le a_j < 2^{e_j}</math> при <math>0 \le k \le t </math>.
		+
		+	Тогда <math>A \equiv {(a_t + a_{t-1} + \ldots + a_1 + a_0)} \pmod {2^{e_j}-1}</math>, поскольку <math>N \equiv 1 \pmod{2^{e_j}-1}</math>.
		+
		+	Поэтому <math>{\alpha}_j</math> вычисляются путём сложения <math>e_j</math>-битовых чисел <math>{a_t \oplus a_{t-1} \oplus \ldots \oplus a_1 \oplus a_0} \pmod{2^{e_j}-1}</math>.
		+
		+	3. Обратное преобразование для чисел Мерсенна. Метод Гарнера.
		+
		+	Обратный переход от СОК к позиционной системе счисления несколько сложнее. Как мы видели при доказательстве китайской теоремы об остатках, при вычислении обратных мультипликативных элементов требуется уметь вычислять значение функции Эйлера, которое в общем случае требует факторизации, т.е. разложения чисел <math>p_j</math> на простые множители. Даже это обстоятельство показывает, что обратное преобразование чисел из СОК в позиционную систему счисления в соответствии сэтим алгоритмом требует большого числа вычислительных операций с высокой точностью, а именно этого хотелось бы избежать.
		+	Метод перехода от <math>{\alpha}_1, {\alpha}_2, \cdots, {\alpha}_n</math> к <math>A</math>, пригодный для практического применения, основан на другом доказательстве китайской теоремы об остатках. Такое доказательство предложено в 1958 г. Х. Л. Гарнером. Оно основано на использовании <math>{C_n}_k</math> констант <math>c_{i,j} (1 \le i \le j \le k)</math>, где
		+	:<math>c_{i,j} \equiv 1 \pmod{p_j}</math>. (3)

← Предыдущая		Версия 13:29, 25 декабря 2014
Строка 74:		Строка 74:

	что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до <math>p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 > 2^{143}</math>.		что обеспечивает эффективность сложения, вычитания и умножения целых чисел в интервале вплоть до <math>p_1 \cdot p_2 \cdot p_3 \cdot p_4 \cdot p_5 > 2^{143}</math>.
		+
		+	2. Прямое преобразование для чисел Мерсенна
		+
		+	Модулярное представление <math>({\alpha}_1, {\alpha}_2, \ldots, {\alpha}_n)</math> для заданного числа <math>A</math> может быть получено посредством деления <math>A</math> на <math>(p_1, p_2, \ldots, p_n)</math> с запоминанием остатков. В случае, когда <math>A = {({\nu}_k, {\nu}_{k-1}, \ldots, {\nu}_0)}_b</math>, возможно применение более подходящего способа, который состоит в том, чтобы, используя СОК, вычислить полином
		+
		+	:<math>(\ldots ({\nu}_k \cdot b + {\nu}_{k-1}) \cdot b + \ldots ) b + {\nu}_0)</math>.
		+
		+	Если основание <math>b = 2</math> и модули <math>p_j</math> имеют вид <math>2^{e_j}-1</math>, оба подхода сводятся к совсем простому способу.
		+
		+	Рассмотрим двоичные представления числа <math>A</math> с блоками по <math>{e_j}</math> бит:
		+
		+	:<math>A = a_t \cdot N^t + a_{t-1} \cdot N^{t-1} + \ldots + a_1 \cdot N + a_0</math>,
		+
		+	где <math>N = 2^{e_j}</math> и <math>0 \le a_j < 2^{e_j}</math> при <math>0 \le k \le t </math>.

← Предыдущая		Версия 12:40, 25 декабря 2014
Строка 56:		Строка 56:

	:<math>{\alpha}_j \ominus {\beta}_j = ({\alpha}_j - {\beta}_j \pmod{e_j}) - \left[ {\alpha}_j < {\beta}_j \right]</math>.		:<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>.

← Предыдущая		Версия 10:23, 25 декабря 2014
Строка 55:		Строка 55:
	<math>{\alpha}_1, {\alpha}_2, \cdots, {\alpha}_n</math> и <math>{\beta}_1, {\beta}_2, \cdots, {\beta}_n</math> при сложении или умножении соответственно. При вычитании можно пользоваться и соотношением:		<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>.	+	:<math>{\alpha}_j \ominus {\beta}_j = ({\alpha}_j - {\beta}_j \pmod{e_j}) - \left[ {\alpha}_j < {\beta}_j \right]</math>.