Aritmetika využívající zbytkové systémy
| Thesis title in Czech: | Aritmetika využívající zbytkové systémy |
|---|---|
| Thesis title in English: | Arithmetic using residue number systems |
| Key words: | Montgomeryho redukce|pseudo-Mersennova prvočísla|modulární aritmetika|systémy zbytkových tříd |
| English key words: | Montgomery arithmetic|pseudo-Mersenne primes|modular arithmetic|residue number systems |
| Academic year of topic announcement: | 2024/2025 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | |
| Department: | Department of Algebra (32-KA) |
| Supervisor: | prof. RNDr. Aleš Drápal, CSc., DSc. |
| Author: |
| Guidelines |
| 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. |
| References |
| 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 |
| Preliminary scope of work |
| 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. |
| Preliminary scope of work in English |
| 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. |