YouTube

Got a YouTube account?

Νέο: ενεργοποιείστε μεταφράσεις και λεζάντες που δημιουργήθηκαν από θεατές στο κανάλι σας στο YouTube!

Polish υπότιτλους

← RSA Encryption step 3

Πάρτε τον Κωδικό ενσωμάτωσης
8 Γλώσσες

Showing Revision 1 created 10/24/2014 by Lech Mankiewicz.

  1. Ponad 2000 lat temu Euklides wykazał,
    że każda liczba

  2. ma dokładnie jeden rozkład na czynniki
    pierwsze. Uznajmy go za tajny klucz.
  3. Okazuje się, że rozkład na czynniki
    pierwsze to trudny problem.
  4. Wyjaśnijmy, co rozumiemy
    przez „łatwy” i „trudny”,
  5. wprowadzając pojęcie
    tzw. złożoności czasowej.
  6. Każdy z nas mnożył liczby
  7. i ma własne sposoby,
    żeby to przyspieszyć.
  8. Odpowiednio zaprogramowany komputer
  9. będzie mnożył liczby
    znacznie szybciej niż człowiek.
  10. Na wykresie przedstawiono
    czas potrzebny komputerowi
  11. do pomnożenia dwu liczb.
  12. Czas potrzebny
    do znalezienia odpowiedzi
  13. wydłuża się wraz ze wzrostem liczb.
  14. Zauważcie, że czas obliczeniowy
  15. jest znacznie krótszy od sekundy
    nawet przy dużych liczbach.
  16. Dlatego wykonanie jest „łatwe”.
  17. Porównajmy to z rozkładem
    na czynniki pierwsze.
  18. Gdyby ktoś kazał wam
    rozłożyć liczbę 589,
  19. od razu byście wiedzieli,
    że będzie trudno.
  20. Niezależnie od obranej strategii,
  21. metodą prób i błędów
    będziecie szukać liczby,
  22. przez którą
    bez reszty dzieli się 589.
  23. Pomęczycie się trochę i ustalicie,
    że ten rozkład to 19 razy 31.
  24. Gdyby kazano wam rozłożyć
    na czynniki pierwsze liczbę 437231,
  25. zapewne poddalibyście się
    i zaprzęgli do pomocy komputer.
  26. Uda się to przy małych wartościach,
  27. ale gdy każemy komputerowi
    rozkładać coraz większe liczby,
  28. wystąpi efekt lawiny.
  29. Czas potrzebny do wykonania obliczeń
  30. będzie rósł bardzo szybko,
    bo jest więcej etapów.
  31. W miarę wzrostu liczb, komputer
    będzie potrzebował minut, godzin…
  32. aż wreszcie - setek lub tysięcy lat,
  33. by przeprowadzić
    rozkład ogromnych liczb.
  34. Dlatego zadanie nazwiemy trudnym,
  35. z powodu czasu potrzebnego
    na znalezienie rozwiązania.
  36. Rozkładu na czynniki pierwsze
    użył Cocks w rozwiązaniu zapadkowym.
  37. Krok pierwszy: że Alicja losowo
    wygenerowała liczbę pierwszą
  38. o długości ponad 150 cyfr.
    Nazwijmy ją P1.
  39. Wygenerowała kolejną liczbę pierwszą,
    podobnej wielkości; nazwiemy ją P2.
  40. Teraz mnoży te liczby pierwsze
  41. i uzyskuje liczbę złożoną N,
  42. mającą ponad 300 cyfr.
  43. Mnożenie potrwa mniej niż sekundę;
  44. poradzi sobie z nim
    nawet przeglądarka internetowa.
  45. Potem Alicja
    bierze czynniki pierwsze N,
  46. czyli P1 razy P2, i ukrywa je.
  47. Gdyby podała komuś N,
  48. przez wiele lat
    komputerowo szukałby rozwiązania.
  49. Krok drugi:
    Cocks musiał znaleźć funkcję,
  50. która zależy od tego, czy znamy
    rozkład N na czynniki pierwsze.
  51. Sięgnął więc do opublikowanej
    w 1760 roku pracy
  52. szwajcarskiego matematyka
    Leonharda Eulera.