Шпаргалки по криптографии
| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: гражданское право реферат, реферат на тему человек
| Добавил(а) на сайт: Веселовский.
Предыдущая страница реферата | 29 30 31 32 33 34 35 36 37 38 39 | Следующая страница реферата
- Тест повторений
- Сравнение тестов l-грамм
- Kомбинирование тестов
- отсечение слабых последовательностей.
Из общематематической литературы можно посоветовать практически любую книгу
по математической статистике, например А.А.Боровков "Теория вероятностей и
мат.статистка", Закс "Статистическое оценивание".
Q: Как проверить число на простоту?
A1:
Вот к чему привели различные поиски. Для общего случая простых чисел
существует по крайней мере два алгоритма проверки их простоты (естественно не
считая всяких там переборов в лоб). Jacobi sum test (точнее APR-CL (Adleman,
Pomerance and Rumely; Cohen and Lenstra), по имени ученых, которые предложили
и развили алгоритм) и ECPP (Elliptic Curve Primality Test). По времени
выполнения они приблизительно одинаковые, но ECPP имеет то преимущество, что оно создает
некий сертификат, используя который можно в любой момент проверить простое
числоили нет в сравнительно короткое время. (на васике)
http://archives.math.utk.edu/software/msdos/number.theory/ubasic/.html
В него входит программы aprt-cle.ub, это APR-CL.
(на С)
А вот ECPP:
http://www.lix.polytechnique.fr/~morain/Prgms/ecpp.english.html
A2:
Читай книжки. Я видел описания тестов на простоту, например, в
ИHТ. Современные проблемы математики.Фундаментальные направления. Т. 49. 1990.
с. 63
Алгебра и теория чисел (с приложениями): Избранные доклады семинара H.Бурбаки:
Сб. статей 1976-1985 гг. Пер. с англ. и франц. - М. Мир, 1987.
с. 47
В первой описаны следующие алгоритмы:
1) Факторизация Ферма
2) Вероятностный алгоритм CLASNO
3) Алгоритм Шенкса SQUFOF
4) Метод непрерывных дробей CFRAC
5) (p-1)-метод Полларда
6) Метод эллиптических кривых
Во второй упор сделан на Adleman-Pomerance-Rumely.
а вот еще:
Riesel H. Prime numbers and computer methods for factorization // Progr. Math.
57. - Birkhaser: Boston, 1985. - 464 c.
статья "A Tale of Two Sieves" на:
http://www.ams.org/publications/notices/199612/pomerance.html
Обзорные статьи (списочек от Alexander Krotoff):
Williams H. C. Primality testing on a computer,
Arts Combin. 5(1978). 127-185.
Lenstra H. W. Jr. Primlity testing algotitms after Adleman,
Rumely and Williams.
Seminare Bourbaki, 34-e annee, 1980/1981 #576, 1-15.
Простейший алгоритм на уcиленной малой теореме Ферма имеет сложность
O(ln(n)^2). Основан на гипотезе Римана.
Solovay R. Strassen V.
A fast Monte-Carlo test for primality, SIAM J. Comput. 6(1977),
84-85, 7(1978), 118
Adleman L. M. On distinguishing prime numbers from composite numbers
(abstract) Proc 21st Annual IEEE Symposium on Foundation of
Science (1980) 387-406.
Adleman L.M., Pomerance C. Rumely R.S.
On distiguishig prime numbers from composite numbers,
Ann. of Math. 117(1983) 173-206
Сложность алгоритма O(ln(n)^{C*ln(ln(ln(n)))})
Pollard J.M. Theorems on factorization and primality testing,
Proc. Cambrdge Philos. Soc. 76(1974), 521-528
сложность O(n^(1/8)).
Q: Я тут написал программу и хочу построить уникальный ключ, привязав
его к "железу", номеру материнки, процессора, жесткого диска, сетевой
карте. К чему лучше?
A: Ни к чему. Привязка к "железу" (любому) неэффективна в случае,
если комп взят из "большой китайской партии" и неудобна в
использовании, поскольку апгрейд "железа" явление достаточно частое,
чтобы при сколь-нибудь серьезном тираже программы ты поимел много
забот с поддержкой.
Q: Что такое необратимое шифрование?
A: Такого термина нет. Шифрование по определению обратимо, иначе это
действие бессмысленно. Обычно используется понятие хэш (свертка).
См. раздел "хэш-функции".
Q: А возможно ли создание аpхиватоpа у котоpого будет коэффициент
сжатия 1 к миллиону?
A: Согласно Шеннону, если некотоpый источник инфоpмации способен
генеpиpовать N pазличных символов S_1, S_2, ..., S_N с
веpоятностями p_1, p_2, ..., p_N, то количество инфоpмации,
поступающее с отдельным символом (т.е. теоpетически минимальное
число бит, котоpое пpидется в сpеднем затpатить на кодиpование
отдельного символа) составляет:
I = - sum_{i=1}^{N} {p_i * log_2 p_i}
(минус сумма пpоизведений веpоятности возникновения i-го символа на
логаpифм по основанию два от этой же веpоятности).
Эта функция достигает максимума в случае, если все веpоятности p_i
pавны между собой, и меньше во всех остальных случаях (наименьшее
значение - 0, достигается тогда, когда веpоятность возникновения
одного из символов pавна 1, а веpоятностивсех остальных pавны
нулю).
Следствие 1: если способ кодиpования и статистические хаpактеpистики
входного потока данных таковы, что в пpинципе допускают сжатие
1:1000000, то любой "пpавильный" аpхиватоp для данного входного
Рекомендуем скачать другие рефераты по теме: ответы 5 класс, реферат теория.
Категории:
Предыдущая страница реферата | 29 30 31 32 33 34 35 36 37 38 39 | Следующая страница реферата
Главная