Obsahuje:
  • všechny e-ziny od 9/1999
  • celou databázi NEWS
  • soutěže 2000-2011
  • další články a BONUSY

Crypto - News

http://crypto-world.info

Crypto - News | Security - News

09 / 2004
Vybrali pro vás: TR - Tomáš Rosa, JP - Jaroslav Pinkava, PV - Pavel Vondruška, VK - Vlastimil Klíma

Riemannova hypotéza - podle Louise de Branges

08.09.2004
Na webu univerzity Purdue si m?žete p?e?íst výklad pana de Brangese k jeho chápání Riemannovy hypotézy. Pokud bude d?kaz ov??en, získá autor slávu (a také p?íslušnou cenu).
Spekulace, které se objevují v souvislosti s tímto výsledkem jsou však pon?kud pochybené.
Jediná známá souvislost s kryptografií je vztah k známému Milerovu testu na prvo?íselnost (ov??ení zda dané ?íslo p je prvo?íslem, tj. jeho jedinými d?liteli jsou jedni?ka a samotné p).
Odpovídající tvrzení zní: Pokud platí Riemannova hypotéza, pak daný test má polynomiální výpo?etní složitost.
V té dob? (Miller?v ?lánek je z roku 1976) to byl významný výsledek, žádný test na prvo?íselnost, který by m?l prokázanou polynomiální složitost znám tehdy nebyl a nebyl znám ani dlouho potom. Modifikovaný Miller-Rabin?v test se stal jedním z nejužite?n?jších test? na prvo?íselnost.
V kryptografii má toto samoz?ejm? význam pro ta schémata, která se o využití prvo?ísel opírají (je to fakticky celá dnešní kryptografie s ve?ejným klí?em).
Zatímco však Miller?v výsledek nic neztratil na svém praktickém významu (Miller-Rabin?v test je v praxi nejpoužívan?jším nástrojem), teoretický význam výsledku byl p?ed dv?ma lety zastín?n výsledkem indických matematik? - Manindra Agrawal, Neeraj Kayal a Nitin Saxena PRIMES is in P. Tento výsledek potvrdil, že složitost úlohy - ov??it zda dané ?íslo je prvo?íslem - má polynomiální charakter. Tedy jestliže dnes n?kdo prokáže, že Riemannova hypotéza platí, pak je tedy i prokázáno, že Miller?v algoritmus má polynomiální charakter. To je však pln? v souladu s výsledkem indických matematik?. Tento výsledek je znám již dva roky a žádná revoluce se v kryptologii díky n?mu nekonala.
Algoritmy pro testování na prvo?íselnost mají v kryptologii konstruktivní charakter (umož?ují vytvá?et konkrétní podobu šifrovacích algoritm?) a není zatím znám jejich jakýkoliv dopad na kryptoanalytické postupy (destruktivní, luštitelský pohled).
Zdroj: http://www.math.purdue.edu/ftp_pub/branges/apology.pdf
Autor: JP


Design: Webdesign