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