§ 9 Упражнения

Для решения приведенных ниже упражнений удобно будет воспользоваться каким-либо пакетом аналитических вычислений. Приведем сводку полезных стандартных функций из пакета MAPLE V Release 5. Часть из них подгружается к основным вызовом из with(numtheory);:

igcd и ilcm - НОД и НОК;

igcdex - расширенный вариант igcd с возможностью нахождения линейного представления НОД;

ifactor - каноническое разложение числа;

isprime - проверка числа на простоту;

phi - функция Эйлера;

msolve - решение уравнений по фиксированному модулю;

order - вычисление порядка числа по фиксированному модулю;

index или mlog - вычисление индекса числа по основанию другого числа по фиксированному модулю.

length - число цифр в представлении числа;

nextprime (prevprime) - нахождение простого числа ближайшего заданному сверху (снизу);

chrem - китайская теорема об остатках;

floor - целая часть числа;

isqrt - вычисление целой части от квадратного корня из числа;

issqr - проверка, является ли число полным квадратом (подгружается вызовом readlib(issqr);).

Приведем примерный листинг действий пользователя (вводимые им команды начинаются после знака > ) и реакции на них программы:

[ > with(numtheory):

Warning, new definition for order

[ > A:=1492736; B:=4653778; C:=278368;


A
:=
1492736
B
:=
4653778
C
:=
278368
[ > ifactor(A);
(2)8 (7)3 (17)
[ > igcd(A,B,C);
2
[ > ilcm(A,B,C);
30215376080266496
[ > convert(A, binary);
101101100011100000000
[ > nextprime(1000);
1009
[ > isprime(43297863);
false
[ > isprime(43297847);
true
[ > phi(A);
602112
[ > A^mod  3736778;

Error, object too large

[ > A&^mod  3736778;


1928192
[ > msolve(A*x=1,87236);

[ > msolve(A*x=1,87233);


{x=2704}

Полное описание любой выполняемой операции (на английском языке) можно получить, записав ее имя после вопросительного знака, например: [ > ?fermat

Прокомментируем четыре строчки из приведенного выше листинга. Тест числа на простоту isprime является вероятностным. Отрицательный результат false следует считать абсолютно истинным: проверяемое число, действительно, не является простым. Однако же результат true следует понимать в том смысле, что проверяемое число скорее всего является простым, так как серия испытаний, аналогичных тем, что указаны во втором вероятностном алгоритме страницы 91, не установила противное.

Далее программа отказалась вычислить выражение AB mod M при его представлении в виде 1492736^4653778   mod  3736778, сообщив, что оно слишком велико. В самом деле, число 14927364653778 выходит за пределы чисел, представимых в данной версии MAPLE (524 280 цифр). Однако следующий вариант представления 1492736&^4653778   mod  3736778 практически мгновенно приводит к ответу. В чем тут дело? Последовательность &^ сигнализирует программе о том, что операция возведения в степень будет производится по модулю некоторого числа. Программа реагирует на этот сигнал запуском алгоритма ``квадрирования-умножения'' (см. с. 32).

      Упражнение 9.1 .  Взломав открытый ключ шифрования, прочитайте сообщения (открытый текст закодирован стандартной кодировкой).

В шифровках 1-8 длина блоков равна 10.

  1. M=3273550829, E=1925928379,
    1169117912 1244629799 2168855069 1243855092 0437023454 2762017513 0127848283
    0047229456 2567946795 2860789969 3245731988 0034676752 1557331563 1308187811
  2. M=3337224043, E=2344644737,
    3211612606 1208442100 2529758308 2762054337 1406507518 1251992427                     
    2442112810 0547056391 0568275910 3137778049 2989017937 2820696238 2486694925
  3. M=3571723717, E=1054875165,
    3371389761 3108772900 2789090756 1702524865 1459737350 3094823069 2426005999
    3088333655 1346615411 2119806179 1572525825 1397236295 0490884957 1694795075
  4. M=3414621671, E=627535223,
    2728903315 1427672020 2710570826 1168363236 2353416748 0459131576                     
    0634259134 3132407495 1814809280 2656246726 1473949532 1041251468 2047712588
  5. M=3601800221, E=300140017,
    0100111701 2753015690 2201516922 3363274335 1518851909 1806120100                     
    3573090214 0306190003 0954217522 3363101814 1887404463 1106001617 2744326638
  6. M=8590000127, E=3681419263,
    5289389833 0322445978 4488463867 6745107937 3431374889 8532179333
    3411484703 1285890029 2951679964 2820703034 0838735447 1679852513
  7. M=3337460873, E=825541727,
    0006181209 0504711138 2946944228 0603228516 1338276606 2622465339
    1543961568 2435259794 3186948955 1203023424 2066199011 2413376881
    2948791304 2834914982 1142922701                                                               
  8. M=5694996163, E=2676573121,
    1163219079 4668046830 0011216732 0309650467 3267065033 1192514275
    1212489158 5058346454 4345793196 4397102669 5368937727 0949088697
    5120945088 1192514275 1921390549 0896888534 2535878443 4397102669
    В шифровках 9 и 10 длина блоков равна 12.
  9. M=304061960677, E=1251437711,
    009845336878 131918325363 200330796769 176207234138 201318313310 148890103474
    014807085093 255259487321 059593707307 054728561148 190490857163 071144700575
    194450312531 278133682149 249837161637                                                                           
  10. M=357106915621, E=182979752741,
    325172590473 343958407857 181997910876 256274850311 012909887764
    В шифровках 11 и 12 длина блоков равна 38.
  11. M= 17428130119190358656862844953928880399, E= 7641232191248410654157,
    04945624150857327747472113001948209425
  12. M=77512957676264314053480251723654409833,  E=65537.
    05466596792819218212234305511305291063 20198134849315351291256415950980246911
    60568601691487730459566983298202883187
    В шифровке 13 длина блоков равна 48.
  13. M=323304894015216546587068731061060010043806210137 ,

    E = 182564475735968835170568313036845173155699825601


    298518555120973843005896884803656930744052264560
    214140117353937599348267918644229308388594182193

      Упражнение 9.2 .  Почему выбор ключа в сообщении 9 следует считать неаккуратным?

Намек. Попробуйте зашифровать этим ключом слово ЯСТРЕБ, а потом дешифровать полученное.

      Упражнение 9.3 .  Число c=09082013172005 представляет в стандартной кодировке слово `` ИЗУМРУД''. А каково старинное название этого минерала? Для ответа на этот вопрос достаточно знать, что результат шифрования этого названия открытым ключом M=33797052734279, E=87937893079 как раз и совпадает с c.