Информатика, вычислительная техника
и управление
Системный анализ, управление и обработка информации
Прохорова О.В., доктор технических наук, профессор Самарского государственного архитектурно-строительного университета
ГЕНЕРАЦИЯ ПОСЛЕДОВАТЕЛЬНОСТИ ПРОСТЫХ ЧИСЕЛ
В статье рассматривается метод генерации последовательности простых чисел. Автором сформулированы необходимые и достаточные условия простоты чисел, необходимые и достаточные условия составного числа. На примерах показана генерация простых чисел с проверкой обязательных условий, а также разложение большого числа на простые делители.
Ключевые слова: простые и составные числа, генерация последовательности простых чисел, множество значимых чисел.
GENERATION OF THE PRIME NUMBERS SEQUENCE
The article describes the method of the prime numbers sequence generation. Author states necessary and sufficient conditions for prime and composite numbers. Solutions of the prime numbers generation with the required conditions verification and the decomposition of the composite number on the prime multipliers were shown.
Keywords: prime and composite numbers, generation of the prime numbers, set of the significant numbers.
Одной из важных вычислительных задач является проверка чисел на простоту (дано число, нужно сказать, простое оно или нет). Самый теоретически быстрый на данный момент алгоритм проверки числа, составное оно или нет, - тест Миллера-Рабина (Miller-Rabin test).
Тест Миллера - Рабина - вероятностный полиномиальный тест простоты. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера - Рабина часто используется в криптографии для получения больших случайных простых чисел.
Раскладывание числа на простые сомножители практикуется достаточно широко, например, в алгоритме RSA, где стойкость схемы RSA зависит от того, как быстро можно разложить большое составное число на 2 простых сомножителя. Процедура такого разложения занимает относительно много времени в силу большого числа итераций подбора, что является большим минусом в применении.
Предлагаемая автором методика генерации последовательности простых чисел включает ряд правил:
1. Сцепляются два числа. Самая правая цифра есть только нечетное число, за исключением цифры 5, т.е. последней цифрой справа могут быть только: 1, 3, 7, 9. Слева это любые числа, начина с 0 и далее. Для двух разрядного числа и левой цифре 0 правая цифра 5 допускается.
Для каждого сцепленного числа X = [ax • a2 •...• an} находится отображение F(X) = F{a1
a2 a3 ... an} = b, где аi - есть цифры числа Х, b - есть одна цифра, полученная последовательным сложением всех цифр числа Х. Таким образом из сцепленных чисел формируется
множество значимых чисел, обозначаемое буквой В это множество не входят также
числа, состоящие из повторяющихся цифр за исключением числа 11. Числа множества у подчиняются следующему правилу:
Е(Х) = ]Таг = Ъ е Н, где Н = {1, 2, 4, 5, 7, 8}.
где
I=1
2. Для каждого значимого числа Хе у формируется множество его делителей, обозначаемое 0(Х). Множество 0(Х) формируется из значимых чисел меньших Х / 2, полученных ранее, возрастающих по величине и по которым принято заключение об их простоте (см. теоремы 1- 2). Возможные делители есть простые числа: {3,7, 11, 13, 17, 19, ...}. Для
поиска делителей числа Хе у можно воспользоваться программой, реализованной автором и прилагаемой в конце статьи.
3. В множество у (Х) простых чисел включаются лишь те числа из множества УХ), для которых 0(Х) есть пустые множества.
Рассмотрим применимость предложенных правил генерации последовательности простых чисел на примерах. Результаты приведены в таблицах. В первом столбце по строкам таблицы располагаются цифры от 0 до 9. В остальных столбцах первой строки располагаются цифры 1, 3, 7, 9.
1. На пересечении строки и столбца помещается число в соответствии спервым правилом -конкатенации (сцепления) чисел, а именно, сцепления числа строки и цифры столбца,
при этом учитываются правила 1 и 2. Множество чисел у начинается с известных простых чисел 01, 07, затем дополняется числами 11, 13, 17 и т.д. Числа 02, 03 и 05 вводятся
в окончательно сформированное множество дополнительно, поскольку они яв-
ляются простыми, но не генерируются рассматриваемым методом. В таблицу не входят числа, нарушающие правила. Например, число 21 имеет сумму цифр равную 3, что не допускается по правилу 2.
Таблица 1.
Генерация простых чисел Х < 100
№ 1 3 7 9
0 01 07
1 11 13 17 19
2 23 29
3 31 37
4 41 43 47 49
5 53 59
6 61 67
7 71 73 79
8 83 89
9 91 97
2. Построенная такая таблица дает множество чисел УХ)= {1, 2, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 91, 97}.
3. Множества 0(Х) для всех чисел кроме 49 и 91 есть пустые множества, а 0(49) = {7}, 0(91) = {7, 13}. Значит, числа 49 и 91 являются составными, т.к. они имеют делители.
4. Массив W(X)= {01, 02, 03, 05, 07, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97} есть массив простых чисел.
5. Продолжая генерировать числа, увеличиваем левое число для сцепления. Оно уже будет иметь 2 разряда, в начале с единицей слева, т.е. это будут числа {10, 11,12,13,14,15,16,17,18,19}, а справа те же цифры столбца 1,3,7, 9.
Таблица 2.
Генерация простых чисел 100 < Х < 200
№ 1 3 7 9
10 101 103 107 109
11 113 119
12 121 127
13 131 133 137 139
14 143 149
15 151 157
16 161 163 167 169
17 173 179
18 181 187
19 191 193 197 199
6. Ряд чисел массива у(Х) увеличился уже до числа 199. Но в него попали числа 119, 121, 133, 143, 161, 169, 187, которые подчиняются правилу 1, но для них множества Q(Х) не является пустыми, т.е. нарушается правило 3.
7. Применяя к этим числам правило 2 находим: Q(119) = {7, 17}, Q(121) = {11}, Q(133) = {7, 19}, Q(143) = {11, 13}, Q(161) = {7, 23}, Q(169) = {13}, Q(187) = {11, 17}.
8. Исключив эти числа из рассмотрения, мы получим множество простых чисел у(Х)= {01, 02, 03, 05, 07, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199}.
По аналогии генерируются простые числа и далее. Анализ результатов генерирования последовательности простых чисел по представленной методике дает основание для формулирования теорем. Отметим, что числа размерности более 1 оканчивающиеся на четную цифру или цифру 5 не рассматриваются на простоту, т.к. они заведомо составные.
Теорема 1. Необходимым условием простоты числа X€ у размерности более 1, которое не состоит из повторяющихся цифр за исключение числа 11, является выполнение требования:
^ (1) ^ (X) = X Я,- = ь е Н , где Н = { 1, 2, 4, 5, 7, 8}.
,=1
Теорема 2. Достаточны условием простоты числа X еу является пустота множества его делителей Q(Х).
Теорема 3. Достаточным условием того, что число разрядности более единицы, есть составное число, является выполнение требования:
« (2) Р (X) = X А, = ь е 2, Где 2 = { 3, 6, 9}.
I=1
Доказательство теорем подтверждается простыми действиями с числами согласно сформулированным правилам и в силу элементарности действий здесь не приводится. Пример 1. Проверим число Х = 1293 на предмет простое оно или составное. Решение. Сложим все цифры числа до одной цифры, получим цифру 6. Значит число 1293 - составное на основании теоремы 3. Проверим это. Воспользуемся программой автора (см. конец статьи). Получим, что 0(Х) = {3, 431}. Значит, оно не простое, что и требовалось показать.
Для разложения большого числа Х разрядности п на простые делители будем рассматривать следующие правила:
1. Выделить цифры числа Х, т.е. {а1 а2 а3 .. .ап}.
п
2. Найти Р(Х) = X ^ = Ь е 2 , где 2 = { 3 6 9}.
г=1
3. Если условие (2) не выполнилось, то считать его составным или простым нельзя. Нужна дополнительная проверка. Переход к п. 5
4. Если условие (2) выполнено, то число Х заведомо составное.
5. Находим для него 0(Х), воспользовавшись программой. Получим множество простых делителей заданного числа Х.
Пример 2. Разложим большое число на простые делители. Пусть таким числом будет числоХ =156789.
Решение задачи отобразим в виде таблицы 3.
Таблица 3.
__Разложение большого числа на простые делители._
Х - делимое Р(Х) Q(X) - делитель Частное Остаток от деления
156789 9 3 52263 0
52263 9 3 17421 0
17421 6 3 5807 0
5807 2 - - -
Отметим, что повторяющиеся делители входят в множество 0(Х) по одному разу. Подводим итог решения. Число 156789 является составным, оно имеет делителями простые числа: {3, 5807}, что и требовалось показать. Данная процедура поиска простых делителей числа разрядности п и заложена в программу, прикрепленную ниже.
Пример 3. Разложим большое число на простые делители. Пусть таким числом будет число X = 271156629923 разрядности п= 12. Результат расчетов поместим в таблицу 4.
Решение.
Таблица 4.
_ Разложение большого числа на простые делители._
Х ( делимое) Б(Х) Q(X)- делитель Частное Остаток от деления
271156629923 9 89 3046703707 0
3046703707 10 229 1184090087 0
1184090087 2 89 13304383 0
13304383 7 - - -
Подводим итог решения. Число 271156629923 является составным, оно имеет делителями простые числа: 89, 229, 13304383, что и требовалось показать.
Предложенная автором методика генерации последовательности простых чисел имеет большое преимущество по сравнению с существующими алгоритмами, а именно, элементарность проверки любого числа на простоту и разложения большого числа на простые сомножители, что особенно важно в современной криптографии.
Приведем код на языке С++ несложной процедуры поиска простых делителей заданного числа.
int main()
{
long long c;
int flag1 = 0, flag2;
cout << " Enter number c \n";
cin >> c;
cout << "\n Search devisors of the given number:\n "; int i = 3;
while (i < c / 2)
{
flag2 = 0;
for (int j = 2; j < i / 2; j++)
if (i%j == 0) {
flag2 = 1; break;
}
if (flag2 == 1)
{
i++;
continue;
}
if (c % i == 0) {
cout << " " << i; flag1 = 1;
}
i++;
}
if (
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.