Магията на простите числа - 2012/2013

Конспект

1. Разлагане на числата на прости множители. Алгоритъм на Евклид. Делимост на целите числа. Най-голям общ делител и най-малко общо кратно на няколко числа. Алгоритъм на Евклид и приложения. Основна теорема на аритметиката.
2. Числови сравнения. Основни понятия. Свойства на сравненията.
3. Прости числа и съвършени числа. Разпределение на простите числа. Решето на Ератостен. Съвършени числа. Числа  на Мерсен и Ферма.
4. Теореми на Ферма и Ойлер. Псевдопрости числа. Теорема на Ферма. Бързо степенуване. Функция на Ойлер. Теорема на Ойлер.
5. Китайска теорема за остатъците. Сравнения и системи сравнения от първа степен с едно неизвестно. Китайската теорема за остатъците. Случай на модули, които не са взаимно прости. Свойства на функцията на Ойлер.
6. Криптосистемата RSA. Основна идея. Примери. Атаки срещу RSA. 
7. Криптография, базирана на теорията на квадратичните остатъци. Квадратни сравнения с едно неизвестно. Квадратични остатъци и неостатъци. Символи на Льожандър и Якоби. Закон за реципрочност на квадратичните остатъци. Алгоритъм за хвърляне на монета по телефона. Криптосистема на Голдвасер-Микали.
8. Техники за разлагане на числата като произведение на прости множители. Алгоритъм на Ферма. Подобрение на Крайчик. Два алгоритъма на Полард.

Литература

1. Bressoud, David M., Factorization and Primality Testing, Springer-Verlag, 1989.

Учебни материали

Резултати от писмени тестове