Чернобровкин В.В., Каримов Р.Р. Сургутский государственный университет Метод поиска простых чисел в ограниченном диапазоне ВВГП-2012

Разработка инструментария для работы с многоразрядными числами (1 млн.разрядов)

- Криптография и криптология - Задачи с необходимой высокой точностью - Моделирование физических, химических процессов - Аэродинамика, гидродинамика - Расчет оболочек ядерных реакторов

Многоразрядная арифметика Модулярная арифметика Простые числа

Примерпредставления числа A по модулю P в системе остаточных классов: Пример представления числа A по модулю P в системе остаточных классов: Пусть A = 96576, p 1 =13, p 2 =17, p 3 =19, p 4 =23 P= П p i = 13*17*19*21=96577 Тогда ((12 (mod 13), 16(mod17), 18(mod19), 22(mod23)) Со всеми остатками можно проводить арифметические операции (-,+,*, /,^). Главное чтобы результат вычислений не превосходил Пример вычисления в модулярной арифметике

Последний разряд числа: i 0 = {0, 1, 2, …, 9} 1. Число делится на 2, когда последняя цифра делится на 2: i 0 = {2, 4, 6, 8} i 0 = {2, 4, 6, 8} 2. Число делится на 5, когда последняя цифра делится на 5, т.е. если она 0 или 5: i 0 = {0, 5} i 0 = {0, 5} i 0 = {0, 2, 4, 5, 6, 8} Составные числа: i 0 = {0, 2, 4, 5, 6, 8} i 0 = {1, 3, 7, 9} Возможно простые числа: i 0 = {1, 3, 7, 9} Метода поиска простых чисел

[Z n, …, Z n+1 ] [Z n, …, Z n+1 ] Числа где i 0 =1 Числа где i 0 =3 Числа где i 0 =7 Числа где i 0 =9 Поиск простых чисел Простые числа Pi, где i 0 =1 Простые числа Pi, где i 0 =3 Простые числа Pi, где i 0 =7 Простые числа Pi, где i 0 =1 Общий файл с простыми числами Метода поиска простых чисел Поиск простых чисел

Типы данных Переменные Unsigned long FirstNum = 2^30 ( ) Unsigned long LastNum = 2^31 ( ) Массивы: a[0… N ] = {FirstNum … LastNum} (массив с числами диапазона) b[0..N] = {0, 2, 5, 13, …} (массив признака простоты): 0 – простое число, 2 … lastnum - составное 0 – простое число, 2 … lastnum - составное Программная реализация ТипМакс.значениеBytes Long Unsigned long Long long Unsigned long long

for (unsigned long i=firstnum; i

__device__ int CheckPrime(unsigned long num) { int result = 0; for (int i=2; i(dev_a, dev_b, firstnum, N); } Реализация GPU

Сравнение: CPU и GPU* Диапазон Количество чиселCPUGPURate 2^31-10^2… 2^ ,12 2^31-10^3… 2^ ,73 2^31-10^4… 2^ ,22 2^31-10^5… 2^ ,80 2^31-10^6… 2^ ,10 2^31-10^7… 2^ ,14 * ПГУ Тесла

Сравнение: Оценка Чебышева* * ПГУ Тесла Диапазон Количество чисел простые/всего (%) Количеств о простых Оценка Чебышев а Кол.прост-Чебышева /Количество простых 2^31-10^2… 2^ ,29 2^31-10^3… 2^ ,00 2^31-10^4… 2^ ,29 2^31-10^5… 2^ ,82 2^31-10^6… 2^ ,80 2^31-10^7… 2^ ,73

- Более быстрый алгоритм определения простоты числа - Числа, для которых не найден делитель на итерации k, заносить в массив и вычислять отдельно

Чернобровкин В.В., Каримов Р.Р. Сургутский государственный университет Поиск простых чисел с использованием CUDA ВВГП-2012