Details

Целью работы является повышение скорости работы алгоритма факторизации ECM за счёт применения технологии параллельного программирования CUDA. Объектом исследования являются алгоритмы факторизации больших чисел. Задачи, решаемые в ходе исследования: 1. Исследовать существующие алгоритмы факторизации с целью определения возможности их распараллеливания с применением GPU. 2. Адаптировать алгоритм факторизации с использованием эллиптических кривых (ECM, Elliptic Curve Method) под архитектуру GPU с применением фреймворка CUDA. 3. Оценить скорость разработанного программного прототипа по сравнению с другими эффективными алгоритмами факторизации больших чисел на CPU и GPU. В ходе работы были исследованы существующие алгоритмы факторизации и определён потенциал их оптимизации за счёт применения GPU. В результате работы была разработана модификация алгоритма факторизации ECM с применением GPU, была произведена оценка скорости работы разработанной программы с применением различных видеокарт, а также произведено сравнение с аналогичными реализациями алгоритма на CPU. Полученные результаты могут быть использованы для дальнейшего исследования алгоритма факторизации ECM с применением GPU.

The purpose of the work is to increase the speed of the ECM factorization algorithm through the use of CUDA parallel programming technology. The object of the research is algorithms for factoring large numbers. Tasks to be solved during the research: 1. Investigation of existing factorization algorithms to determine the possibility of their parallelization using a GPU. 2. Adapt the elliptic Curve factorization algorithm (ECM, Elliptic Curve Method) to the GPU architecture using the CUDA framework. 3. Evaluate the speed of the developed software prototype in comparison with other efficient algorithms for factoring large numbers on the CPU and GPU. During the work, existing factorization algorithms were studied and the potential for their optimization through the application of GPU was determined. As a result, a modification of the ECM factorization algorithm utilizing GPU was developed. An evaluation of the execution speed of the developed program using various graphics cards was carried out, and a comparison was made with similar CPU-based implementations of the algorithm. The results obtained can be used for further investigation of the ECM factorization algorithm using GPU.

• РЕФЕРАТ
• ABSTRACT
• СОДЕРЖАНИЕ
• ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
• ВВЕДЕНИЕ
• 1ОБЗОР АЛГОРИТМОВ ФАКТОРИЗАЦИИ ЦЕЛЫХ ЧИСЕЛ
  • 1.1Исследование алгоритмов на предмет реализации в ни
    • 1.1.1Алгоритмы с тривиальным параллелизмом, но неприемл
    • 1.1.2Наиболее эффективные алгоритмы (GNFS/SNFS) со слож
    • 1.1.3Алгоритмы с умеренной сложностью и ограниченным па
    • 1.1.4ECM — алгоритм с идеальной структурой для параллел
  • 1.2Основные термины и определения для понимания алгор
  • 1.3Оценка сложности вычислений с использованием разли
  • 1.4Вычисление кратной точки эллиптической кривой
  • 1.5Алгоритм факторизации ECM
  • 1.6Выводы
• 2МЕТОДЫ МОДИФИКАЦИИ АЛГОРИТМА ФАКТОРИЗАЦИИ ECM ДЛЯ
  • 2.1CUDA в качестве фреймворка для использования GPU
  • 2.2Критерии выбора GPU и анализ аппаратных характерис
  • 2.3Особенности реализации алгоритма ECM с использован
    • 2.3.1Выбор оптимального решения для возможности использ
      • 2.3.1.1Конкретные архитектурные решения
    • 2.3.2Особенности работы с памятью в программе на CUDA
    • 2.3.3Анализ структур данных и паттернов доступа в ECM
    • 2.3.4Анализ алгоритма ECM на предмет стратегии параллел
    • 2.3.5Стратегия ускорения для архитектуры GPU
    • 2.3.6Ограничения и компромиссы
    • 2.3.7Анализ параметров запуска ядра алгоритма
  • 2.4Выводы
• 3ТЕСТИРОВАНИЕ РАЗРАБОТАННОГО ПРОГРАММНОГО ПРОТОТИПА
  • 3.1Описание тестового стенда
  • 3.2Выбор эталонных библиотек для сравнения
    • 3.2.1Методология тестирования и анализ результатов
  • 3.3Результаты сравнения скорости работы разработанног
  • 3.4Анализ классов чисел с особыми свойствами для тест
  • 3.5Выводы
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