Discrete Mathematics and Selected Topics in Cryptography Field of study: Applied Computer Science
Programme code: W4-S1IS19.2023

Module name: Discrete Mathematics and Selected Topics in Cryptography
Module code: W4-IS-S1-MDEK
Programme code: W4-S1IS19.2023
Semester:
  • winter semester 2025/2026
  • winter semester 2024/2025
Language of instruction: Polish
Form of verification: exam
ECTS credits: 5
Purpose and description of the content of education:
Celem przedmiotu jest zaznajomienie z zagadnieniami związanymi z matematyka dyskretną oraz przedstawienie podstaw teoretycznych współczesnej kryptografii a także przedstawienie głównych problemów dotyczących kryptografii wraz z odpowiednimi algorytmami stosowanymi w rozwiązaniach. Realizowane treści: 1. Elementy teorii liczb: liczby pierwsze, jednoznaczność rozkładu, NWD, algorytm Euklidesa, równania diofantyczne; kongruencje, arytmetyka modularna, ciała skończone, logarytm dyskretny, małe twierdzenie Fermata i twierdzenie Eulera; sito Eratostenesa, testy pierwszości, algorytm Rabina, rozkład liczby na czynniki, algorytm Fermata. 2. Elementy kryptografii: problem logarytmu dyskretnego, szyfr Cezara, algorytm szyfrujący RSA, algorytm ElGamala i warunki ich bezpieczeństwa, protokół Diffiego - Hellmana. Funkcja skrótu, podpis cyfrowy i uwierzytelnianie. 2. Kombinatoryka: wariacje, permutacje, kombinacje; symbole dwumianowe Newtona i ich własności. Algorytmy generujące proste obiekty kombinatoryczne: permutacje, wariacje, podzbiory zbioru; generowanie losowych obiektów kombinatorycznych; złożoność obliczeniowa i przykłady zastosowań takich algorytmów. 3. Metody zliczania obiektów: metoda bijektywna; reguła włączania i wyłączania; rekurencja i funkcje tworzące, liczby Fibonacciego. 4. Elementy teorii grafów: podstawowe pojęcia; minimalne drzewo rozpinające; problem minimalnych odległości; grafy Eulera i Hamiltona, problem komiwojażera.
List of modules that must be completed before starting this module (if necessary): not applicable
Learning outcome of the module Codes of the learning outcomes of the programme to which the learning outcome of the module is related [level of competence: scale 1-5]
zna i rozumie znaczenie zastosowań matematyki dyskretnej w informatyce [W4-IS-S1-MDEK_01]
 IS1_W01 [4/5] IS1_W02 [3/5]
zna podstawowe pojęcia i metody obliczeniowe elementarnej teorii liczb [W4-IS-S1-MDEK_02]
 IS1_W01 [4/5] IS1_W02 [4/5]
zna i opisuje szyfry klasyczne oraz podstawowe kryptosystemy z kluczem publicznym i wyjaśnia matematyczne podstawy ataku na nie [W4-IS-S1-MDEK_03]
 IS1_W01 [3/5] IS1_W03 [3/5]
zna pojęcia kombinatoryki i algorytmy kombinatoryczne [W4-IS-S1-MDEK_04]
 IS1_W02 [4/5]
zna pojęcia związane z teorią grafów [W4-IS-S1-MDEK_05]
 IS1_W01 [3/5]
potrafi zastosować algorytm Euklidesa do rozwiązywania równań diofantycznych liniowych i układów równań kongruencyjnych, potrafi zastosować poznane metody testowania liczb pierwszych i rozkładu liczb na czynniki pierwsze [W4-IS-S1-MDEK_06]
 IS1_U01 [3/5] IS1_U05 [4/5]
potrafi analizować ataki na RSA i wyjaśnić podstawy matematyczne ataków na szyfry klasyczne i szyfry asymetryczne [W4-IS-S1-MDEK_07]
 IS1_U01 [3/5] IS1_U08 [4/5]
potrafi zastosować właściwe schematy kombinatoryczne do rozwiązywania problemów informatycznych i przeprowadzić konieczne obliczenia przy pomocy poznanych metod i algorytmów [W4-IS-S1-MDEK_08]
 IS1_U01 [3/5] IS1_U05 [3/5]
potrafi zastosować terminologię i algorytmy teorii grafów do rozwiązywania problemów informatycznych [W4-IS-S1-MDEK_09]
 IS1_U01 [3/5] IS1_U05 [3/5]
jest świadom istniejących zagrożeń dla bezpieczeństwa informacji [W4-IS-S1-MDEK_10]
 IS1_K01 [3/5] IS1_U08 [3/5]
Form of teaching Number of hours Methods of conducting classes Assessment of the learning outcomes Learning outcomes
lecture [IS-S1-MDEK_fs_1] 15 Formal lecture/ course-related lecture [a01] 
Screen presentation [c07]  		exam W4-IS-S1-MDEK_01 W4-IS-S1-MDEK_02 W4-IS-S1-MDEK_03 W4-IS-S1-MDEK_04 W4-IS-S1-MDEK_05
discussion classes [IS-S1-MDEK_fs_2] 45 Activating method – peer learning [b08] 
Laboratory exercise / experiment [e01]  		course work W4-IS-S1-MDEK_06 W4-IS-S1-MDEK_07 W4-IS-S1-MDEK_08 W4-IS-S1-MDEK_09 W4-IS-S1-MDEK_10
The student's work, apart from participation in classes, includes in particular:
Name Category Description
Literature reading / analysis of source materials [a02] Preparation for classes
reading the literature indicated in the syllabus; reviewing, organizing, analyzing and selecting source materials to be used in class
Developing practical skills [a03] Preparation for classes
activities involving the repetition, refinement and consolidation of practical skills, including those developed during previous classes or new skills necessary for the implementation of subsequent elements of the curriculum (as preparation for class participation)
Consulting materials complementary to those indicated in the syllabus [a04] Preparation for classes
agreeing on materials complementary to those indicated in the syllabus, supporting the implementation of tasks resulting from or necessary for class participation
Determining the stages of task implementation contributing to the verification of learning outcomes [c01] Preparation for verification of learning outcomes
devising a task implementation strategy embracing the division of content, the range of activities, implementation time and/or the method(s) of obtaining the necessary materials and tools, etc.
Studying the literature used in and the materials produced in class [c02] Preparation for verification of learning outcomes
exploring the studied content, inquiring, considering, assimilating, interpreting it, or organizing knowledge obtained from the literature, documentation, instructions, scenarios, etc., used in class as well as from the notes or other materials/artifacts made in class
Analysis of the corrective feedback provided by the academic teacher on the results of the verification of learning outcomes [d01] Consulting the results of the verification of learning outcomes
reading through the academic teacher’s comments, assessments and opinions on the implementation of the task aimed at checking the level of the achieved learning outcomes
Development of a corrective action plan as well as supplementary/corrective tasks [d02] Consulting the results of the verification of learning outcomes
reviewing and selecting tasks and activities enabling the elimination of errors indicated by the academic teacher, their verification or correction resulting in completing the task with at least the minimum passing grade
Attachments
Module description (PDF)
Information concerning module syllabuses might be changed during studies.
Syllabuses (USOSweb)
Semester Module Language of instruction
(no information given)