Aritmetika využívající zbytkové systémy
Název práce v češtině: | Aritmetika využívající zbytkové systémy |
---|---|
Název v anglickém jazyce: | Arithmetic using residue number systems |
Klíčová slova: | Montgomeryho redukce|pseudo-Mersennova prvočísla|modulární aritmetika|systémy zbytkových tříd |
Klíčová slova anglicky: | Montgomery arithmetic|pseudo-Mersenne primes|modular arithmetic|residue number systems |
Akademický rok vypsání: | 2024/2025 |
Typ práce: | bakalářská práce |
Jazyk práce: | |
Ústav: | Katedra algebry (32-KA) |
Vedoucí / školitel: | prof. RNDr. Aleš Drápal, CSc., DSc. |
Řešitel: |
Zásady pro vypracování |
Student objasní princip Montgomeryho aritmetiky. Vedle toho vyloží výhody počítání modulo pseudo-Mersennova a Solinasova prvočísla. Dále vysvětlí, jak se idea Montgomeryho redukce přenáší do výpočtů pomocí systémů zbytkových tříd, a vyhodnotí efektivitu výpočtů pomocí takových systémů ve srovnání s efektivitou výpočtů nad uvedenými speciálními tvary prvočísel.
The student will explain the principles of Montgomery arithmetic. Besides that he or she will explain advantages of computing modulo pseudo-Mersenne and Solinas primes. Furthermore, the student will explain how the idea of Montgomery arithmetic is being transferred to residue number systems, and will compare the efficiency of such computations in comparison with computations over the mentioned special classes of primes. |
Seznam odborné literatury |
Aleš Drápal: Algorithms over elliptic curves, Chapter Montgomery arithmetic
https://dl1.cuni.cz/course/view.php?id=12072 Jean Claude Bajard and Sylvain Duquesne: Montgomery-friendly primes and applications to cryptography https://hal.sorbonne-universite.fr/hal-02883333/file/BaDueprintversion.pdf Další literatura bude doplněna dle potřeby This list will be extended as needed |
Předběžná náplň práce |
Ve spodní vrstvě kryptografických aplikací vybudovaných nad prvočísly vždy je modulární aritmetika. Ta musí býr rychlá, a proto se prvočísla volí různých speciálních tvarů. To je dobře patrné například ze seznamu standardizovaných eliptických křivek, jak je uvádí NIST. Práce by měla poskytnout základní orientaci o metodách, které jsou pro rychlou modulární aritmetiku používány. |
Předběžná náplň práce v anglickém jazyce |
The lower core of cryptographic applications over primes always deals with modular arithmetic, which has to be fast enough. Because of that primes of special forms are being chosen. This is well documented by the list of standards for elliptic curves, as suggested by NIST. The thesis should give an overall orientation in methods that are being used for fast modular arithmetic. |