Wprowadzenie do arytmetyki wielkich liczb [...]
Jakub Juszczakiewicz 
9. Sesja Linuksowa Pełny tytuł: „Wprowadzenie do arytmetyki wielkich liczb i jej zastosowanie w kryptoanalizie."
Dzień 2, wykład 3. Prowadził Jakub Juszczakiewicz.
Wykład omawia w rzeczywistości dwa zazębiające się zagadnienia: arytmetykę wielkich liczb, oraz problem rozkładu na czynniki pierwsze dużych liczb. Przez duże liczby rozumiemy takie, których reprezentacji binarnej nie da się zmieścić w pojedynczym rejestrze procesora. Oprócz podstawowych algorytmów, zwanych w literaturze jako szkolne, omówię bardziej wyrafinowane dla mnożenia i dzielenia. Bezpieczeństwo algorytmów takich jak RSA czy Blum Blum Shub jest bezpośrednio zależne od trudności problemu faktoryzacji. Tę kwestię poruszę w drugiej części, gdzie przedstawię kilka znanych algorytmów rozkładu na czynniki pierwsze.