Текущ час:0:00Обща продължителност:2:58

Видео транскрипция

Преди 2000 години Евклид показва, че всяко число има точно един начин за разлагане на прости множители, за което можем да мислим като за таен ключ. Оказва се, че намирането на тези прости множители е фундаментално трудна задача. Да уточним, че с "трудно" и "лесно" имаме предвид т.нар. "сложност по време". Всички сме умножавали числа и всеки от нас има собствени правила за това, за да ускори нещата. Ако програмираме компютър да умножава числа, той може да го направи много по-бързо от всеки човек. Ето графика, която показва времето, което е нужно на един компютър да умножи две числа. И, разбира се, времето за намиране на отговора, нараства с големината на числата. Забележи, че времето за изчисление остава по-малко от секунда, дори за доста големи числа. Следователно операцията е "лесна" за изпълнение. Сега да сравним това с разлагането на множители. Ако трябва да разложиш на множители 589, ще забележиш, че задачата става по-трудна. Без значение от стратегията, ще трябва да има проби и грешки, докато намериш число, което да дели 589 без остатък. След известна борба ще откриеш, че разлагането на множители е 19 х 13. Ако трябва да разложиш на множители 437 231, вероятно ще се откажеш и ще потърсиш компютър, който да ти помогне. Това работи добре за малки числа, макар че ако използваме компютър, за разлагането на все по-големи и по-големи числа, се получава ефектът беглец. Времето, необходимо за изпълняване на изчисленията, нараства бързо, тъй като са необходими повече стъпки. С нарастване на числото, на компютъра му трябват минути, след това часове, накрая ще му трябват стотици или хиляди години, за да разложи голямо число на прости множители. Тогава казваме, че задачата е "трудна", заради нарастващото време за решаване. Ето защо Кокс използва разлагането, за да постои решението със секрет. Стъпка едно, представи си, че Алис генерира случайно просто число с дължина повече от 150 цифри. Наричаме го "р1". След това генерира второ случайно просто число с проблизително същия размер; наричаме го "р2". След това тя умножава двете числа и получава съставното число "N", което има над 300 цифри. Това умножение отнема по-малко от секунда; можем да го направим дори в браузъра. След това тя взима множителите на N р1 х р2, и ги скрива. Ако сега даде N на някого, той трябва да има компютър, който да работи с години, за да намери решението. Стъпка две, Кокс трябва да намери функция, която зависи от това да са известни множителите на N. За целта той се обръща към работата, свършена през 1760 година от швейцарския математик Леонард Ойлер.