Cel kształcenia i wykaz literatury

Główny cel kształcenia: Głównym celem kształcenia w ramach tego modułu zajęć jest przekazanie studentom matematycznych podstaw współczesnej kryptografii, która oparta jest w głównej mierze o twierdzenia teorii liczb oraz wykorzystuje właściwości struktur algebraicznych takich jak grupy, pierścienie oraz ciała liczbowe.

Ogólne informacje o zajęciach: Zajęcia mają formę wykładów i ćwiczeń tablicowych, na których poznawane są i badane rachunkowo różne pojęcia i twierdzenia teorii liczb. Wiedza ta pozwala studentom informatyki zrozumieć skomplikowane algorytmy testowania pierwszości liczb, reguły rozkładu liczb całkowitych na czynniki pierwsze, procedury działania kryptosystemów opartych o arytmetykę modularną.

Wykaz literatury, wymaganej do zaliczenia zajęć

Literatura wykorzystywana podczas zajęć wykładowych

1	Song Y. Yan	Teoria liczb w informatyce	Wydawnictwo naukowe PWN, Warszawa.	2006
2	Wacław Marzantowicz, Piotr Zarzycki	Elementarna teoria liczb	PWN.	2006
3	Marcin Karbowski	Podstawy kryptografii. Wydanie III	Helion.	2014

Literatura do samodzielnego studiowania

1

Andrzej Chrzęszczyk

Algorytmy teorii liczb i kryptografii w przykładach

Wydawnictwo BTC - Legionowo.

2010

Wymagania wstępne w kategorii wiedzy/umiejętności/kompetencji społecznych

Wymagania formalne: wpis na drugi semestr studiów magisterskich na kierunku Informatyka

Wymagania wstępne w kategorii Wiedzy: podstawowa wiedza w zakresie algebry i teorii liczb

Wymagania wstępne w kategorii Umiejętności: umiejętność wykonywania bez błędów złożonych obliczeń arytmetycznych, zdolność rozumienia abstrakcyjnych pojęć matematycznych

Wymagania wstępne w kategorii Kompetencji społecznych: systematyczność w pracy i wytrwałość w pokonywaniu trudności

Efekty kształcenia dla zajęć

MEK	Student, który zaliczył zajęcia	Formy zajęć/metody dydaktyczne prowadzące do osiągnięcia danego efektu kształcenia	Metody weryfikacji każdego z wymienionych efektów kształcenia	Związki z KEK	Związki z PRK
01	zna podstawowe twierdzenia teorii podzielności liczb	wykład, ćwiczenia rachunkowe	sprawdzian pisemny	K_U05+ K_K02+	P7S_KR P7S_UW
02	potrafi rozwiązywać liniowe równania diofantyczne metodą rozszerzonego algorytmu Euklidesa	wykład, ćwiczenia rachunkowe	sprawdzian pisemny	K_U05+ K_K02+	P7S_KR P7S_UW
03	potrafi obliczać wartość symbolu Jacobiego i Legendre'a	wykład, ćwiczenia rachunkowe	sprawdzian pisemny	K_U05+ K_K02+	P7S_KR P7S_UW
04	zna podstawowe własności kongruencji i twierdzenia arytmetyki modularnej	wykład, ćwiczenia rachunkowe	sprawdzian pisemny	K_U05+ K_K02+	P7S_KR P7S_UW
05	zna prawa działań na punktach leżących na krzywych eliptycznych	wykład, ćwiczenia rachunkowe	sprawdzian pisemny	K_U05+ K_U08+ K_K02+	P7S_KR P7S_UW
06	potrafi wyznaczyć rząd liczby naturalnej oraz sprawdzić, czy jest ona pierwiastkiem pierwotnym	wykład, ćwiczenia rachunkowe	sprawdzian pisemny	K_U05+ K_K01+ K_K02+	P7S_KK P7S_KR P7S_UW

