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

Конспект

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

Литература

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

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

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

 

Коментари

снимка на tpeneva

Публикувани са резултатите от писмения тест. Максималният брой точки на теста беше 10 точки. Всяка точка носи 0,10 към крайната оценка. Това означава, че ако успешно сте криптирали някакво съобщение до мен,  декриптирали сте изпратеното от мен съобщение и имате поне 6 точки на теста, получавате оценка Отличен (6). 

Ако искате да поправите оценката си на теста или да се явите на него за първи път, може да го направите всеки петък от 12:30 часа в каб. 443. В такъв случай, моля предварително да ме уведомите на tpeneva@uni-plovdiv.bg, за да не пиша оценка в протокола.
 

снимка на tpeneva

Очаквам вашите криптирани съобщения на tpeneva@uni-plovdiv.bg

За улеснение, в Учебни материали е публикуван протокол за криптиране и декриптиране на съобщения с криптосистемата RSA.