Predmet Kriptografija in teorija kodiranja - 19. dec. 2003

Povzetek predavanja:
nadaljevali smo s 4. poglavjem:

• dokaz Gaussovega izreka o kvadratni recipročnosti praštevil z Eisensteinovo lemo
• Miler-Rabinov test za testiranje praštevilskosti
• Napadi na RSA (naključne napake)
• Rabinov kriptosistem (varnost zagotovljena z Las Vegas algoritmom)
• algoritmi za faktorizacijo (požresna metoda, Pollardova metoda)

Prosojnice si lahko ogledate ali pa jih izpišete (po 8 na eno stran).

Dodatna gradiva:

• Ključna vloga (problema praštevil) v kriptografiji:
  Metode za ugotavljanje, ali je neko število praštevilo, so pritegovale matematike od antičnih časov dalje. Razumeti praštevila je namreč ključnega pomena za reševanje številnih pomembnih matematičnih problemov. V zadnjem času pa se je pozornost usmerila na teste, ki jih lahko zaženemo na računalniku, saj takšne teste uporabljamo pri šifriranju digitalnih podatkov in pri digitalnih podpisih. Npr. testiranje praštevilskosti igra ključno vlogo v vseh razširjenih kriptosistemih z javnimi ključi, npr. RSA, DH, EC-DH. Varnost prvega je zasnovana na težavnosti iskanja deliteljev danega števila, varnost preostalih dveh pa na osnovi težavnosti diskretnega logaritma. Ti kriptosistemi se uporabljajo za varne transakcije in digitalno podpisovanje preko interneta ali s pametnimi karticami.

  Pogosto moramo izbrati praštevilo na določenemu intervalu. Toda ko ga najdemo, kako lahko dokažemo, da je v resnici praštevilo? En največjih matematikov, Karl Friedrich Gauss (1777-1855), je v svoji knjigi Disquistiones Arithmeticae (1801) zapisal: "Menim, da čast znanosti narekuje, da z vsemi sredstvi iščemo rešitev tako elegantnega in tako razvpitega problema."

  Od leta 1960 dalje se je s prihodom računalnikov pomaknil poudarek od iskanja matematične formule do iskanja učinkovitega algoritma (recept za iskanje po korakih).

  Glej DELO, Znanost, sept. 2002, str.9.

• Marko Petkovšek, Rešitev problema praštevil, Presek 30 (2002/03), str. 155 in II. stran ovitka.
• Tadej Novak, Odločitveni problem PRATEVILO, Obz. mat. fiz. 50/5(2003), str. 129-143.

• F. Bornemann, PRIMES Is in P: A Breakthrough for Everyman, AMS Notices 50/5 (May 2003), 245-252 (237K).

• Andrew Granville of the Université de Montréal discussed the recently published "polynomial time primality test" of Manindra Agrawal, Neeraj Kayal and Nitin Saxena. Their algorithm--referred to as AKS--decreased the amount of time to determine the primality of a number n from d^{(log log d)} to approximately (log n)^7.5 or d^7.5 steps, where d is roughly (log n)/(log 2). Granville provided both the proof of this test and an historical context for this discovery by building on ideas likely to be familiar to anyone having taken a course in undergraduate number theory. In this way, he held one's attention all the way to his "stop the presses" punch-line revelation of an improved result by Lenstra and Pomerance: a new algorithm with an even faster running time of (log n)⁶.
  Glej ps , pdf.

Domače naloge: