Сайт о программировании, математике и моделировании
Записи с метками факторизация
Литература по программированию и криптографии
1 Декабрь
- Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черёмушкин А.В. Основы криптографии. М.: Гелиос АРВ, 2002. 2-е изд.
- Бондарев, Рублицкий, Качко. Основы программирования.
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.:МЦНМО, 2003.—328 с.
- Василенко О.Н. Применение круговых полей в криптосистемах RSA // IV Международная конференция «Современные проблемы теории чисел и ее приложения». Тула ,10-15 сентября, 2001 /Тезисы докладов. С 36—37. Читать дальше >
РО-алгоритм Полларда — алгоритм для факторизации чисел
1 Декабрь
В криптографии факторизацией называют разложение числа на простые множители. На предположении о вычисления сложности данного процесса основывается криптостойкость некоторых алгоритмов шифрования с открытым ключом, таких, как RSA, алгоритм на эллиптических кривых. Существует большое количество методов факторизации, которые отличаются вычислительной сложностью.
Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время доказано, что родственная задача о распознавании простоты числа является полиномиально разрешимой и для неё существует много эффективных тестов простоты.
Эти методы могут быть использованы в алгоритмах шифрования RSA, где вся секретная часть спрятана не в знании кода алгоритма, а в наличии ключа, длинного числа, подданного на «вход» алгоритма вместе с защищаемыми данными. Читать дальше >
