Predmet Kriptografija in teorija kodiranja - 7. III. 2008
predavanja: nazaj
| naprej
povzetek predavanja | dodatna
gradiva | domače naloge
Povzetek predavanja:
Drugi kriptosistemi z javnimi ključi (pričetek 5. poglavja)
- ElGamalovi protokoli in shema Massey-Omura
- problem diskretnega logaritma
- algoritmi za računanje diskretnega logaritma:
- metoda velikega koraka malega koraka,
- Pohlig-Hellmanov algoritem,
- varnost bitov pri diskretnem logaritmu
- računanje v končnih obsegih
(polinomska baza, trinomi, normalna baza,
optimalna normalna baza)
Dodatna gradiva:
Domača stran o
praštevilih (informacije o praštevilih)
Citat Hendrika Lenstre (1985):
"Suppose that 2 100-digit numbers
p and q have been proved prime. Suppose moreover that
p and q are thrown away by mistake, but their product
pq is saved. How to recover p and q? It must be
felt as a defeat for mathematics that, in these circumstances, the most
promising approaches are searching the waste paper basket and applying
mnemo-hypnotic techniques."
Razno:
- RSAjevi izzivi za faktorizacijo.
Ponujene so bile denarne nagrade za faktorizacijo naravnih števil
različnih velikosti.
- 1994: z uporabo algoritma za faktorizacijo s kvadratnim rešetom
je faktorizirano 129 mestno decimalo število (425 bitov) (izziv RSA-129).
- 1996: z uporabo algoritma za faktorizacijo s NF (number field)
rešetom je faktorizirano 130 mestno decimalo število (izziv RSA-130).
Domače naloge
- Dokaži, da je kompleksnost matrike za množenje normalne baze
vsaj 2n-1 (tj. število neničelnih elementov).