Test

  • 13 марта 2012 г.
  • 1841 Слова
«Вятский государственный гуманитарный университет» 
Факультет информатики, математики и физики 
Кафедра прикладной математики и информатики 








Выпускная квалификационная работа

«Параллельные алгоритмы компьютерной алгебры»






Выполнил студент группы ПМ-51:
Маслов Дмитрий НиколаевичНаучный руководитель:
Разова Е.В.

Подпись научного руководителя:________

Работа допущена к защите:_____________ 

(дата)________________2012г. 






Киров
2012г.

Содержание.Введение…………………………………………………………………………..3

Глава 1: Алгоритмические проблемы
и методы их решения ………………………...………….…….…….4

1.1. Система шифрования RSA …………...……………………….…….…….4


1.2. Построение больших простых чисел …………..….…..………………....8


1.3. Нахождение взаимно простых чисел …..…………….…..……...……...12


1.4. Решение уравнения a * x + b * y =1……..………………..…………...…12


1.5. Большие числа и работа с ними …………………...….….……………..14


1.6. Факторизация числа ……………….…..……………….….……………..16


Глава 2: Исследование возможности
распараллеливания алгоритмов компьютерной алгебры………....……..22

2.1. Алгоритмы работы с большими числами……………...………………22


2.2. Алгоритм Миллера-Рабина……………….……………...………………22


Заключение……………………………………………………………………...25


Списоклитературы…………………………………………………………….26

Введение.



Алгоритмы компьютерной алгебры находят применение при решении задач во многих сферах деятельности. В частности они широко используются в криптографии и служат для разрешения многих алгоритмических проблем, возникающих в этой области. Рассмотрение алгоритмов компьютерной алгебры на примере именно криптографии не случайно. Криптография очень важна в современном мире. Без нее нельзя обойтисьпри защите данных, которые следует передать по открытым каналам связи, а также там, где приходиться подтверждать целостность информации или доказывать ее авторство. Важным аспектом криптографии является скорость. Криптосистемы будут цениться гораздо меньше, если скорость шифрования будет сравнима со скоростью их взлома.


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


В настоящее время с развитием технологий и появлением все более мощных многопроцессорных вычислительных комплексов, идеяраспараллеливания алгоритмов компьютерной алгебры выглядит перспективной и актуальной.


Целью данной работы являются рассмотрение алгоритмов компьютерной алгебры, применяющихся в криптографии, исследование возможности их распараллеливания и анализ эффективности применения параллельных реализаций в криптографии.

Глава 1. Алгоритмические проблемы
и методы их решения

1.1. Система шифрования RSAСистема RSA, название которой происходит от первых букв фамилий авторов, Рон Ривеста, Ади Шамира и Леонардо Адлемана, является наиболее распространенной и изученной криптосистемой с открытым ключом. Она основана на использовании того факта, что легко перемножать два больших простых числа, в то же время крайне трудно разложить на множители их произведение. В результате произведение может бытьиспользовано в качестве элемента открытого ключа зашифрования. Исходные простые числа необходимы для расшифрования, при этом задача их восстановления до сих пор сопротивляется всем атакам криптоаналитиков. Таким образом, имеются хорошие предпосылки для построения односторонней функции с секретом.


Рассмотрим RSA...
tracking img