Кухни по поръчка | Съвети за мода и красота | Ваучери за намаления

Училищната парабола може да умножава числа

Геометричен трик с права линия през две точки разкрива връзката между параболата и криптографията върху елиптични криви

Училищната парабола y=x^2 може да се използва за умножение на числа – достатъчно е да се изберат две точки на графиката и да се прекара права линия през тях. Мястото, където правата пресича вертикалната ос, дава резултата от умножението. Това показва връзка между геометрията и аритметиката, която стои в основата на по-сложна математика, използвана в криптографията върху елиптични криви.

Например, за да се изчисли 3 × 4, на параболата се избират точките (-3, 9) и (4, 16). Координатата y на първата точка е 9, защото (-3)^2 = 9, а на втората е 16, защото 4^2 = 16. Ако точките се свържат с права линия, тя пресича оста y при стойност 12, което дава познатия резултат 3 × 4 = 12.

Редът на множителите не променя нищо – ако вместо (-3, 9) и (4, 16) се вземат (-4, 16) и (3, 9), правата отново пресича вертикалната ос при y=12. Правилото важи за произволни числа a и b: на графиката се отбелязват точките (-a, a^2) и (b, b^2), а координатата на пресечната точка с оста y е равна на произведението ab. Това може да се докаже математически, като се използва уравнението на правата y=mx+c и се покаже, че c=ab, когато a+b≠0. При a+b=0 двете точки съвпадат и не може да се прекара единствена права линия.

Такава геометрична конструкция работи и с нецели числа, но точността зависи от точността на чертежа – колкото по-сложни са координатите, толкова по-трудно е без изчисления да се определят точките и пресечната точка. Затова параболата е интересна преди всичко като нагледно доказателство за връзката между геометрията и аритметиката, а не като заместител на калкулатор.

От параболата към елиптичните криви

Подобен принцип – операции с числа, свързани с точки по крива – се среща и в съвременната криптография. Класически пример е RSA, която се основава на изчислителната сложност на факторизацията на произведението на големи прости числа: умножаването на известни прости числа е лесно, но намирането на първоначалните множители на много голямо произведение е много по-трудно. Криптографията върху елиптични криви използва друга математическа задача. Въпреки името си, елиптичната крива не прилича на елипса; в най-простата си форма над реалните числа тя се задава с уравнение от вида y^2=x^3+ax+b.

С точките на елиптичната крива може да се извършва операция на събиране. Геометрично, през две точки P и Q се прекарва права линия, която обикновено пресича кубичната крива в още една точка; тази точка се отразява спрямо оста x и се получава сумата P+Q. Ако трябва да се събере точка сама със себе си, през P се прекарва допирателна, намира се второто пресичане и то се отразява – това е удвояване на точката. Множественото събиране на една точка със самата нея се записва като Q=kP, където k е цяло число. Когато са известни P и k, Q може да се изчисли ефективно, но обратната задача – по известни P и Q да се определи k – е трудна и се нарича задача за дискретен логаритъм върху елиптична крива.

Реалните криптографски системи работят не върху непрекъсната равнина, а върху крайни полета, където координатите и аритметичните операции се подчиняват на модулни правила. Геометричната схема помага да се разбере принципът на събирането на точки, но практичните алгоритми използват краен набор от допустими стойности. При правилно избрани параметри задачата за дискретен логаритъм изисква огромен обем изчисления, което позволява криптографията върху елиптични криви да използва ключове с по-малък размер в сравнение с RSA при съпоставимо ниво на класическа сигурност. По-малките ключове означават по-малко данни за съхранение и предаване и често намаляват изчислителните разходи.

Връзката с училищната парабола не означава, че криптографските алгоритми директно умножават числа чрез графиката y=x^2. Общият принцип е, че точките върху кривите могат да бъдат снабдени с правила, които превръщат геометрията в аритметика – при параболата правата между две точки дава произведението по оста y, а при елиптичните криви операциите върху точките създават математическа структура, върху която се изграждат криптографските алгоритми.

Коментари
Все още няма коментари