Comparative Analysis Of Integer Factorization Algorithms Using Cpu And Gpu

Authors : Gulida Kimsanova, Rita ISMAİLOVA, Rayimbek SULTANOV

Pages : 52-63

View : 15 | Download : 12

Publication Date : 2017-05-01

Article Type : Research Paper

Abstract :В данной работе была проведена оценка времени работы четырех алгоритмов целочисленной факторизации, а именно тривиального алгоритма факторизации, алгоритма Ферма, алгоритмов Полларда Ро и Брента. Реализация этих алгоритмов была выполнена тремя способами: на языке программирования c, на языке программирования c ++, используя библиотеку GMP 6.0.0 и на архитектуре CUDA для работы на ГПУ. Результаты показали, что алгоритм Ферма и тривиальный алгоритм деления имели самое быстрое время при параллельной реализации в архитектуре CUDA. Разница между временем выполнения факторизации при реализации на CUDA и реализации на GMP доходила до 10 раз. Разница между временем выполнения факторизации при реализации на c и c ++ была в основном связана с различиями в этих языках программирования.
Keywords : Целочисленная факторизация, ЦПУ, GMP, тривиальный алгоритм факторизации, алгоритм Ферма, алгоритм Полларда Ро, алгоритм Брента