KNOW INTUIT, Лекция, Основи на теорията на числата, използвана в криптографията с публичен ключ
Целта на лекцията: да напомни на читателя основните положения на теорията на числата, използвани в криптографията с публичен ключ
Прости и съставни числа
Всяко естествено число, по-голямо от 1, се дели на поне две числа: 1 и себе си. Ако едно число няма делители, освен себе си и единица, то се наричапросто, а ако числото има повече делители, тогавасъставно. Единицата не се счита нито за просто число, нито за съставно число. Например числата 7, 29 са прости; числата 9, 15 са съставни (9 се дели на 3, 15 се дели на 3 и 5).
Интересен факт: ако две прости числа се различават с 2, тогава те се наричат числа "близнаци". Числата-"близнаци" не са много. Например "близнаци" са 5 и 7, 29 и 31, 149 и 151, както и 242 206 083*2 38 880 ±1 (най-голямата двойка "близнаци", открита по време на писане на урока).
Не всяко число може веднага да се каже дали е просто или съставно. Ако числото е по-малко от сто, тогава най-вероятно можем веднага да отговорим на този въпрос. При големите числа обаче нещата са по-сложни. Вземете например числото 2009. Просто ли е или сложно? Нека се опитаме да намерим възможните делители на това число сред първите прости числа. 2009 определено не се дели на 2 (тъй като е нечетно), на 3 (тъй като сумата от цифрите му 2+9=11 не се дели на 3), на 5 . Но като се опитаме да разделим 2009 на 7, ще видим, че резултатът е цял резултат - 287. Така се получава отговорът: числото 2009 е съставно. В този случай отговорът беше получен доста бързо. Случва се проверката за основност да отнеме много повече време и дори са необходими специални компютърни програми за работа с големи цели числа.
Намирането на голям просточислата са важни за математиката и не само. Например в криптографията големи прости числа се използват в алгоритми за криптиране с публичен ключ. За да се гарантира силата на криптирането, там се използват прости числа с дължина до 1024 бита.
Умножаването на две числа е относително лесно, особено ако имаме калкулатор и числата не са много големи. Има и обратна задача -задача за разлагане на множители- намиране на две или повече числа, които дават дадено число при умножение. Тази задача е много по-трудна от умножението на числа и всеки, който се е опитвал да я реши, знае това. Например, ако от нас се изисква да умножим 67 по 113, тогава резултатът, 7571, вероятно ще бъде получен за по-малко от минута. Ако от нас се изисква да намерим две числа, чийто продукт е равен на 7571, тогава най-вероятно ще ни отнеме много повече време.
Търсенето на множители на числото n може да се извърши например чрез изброяване на всички прости числа до както в горния пример с числото 2009. Въпреки това, ако факторите са големи прости числа, тогава ще отнеме много време, за да ги намерите.
По този начин разлагането на голямо число отнема много време, дори когато е известно, че е продукт на две големи прости числа.
Сложността на проблема за факторизиране се използва в някои криптографски алгоритми, като системата за криптиране RSA.
Основна теорема на аритметиката
Всяко съставно число може да бъде съставено от определен брой прости числа с помощта на умножение. Например, съставното число 2009 може да се получи по следния начин:
В математиката се разглежда така нареченатаосновна теорема на аритметиката, която гласи, че всяко естествено число ( n>1) или само по себе си е просто, или може да се разложи напроизведението на простите делители и по уникален начин (ако не обръщате внимание на реда на факторите).
Използвайки нотацията на степента, разлагането на числото 2009 на прости множители може да се запише по следния начин:
Факторизацията се наричаканонична, ако всички множители са прости и са записани във възходящ ред.
Например, нека напишем каноничното факторизиране на числото 150:
Взаимопрости числа и функцията на Ойлер
Две числа се наричат взаимно прости, ако нямат общ делител, различен от единица.
Например числата 11 и 12 са взаимно прости (нямат общ делител освен единица), числата 30 и 35 не са (имат общ делител 5).
Швейцарският математик Леонард Ойлер отдавна се занимава с изследване на модели, свързани с цели числа. Един от въпросите, който го интересуваше, беше следният: колко естествени числа не превишават n и са относително прости на n? Отговорът на този въпрос е получен от Ойлер през 1763 г. и този отговор е свързан с каноничното разлагане на числото n на прости множители. Така че, ако
където p1 , p2 , . pn са различни прости множители, тогава броят на естествените числа, непревишаващи n и относително прости спрямо n, може да бъде точно определен по формулата
Броят на естествените числа, които не превишават n и относително прости спрямо n, се наричафункция на Ойлери се обозначава
Например, нека намерим броя на естествените числа, които не надвишават 12 и са относително прости на 12. От поредица от естествени числа
взаимнопрости (без общи делители) с 12 ще бъдат само числата 1, 5, 7, 11. Техният брой е четири. По този начин
Сега нека се опитаме да изчислим
Сега нека изчислим функцията на Ойлер:
Стойностиизчислени чрез просто изброяване на взаимно прости числа и по формулата на Ойлер, съвпадат. Това не е изненадващо, тъй като формулата за изчисляване на функцията на Ойлер може да бъде доказана строго математически.
Формулата на Ойлер е удобна за използване при големи n, ако е известно разлагането на числото n на прости множители. За криптографията формулата на Ойлер е важна, защото улеснява получаването на числото
Следствие 1. Ако p е просто число, тогава
Наистина, ако p е просто число, тогава неговото канонично разлагане се състои само от себе си. Тогава
Следствие 2. Нека p и q са две различни прости числа ( ). Тогава
Тази формула се обяснява по следния начин. Нека р * q = N , където р и q са две различни прости числа ( ). Тогава
Нека разгледаме няколко примера за използване на следствията от формулата на Ойлер.
Пример 1. Нека намерим 13 - просто число, така че използвайки следствие 1, можем да проверим себе си (и Ойлер), като изпишем всички числа, по-малки от 13:
и броене на всички копрости с него. Всъщност има 12 от тях.
Пример 2. Да намерим 35 - съставно число, което означава, че първото следствие не ни устройва. Въпреки това, 35 е произведение на две прости числа: 35 = 5 * 7 . Използвайки следствие 2, изчисляваме:
Проверяваме като изписваме всички числа по-малки от 35 и без общи делители с него:
Те наистина бяха 24. Последният пример показва, че използването на формулата на Ойлер е много по-удобно от разглеждането на всички числа от доста голям диапазон и проверката за взаимна простота.