Seminar iz kriptografije - 30. marec 1998

povzetek predavanja | dodatna gradiva | domače naloge

Povzetek predavanja:

Arijana Žitnik je končala s 4. poglavjem

Rabinov kriptosistem
algoritmi za faktorizacijo

rešitve nalog 4. poglavja
A.J.: dodatne naloge

Prosojnice Arijane Žitnik si oglejte, ali pa jih izpišite (4 na eno stran).
Organizacijske prosojnice (od A.J.) si lahko ogledate, ali pa jih izpišete (8 na eno stran).

Dodatna gradiva: Sekcija 4.2:

Dober uvod v teorijo števil predstavlja:
- K. Rosen, Elementary Number Theory and its Applications, Addison-Wesley, 3rd edition, 1992.
Sledi knjiga iz teorije števil in njene uporabe v kriptografiji:
- N. Koblitz, A Course in Number Theory and Cryptography, Springer Verlag, 2nd edition, 1994.
Bolj zahtevna knjiga s tega področja je:
- K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, Springer Verlag, 2nd edition, 1990.

Sekciji 4.5 in 4.8:

Domača stran o praštevilih (informacije o praštevilih)

Citat Hendrika Lenstre (1985):
Quote from Hendrik Lenstra (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 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 (do naslednjega tedna):

preberite 5. poglavje (do str. 190),
nadaljujte z reševanjem nalog 4. poglavja