Number Field Sieve for Discrete Logarithm
| Název práce v češtině: | Síto v číselném tělese pro diskrétní logaritmus |
|---|---|
| Název v anglickém jazyce: | Number Field Sieve for Discrete Logarithm |
| Klíčová slova: | Síto v číselném tělese, diskrétní logaritmus |
| Klíčová slova anglicky: | Number field sieve, discrete logarithm |
| Akademický rok vypsání: | 2012/2013 |
| Typ práce: | diplomová práce |
| Jazyk práce: | angličtina |
| Ústav: | Katedra algebry (32-KA) |
| Vedoucí / školitel: | doc. RNDr. Přemysl Jedlička, Ph.D. |
| Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
| Datum přihlášení: | 06.11.2012 |
| Datum zadání: | 06.11.2012 |
| Datum potvrzení stud. oddělením: | 23.11.2012 |
| Datum a čas obhajoby: | 11.02.2016 00:00 |
| Datum odevzdání elektronické podoby: | 04.12.2015 |
| Datum odevzdání tištěné podoby: | 04.12.2015 |
| Datum proběhlé obhajoby: | 11.02.2016 |
| Oponenti: | doc. Mgr. Pavel Příhoda, Ph.D. |
| Zásady pro vypracování |
| Síto v číselných tělesech je algoritmus používaný v rozkladech velkých čísel na prvočísla. V posledních letech se ovšem objevily práce uvádějící, jak je možno tento algoritmus použít pro řešení problému diskrétního logaritmu.
Úkolem této práce je porozumět, jak funguje síto v číselných tělesech u problému diskrétního logaritmu, s důrazem na rozdíly oproti jeho použití při faktorizaci. |
| Seznam odborné literatury |
| Oliver Schirokauer: "The impact of the number field sieve on the discrete logarithm problem in finite fields", Algorithmic Number Theory 44, (2008), 397-420
Antoine Joux, Reynald Lercier: "Improvements to the general number field sieve for discrete logarithms in prime fields. A comparison with the Gaussian integer method”, Math. Comp. 72:242 (2003), 953–967 Arjen Lenstra, Hendrik Lenstra (editors): The development of the number field sieve, Lecture Notes in Mathematics 1554, Springer, Berlin, 1993 |
| Předběžná náplň práce |
| Diskrétní logaritmus je problém, na němž je založeno mnoho kryptografických postupů, např. protokol Diffieho a Hellmanna. Síto v číselných tělesech je algoritmus, který se používá pro rozklad velkých čísel, ale ukazuje se, že jej lze použít i pro diskrétní logaritmus, kde je jedním z mála známých subexponenciálních algoritmů.
Jak popsat síto v číselných tělesech pro diskrétní logaritmus? Výhodou při vypracovávání práce bude, pokud by diplomant měl zároveň metodu naprogramovánu, neboť by měl i praktické zkušenosti s chováním algoritmu. Nicméně, takto velký program není možno naprogramovat během dvou let v plné šíři, proto je doporučeno využít algoritmu síta pro faktorizaci, který už byl pro katedru algebry naprogramován dříve kolektivem autorů (školitel byl mezi nimi). Proto je v zásadách práce výslovně uvedeno, že klíčové je porozumění rozdílům mezi sítem pro faktorizaci a sítem pro diskrétní logaritmus. |
| Předběžná náplň práce v anglickém jazyce |
| The discrete logarithm is a problem on which many cryptographical aproaches are based, i.e. the Diffie-Hellmann protocol. The number field sieve is an algorithm used for factorising large integers but it can be used for the discrete algorithm too; it is one of few known sub-exponential algorithms.
How to describe the number field sieve for the discrete logarithm? When tackling it, an advantage would be having the method written down - it would give some experience with the behaviour of the algorithm. Nevertheless, such a huge programme cannot be written in two years and it is thus recommended to use the number field sieve algorithm for the factorization that was developped a few years ago by a group of authors (the supervisor included). Therefore we require explicitely the comprehension of the difference between the sieve for factorisation and for the discrete logarithm. |