Тема: Параллельные методы решения задач факторизации

В данной работе будут рассмотрены следующие алгоритмы факторизации: алгоритм Ленстры, алгоритм Полларда, квадратичное решето Померанца. Под факторизацией будем понимать декомпозицию объекта, а именно разложение натурального числа в произведение простых чисел. Единственность и существование следует из основной теоремы арифметики.
Факторизация целых чисел является задачей довольно-таки большой сложности, в особенности для больших чисел. До сих пор неизвестен алгоритм, который позволяет быстро факторизовать довольно большое число (порядка 32 знаков и больше). Факторизация лежит в основе многих алгоритмов шифрования, таких как RSA и алгоритм электронно - цифровой подписи. Отсюда вытекает актуальность данной работы.
В данной работе будет поставлено множество экспериментов по факторизации целых чисел, а также будет проведено тестирование параллельных алгоритмов факторизации и их сравнение по эффективности с обычными алгоритмами.
Целью дипломной работы является изучение параллельных методов решения задач факторизации. Данные методы должны допускать эффективное распараллеливание на многопроцессорных вычислительных системах с массовым параллелизмом, демонстрируя масштабируемость, близкую к линейной. Исследуемые алгоритмы теоретически должны работать быстрее в зависимости от входных данных.
Актуальность работы обоснована тем, что в настоящее время программные продукты, использующие параллельные технологии, не так широко развиты в мире.

Купить

По полученным данным можно сделать вывод, что метод квадратичного решета без параллельной реализации работает быстрее остальных методов даже с . Однако этот метод в некоторых случаях уступает методу факторизации Ленстры на эллиптических кривых. На практике выбор границы для метода Ленстры и решета Померанца вызывают затруднения, так как теоретическая оценка этих границ является слишком большой и на практике ее не используют.
Из трех реализаций методов Ро Полларда лучшей оказалась та, в которой случайно выбираются коэффициенты полинома.
На практике метод квадратичного решета оказывается в два раза быстрее метода Ро Полларда.
Купить