Równania liniowe

Prowadzący: Jakub Nowak

Magiczne zastosowania algorytmu znajdowania małych całkowitych rozwiązań układu równań liniowych
Zadania kwalifikacyjne
Kategorie: informatyka matematyka

Opis

Podstawą całych warsztatów będzie algorytm znajdowania "małych" całkowitych rozwiązań układu równań liniowych.

Oznaczony układ równań liniowych ma dokładnie jedno rozwiązanie i jego znalezienie jest proste. Jeżeli jednak liczba niewiadomych jest większa od liczby (nietrywialnych) równań, wtedy liczba rozwiązań jest nieskończona. Możemy znaleźć najmniejsze rozwiązanie (tzn. o najmniejszej sumie kwadratów wartości niewiadomych) przy pomocy algorytmu simplex.

Ze względu na zastosowania chcemy się jednak ograniczyć do rozwiązań całkowitych. Okazuje się, że nieznany jest szybki algorytm znajdowania najmniejszego całkowitego rozwiązania. Poznamy jednak algorytm, który znajduje niekoniecznie najmniejsze, ale całkiem małe (cokolwiek to znaczy), rozwiązanie.

Pewnie po przeczytaniu tego wszystkiego zastanawiasz się, a na co mi to? A no, przy pomocy tego algorytmu rozwiążemy sobie parę zadanek CTF-owych z kategorii crypto. Poznamy też parę trików, jak sobie można radzić z nieliniowymi układami równań.

Podczas warsztatu, w ramach zadań, przyjrzymy się też istniejącym cryptosystemom, np. DSA.

W zależności od zainteresowania uczestników i czasu możemy przyjrzeć się bliżej metodzie Coppersmitha – ogólnej metodzie radzenia sobie z układami nieliniowymi, bądź innym interesującym cryptosystemom, np. NTRU.

Wymagania

  1. Linux;
    • VM też jest ok. Na Windowsie najwygodniej przez WSL 2. Jak ktoś potrzebuje pomocy z instalacją i/bądź obsługą, proszę o kontakt.
  2. Python 3;
  3. Podstawy SageMath (zadania kwalifikacyjne służą jako wprowadzenie);
  4. Macierze i pojęcia algebry liniowej (dokładna lista niżej);
  5. Arytmetyka modularna.

Powyższe wymagania są sprawdzane w zadaniach kwalifikacyjnych.

Używanie SageMath i Python nie jest konieczne, jeśli ktoś jest dobrze zaznajomiony z inną biblioteką do obliczeń matematycznych. Proszę tylko o sprawdzenie, czy istnieje implementacja algorytmu LLL w tej bibliotece. W takim wypadku można oddać zadania kwalifikacyjne w tym czymś innym. Nadal konieczna jest jednak — przynajmniej podstawowa — znajomość Pythona. Zastrzegam, że mogę nie być w stanie pomóc debugować kodu podczas i poza warsztatami.

Przydatne rzeczy

Tutorial SageMath:

Wykłady z algebry liniowej: GAL J. Chaber, R.Pol Wydział MIM UW

Fajne zadanka z crypto (niezwiązane z warsztatami): Cryptopals.

Kontakt

Zadania kwalifikacyjne wysyłamy przez stronę warsztatów. Wszelkie pytania, problemy, rozterki, sugestie, opinie, przemyślenia i dobre słowa można (i zaleca się) zgłaszać przez wybrane z poniższych mediów elektronicznych komunikacji na odległość (na maile czasem odpowiadam wolniej).

Email: j.nowak26+warsztatywww@student.uw.edu.pl

Discord: MrQubo#2852