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

ВАЖНО! На 4.04.2016 г. от 13:00 часа в 443 каб. ще има поправка на теста. 

Конспект

1. ​Разлагане на числата на прости множители. Алгоритъм на Евклид. Делимост на целите числа. Най-голям общ делител и най-малко общо кратно на няколко числа. Теорема за деление с остатък. Алгоритъм на Евклид и приложения. Основна теорема на аритметиката. 

2. Числови сравнения. Основни понятия. Свойства на сравненията.

3. Прости числа и съвършени числа. Разпределение на простите числа. Решето на Ератостен. Съвършени числа. Числа на Мерсен и Ферма.

4. Теореми на Ферма и Ойлер. Псевдопрости числа. Теорема на Ферма. Бързо степенуване. Функция на Ойлер. Теорема на Ойлер. Генериране на редици от случайни битове.

5. Китайска теорема за остатъците. Сравнения от първа степен с едно неизвестно. Системи сравнения от първа степен с едно неизвестно. Китайската теорема за остатъците. Свойства на функцията на Ойлер.

6. Някои техники за разлагане на числата като произведение на прости множители. Алгоритъм на Ферма. Подобрение на Крайчик. Два алгоритъма на Полард.

7. Криптосистемата RSA. Основна идея. Криптиране и електронни подписи. Атаки срещу RSA.

8. Криптография, базирана на теорията на квадратичните остатъци. Квадратични остатъци и неостатъци. Символи на Льожандър и Якоби. Закон за реципрочност на квадратичните остатъци. Алгоритъм за „хвърляне на монета по телефона“. Криптосистема на Голдвасер-Микали и приложения.

9. Схема на Шамир за разпределение на частни ключове.

10. Електронно гласуване.

11. Доказателство с нулево разгласяване (zero-knowledge proof).

Литература

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

2. Начев, Н., Теория на числата, Пловдивско университетско издателство, 2002.

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

Резултати от изпити