13 C
София

Древните военни измами са все още живи в съвременната математика

Оригиналът е на Lakshmi Chandrasekaran

Най-четени

Даниел Десподовhttps://www.kaldata.com/
Ежедневен автор на новини. Увличам се от съвременни технологии, оръжие, информационна безопасност, спорт, наука и концепцията Internet of Things.

В една стара легенда се казва, че китайските военни са използвали математическа хитрост, за да скрият числеността на войските си. Съвсем същият метод се използва в много области на съвременните математически изследвания, в астрономията, в съвременната криптография и още много други.

Представете си, че сте военноначалник в древен Китай и искате да скриете числеността на своята армия от противника. Но същевременно трябва да знаете точния брой на вашите войници. За да се разбере абсолютно точно числеността на армията и да не се даде на противника възможност да получи тази информация, може да се използва интересна математическа хитрост.

Всяка сутрин вашите войници се построяват в многобройни редици по пет души и виждате че в последната редица има трима войници. След това вие ги карате да се престроят в редици по осем души, след което накрая остават седем души. И накрая те се подреждат в редици по девет души, след което в последната редица има само два войника. Без нито веднъж да преброите всички войници тази информация ви е достатъчна, за да определите точната численост на своята армия. При този подход нито веднъж не се назовава точния брой на вашите войници – нещо, което врагът би могъл да научи.

Според тази легенда, пълководците на древен Китай нееднократно са прибягвали до тази хитрост и математическа и измама. Не се казва защо са правили това и няма доказателства дали наистина са го правили. Все пак това е само една легенда. Но за сметка на това тази математическа техника не се е изгубила през вековете и към днешен ден е известна като „Китайската теорема за остатъците„. Тя се появява някъде между третия и петия век от нашата ера и е предложена от математика Сун Дзъ (не е този Сун Дзъ, който е написал „Изкуството на войната“ 1000 години преди това).

 

Тази теорема дава възможност да се определи едно цяло число по няколкото негови остатъци от делението на числа, взети от набор взаимно прости числа. Сун Дзъ не е успял да докаже тази теорема, като това е направил индийският математик и астроном Ариабхата, който измислил начин за решаване на произволен конкретен случай на тази теорема.

Китайската теорема за остатъците ни дава един отличен способ за определяне на дадено цяло число.

За да може по-добре да разберем тази теорема, нека да се върнем към нашия пример. Нашата цел е да открием цялото число Х, което има остатък 3 при деление на 5 и остатък 7 при деление на 8. По-късно ще добавим третото условие, а именно, че това число при деление на 9 дава остатък 2. Математиците наричат това алгебраична конгруенция, а нашата система изглежда по следния начин:

X ≡ 3(mod 5)
X ≡ 7(mod 8)

Решението на първата конгруенция е равно на 3, понеже три по модул 5 е равно на 3. Ако към тройката добавим петица, то тази сума също ще удовлетворява първата конгруенция. Следователно Х може да е всяко число от поредицата 3, 8, 13, 18, 23 и т.н.

 

Наличието на втората конгруенция дава възможност да се уточни решението и намирането на числото X. Числата, които удовлетворяват тази конгруенция и дават остатък 7 при деление на 8 са поредицата 7, 15, 23, 31 и т.н. Сега остава да намерим числото, което го има и в двете поредици:

3, 8, 13, 18, 23, 28, 33
7, 15, 23, 31, 39, 47, 55
Веднага можем да видим, че нашето загадъчно число е 23. Но това далеч не е единственото решение.

Винаги можем да намерим друго число, като вземем произведенията на нашите делители и добавим кратните на него числа към 23. В случая нашите делители са 5 и 8, като тяхното произведение е 40. Ако добавим 40 към 23 ще получим числото 63, които също удовлетворява условията и на двете конгруенции. По този начин можем да съставим следната поредица от числа, която удовлетворява и двете условия – 103, 143, 183, 223 и т.н. По този начин може да бъде намерено решение на всеки 40 числа, като подставяме различни цели числа за К в следната формула:

X=23+40×K

Но най-малкото цяло число, което удовлетворява и двете конгруенции е 23.

Ако сте генерал и знаете, че имате някъде около 300 войници, числата 23, 63 и 103 няма да ви удовлетворяват с точността си. Тогава ще трябва да се добави трето условия към първите две:

X ≡ 3(mod 5)
X ≡ 7(mod 8)
X ≡ 2(mod 9)

Кое число би удовлетворило и трите конгруенции? Нека се върнем към предишната поредица от числа: 23, 63, 103, 143, 183, 223. Нито едно от тях не дава остатък 2 при деление на 9. Но следващото число в тази поредица е 263, което удовлетворява всички условия. Разбира се, ако искаме още по-голяма точност при по-големи числа, можем да добавим четвърта конгруенция и не само четвърта, а колкото пожелаем.

 

Досега ние използвахме делители, които са взаимно прости (две последователни естествени числа). Но какво би станало, ако няма как да изберем делителите? Нека да предположим, че сме астрономи, изследващи две комети с орбитални периоди съответно 4 и 10 години. Последния път те едновременно са стигнали своя перихелий – точката, в която кометата е най-близо до Слънцето, през 1991 и 1997 години. Как можем да пресметнем, кога ще е следващия път когато тези две комети отново ще достигнат своите перихелии в една и съща година?

Китайската теорема за остатъците може да ни помогне и тук. Когато делителите не са взаимно прости числа, вместо да използваме кратните на техните произведения за определяне на възможните решения, ние ще използваме кратните на тяхното най-малко общо кратно. Ето защо в този случай вместо да умножаваме 4 на 10, ще вземем най-малкото общо кратно на тези две числа – 20.

Нека сега се опитаме да изчислим загадъчната година X, която удовлетворява следните конгруентности:

X ≡ 1991(mod 4)
X ≡ 1997(mod 10)

Ако следваме същия процес, който използвахме при предишните примери, то в този случай ще трябва да добавяме кратните на 20 числа към най-малкото цяло число, което удовлетворява и двете конгруентности (това всъщност е 7), то ще изчислим общата година, в която двете комети ще достигнат своите перихелии. Това е 2007 година.

 

Този пример демонстрира колко е широко приложението на китайска теорема, което я прави много полезна в практиката. Тя е използвана в астрономията за пресмятането на древните календари и при избора на тухли с правилен размер за изграждането на здания. Счита се, че тази теорема е използвана при строителството на Великата китайска стена. След повече от 1500 години китайската теорема за остатъците си остава един от най-полезните начини за решаване на съвременните проблеми, включително RSA криптирането, което е в основата на съвременните протоколи за информационна безопасност. Операциите на RSA, независимо дали кодирането, декодирането, подписването или проверката, всъщност представляват модулно експоненциране. Изчисленията се извършват като серия модулни операции. RSA алгоритъмът се използва в на практика всички операционни системи, включително на Microsoft, Apple, Sun, Novell и в Linux дистрибуциите. Алгоритъмът RSA може да бъде открит в смартфоните, в мрежовите карти и още много други. Като цяло, RSA е внедрен като мярка за сигурност във всички главни протоколи за сигурни интернет-комуникации.

Всъщност китайската теорема за остатъците не е само един обикновен тясно специализиран математически инструмент. Тя е в основата на почти всички математически операции в един от основните клонове на теорията на числата, който се нарича модулна аритметика и предлага начини за извършване на математически изчисления с помощта на по-малки числа, точно както в примерите по-горе, в които пресмятахме броя на войниците и годините на перихелиите на кометите.

Абонирай се
Извести ме за
guest
0 Коментара
Отзиви
Всички коментари

Нови ревюта

Подобни новини