Uwaga: W zależności od sytuacji epidemicznej, jeżeli nie będzie możliwości weryfikacji osiągniętych efektów uczenia się określonych w programie studiów w sposób stacjonarny w szczególności zaliczenia i egzaminy kończące określone zajęcia będą mogły się odbywać przy użyciu środków komunikacji elektronicznej (w sposób zdalny).

Treści kształcenia dla zajęć

Sem.	TK	Treści kształcenia	Realizowane na	MEK
2	TK01	Wprowadzenie do teorii liczb. Wiadomości wstępne z algebry. Oznaczenia stosowane w teorii liczb. Definicje grupy, pierścienia i ciała. Teoria podzielności liczb. Podstawowe pojęcia i własności podzielności. Zasadnicze twierdzenie arytmetyki - rozkład kanoniczny liczby naturalnej.	W1, W2, C1	MEK01
2	TK02	NWD i NWW pary oraz zbioru liczb. Podstawowy i rozszerzony algorytmy Euklidesa. Ułamki łańcuchowe.	W3, C2	MEK01
2	TK03	Liniowe równania diofantyczne. Równanie Pella. Rozwiązywanie równań liniowych metodą Euklidesa. Funkcje arytmetyczne fi, tau, sigma, mi. Arytmetyczne funkcje multiplikatywne i ich właściwości. Rozmieszczenie liczb pierwszych.	W4, W5, C3	MEK02
2	TK04	Teoria kongruencji. Kongruencje liniowe. Podstawowe pojęcia i własności kongruencji. Arytmetyka modularna. Małe tw. Fermata i tw. Wilsona. Chińskie tw. o resztach. Multiplikatywne odwrotności.	W6, W7, C4	MEK04
2	TK05	Kongruencje wyższych stopni. Symbol Legendre’a i symbol Jacobiego. Prawo wzajemności reszt.	W8, C5	MEK03
2	TK06	Rząd liczby całkowitej i pierwiastki pierwotne modulo. Indeksy i reszty k-tego stopnia.	W9, C6	MEK06
2	TK07	Podstawowe pojęcia dotyczące krzywych eliptycznych. Arytmetyka, czyli prawa działań na punktach leżących na krzywych eliptycznych. Wzory algebraiczne opisujące dodawanie punktów na krzywych eliptycznych. Zastosowania krzywych eliptycznych.	W10, C7	MEK05

Nakład pracy studenta

Forma zajęć	Praca przed zajęciami	Udział w zajęciach	Praca po zajęciach
Wykład (sem. 2)	Przygotowanie do kolokwium: 10.00 godz./sem.	Godziny kontaktowe: 20.00 godz./sem.	Uzupełnienie/studiowanie notatek: 5.00 godz./sem. Studiowanie zalecanej literatury: 10.00 godz./sem.
Ćwiczenia/Lektorat (sem. 2)	Przygotowanie do kolokwium: 10.00 godz./sem.	Godziny kontaktowe: 15.00 godz./sem.	Dokończenia/studiowanie zadań: 5.00 godz./sem.
Konsultacje (sem. 2)
Zaliczenie (sem. 2)

Sposób wystawiania ocen składowych zajęć i oceny końcowej

Forma zajęć	Sposób wystawiania oceny podsumowującej
Wykład	na podstawie pisemnego kolokwium zaliczeniowego oraz, w razie konieczności, na podstawie odpowiedzi ustnej
Ćwiczenia/Lektorat	na podstawie kilku krótkich sprawdzianów albo jednego większego - do uzgodnienia ze studentami
Ocena końcowa	średnia arytmetyczna ocen z wykładu i z ćwiczeń, obydwie muszą wynosić co najmniej 3,0

Przykładowe zadania

Wymagane podczas egzaminu/zaliczenia
(-)

Realizowane podczas zajęć ćwiczeniowych/laboratoryjnych/projektowych
(-)

Inne
(-)

Czy podczas egzaminu/zaliczenia student ma możliwość korzystania z materiałów pomocniczych : tak

Dostępne materiały : Notatki z wykładów oraz z ćwiczeń.

Treści zajęć powiazane są z prowadzonymi badaniami naukowymi: nie