Целью работы является поиск стратегии алгоритмической оптимизации  (P-1)-алгоритма Полларда в среде многопоточности для более эффективного разложения чисел на множители. Задачи, решаемые в ходе исследования: 1. Разработка библиотеки для реализации длинной арифметики в среде параллельных вычислений на графическом процессоре. 2. Разработка способа модификации оригинального алгоритма P-1 с применением аппаратного ускорения и разработанной библиотеки. 3. Программная реализация разработанного способа. 4. Оценка скорости и эффективности работы созданного средства. В ходе работы была спроектирована библиотека длинной арифметики статической разрядности для применения в среде многопоточного исполнения. Были проанализированы современные исследования в области применения метода P-1 на GPU. В результате работы было разработано несколько вариантов алгоритмической модификации метода P-1 на графическом процессоре, были продемонстрированы возможности спроектированных способов по разложению чисел различной разрядности. Были сделаны выводы о применимости каждого из разработанных способов на практике. Полученные результаты могут быть использованы в качестве основы для проектирования более совершенных способов факторизации чисел на основе алгоритма P-1.

The purpose of the study is to find a strategy for algorithmic optimization of the Pollard P-1 algorithm in a multi-threading environment for more efficient numbers factorization. The research set the following goals: 1. Development of a library for implementing long arithmetic in a parallel computing environment on a graphics processor. 2. Development of a method for modifying the original P-1 algorithm using hardware acceleration and the developed library. 3. Software implementation of the developed method. 4. Scanning speed assessment and efficiency of the developed software implementation. During the work, a library of long static-bit arithmetic was designed for use in a multi-threaded execution environment. Modern studies on the application of the P-1 method on GPUs were analyzed. The work resulted in the development of several variants of an algorithmic modification of the P-1 method on a graphics processor. Capabilities of the designed methods for decomposing numbers of various bit depths were demonstrated. Conclusions were drawn about the applicability of each of the developed methods in practice. The results obtained can be used as a basis for designing more advanced methods for factoring numbers based on the P-1 algorithm.

• Введение
• 1 Алгоритмы факторизации целых чисел
  • 1.1 Классические алгоритмы факторизации
  • 1.2 Факторизация чисел (P-1)-методом Полларда
• 2 Распараллеливание вычислений на графических процессорах
  • 2.1 История появления вычислений общего назначения на GPU
  • 2.2 Современные возможности GPGPU. Процесс разработки
  • 2.3 Оптимизация существующих алгоритмов
• 3 Модификации алгоритма P-1 с применением аппаратного ускорения
  • 3.1 Существующие исследования по выбранной тематике
    • 3.1.1 Yu-Shiang Lin, Chun-Yuan Lin1, Der-Chyuan Lou: Efficient Parallel RSA Decryption Algorithm for Many-core GPUs with CUDA
    • 3.1.2 AJ Kaufmann, David Matlack: CUDA Factor
• 4 Подготовка тестового стенда
  • 4.1 Выбор фреймворка параллелизации на GPU
    • 4.1.1 CUDA
    • 4.1.2 OpenCL
    • 4.1.3 Metal
  • 4.2 Реализация операций длинной арифметики
    • 4.2.1 Обращение к существующим проектам
    • 4.2.2 Проектирование собственной библиотеки
      • 4.2.2.1 Ключевые аспекты разработанной библиотеки
      • 4.2.2.2 Выявление ошибок и недочетов
• 5 Модификации алгоритма P-1
  • 5.1 Ограничения стандартной однопроцессорной реализации алгоритма
  • 5.2 Модифицированный алгоритм выборки множителей на основе степень-гладких чисел
  • 5.3 Алгоритм полного перебора на основе стратегии «перебор с возвратом»
  • 5.4 Алгоритм перебора с использованием циклического буфера
  • 5.5 Алгоритм перебора на основе битовой длины множителей
  • 5.6 Комбинированный алгоритм перебора, направленный на обнаружение сильных простых чисел среди делителей
• 6 Тестирование
  • 6.1 Оборудование, операционная система и версии ПО
  • 6.2 Выбор параметров параллелизации
  • 6.3 Выбор разрядностей вычислений
  • 6.4 Результаты
    • 6.4.1 Модифицированный алгоритм выборки множителей на основе степень-гладких чисел
    • 6.4.2 Алгоритм полного перебора на основе стратегии «перебор с возвратом»
    • 6.4.3 Алгоритм перебора с использованием циклического буфера
    • 6.4.4 Алгоритм перебора на основе битовой длины множителей
    • 6.4.5 Комбинированный алгоритм перебора, направленный на обнаружение сильных простых чисел среди делителей
• 7 Выводы
• Заключение
• Список использованных источников