1610912777-ff63a1b83b9ac0b597c9346050946007 (824719), страница 7
Текст из файла (страница 7)
Ниже используются два свойства Фи-функции Эйлера. Если p простое число, тоϕ(p) = p − 1,(15.2.1)и, если числа n и m взаимно просты, тоϕ(m n) = ϕ(m)ϕ(m).(15.2.2)Итак, если абонент A желает получать от абонента B секретные сообщения, то он выбирает два больших простых числа p и q, берет ихпроизведение r = pq. Находит какое-нибудь число a взаимно простое счислом ϕ(r) и число α удовлетворяющее уравнениюaα ≡ 1(mod ϕ(r)).(15.2.3)Далее он отправляет по любому каналу связи абоненту B числа r и a.Абонент B своё секретное сообщение m < r возводит в степень a по модулю r, т.е. вычисляет число m1 = ma (mod r) и отправляет его абонентуГлава 15. Примеры64A.
Абонент A вычисляет число m2 = mα1 (mod r), которое в силу теоремыЭйлера равно m. Действительно, и силу (15.2.3) существует такое целоеположительное число k, что aα = kϕ(r) + 1, поэтомуm2 = maα (mod r) = mkϕ(r)+1 (mod r) = mϕ(r)km(mod r) = m.Функция power_mod(x, y, z) вычисляет xy (mod z). Алгоритм основанна двоичном представлении показателя степени y. Еслиy = y0 + 2y1 + 22 y2 + .
. . 2k yk ,где y0 , . . . , yk ∈ {0, 1}, тоx y = x y0 x 2 y1 k yk. . . x2.procedure power_mod(x, y, z);beginscalar u, v, w, d;u := x;v := 1;w := y;while w > 0 dobegind := remainder(w, 2);if d = 1 thenv := remainder(u*v, z);w := (w - d)/2;u := remainder(u*u, z);end;return v;end;Функция ort(y) возвращает число взаимно простое с аргументом y.procedure ort(y);beginscalar w;while 1 < 2 doГлава 15. Примеры65beginw := random(y);if gcd(w,y) = 1 thenbegingoto m1;end;end;m1:;return w;end;Функция f i(y) вычисляет Фи-функцию Эйлера аргумента y.
Алгоритм использует свойства (15.2.1) и (15.2.2) Фи-функции Эйлера.procedure fi(y)$beginscalar j, z;s := factorize(y);z := 1;for j:=1:length(s) doz := z*(part(s,j,1) - 1)^part(s,j,2);return z;end;Следующий фрагмент диалога с «Reduce» демонстрирует работоспособность описанного алгоритма. В данном примере r является 130-битовым числом. В стойкости шифрования против взлома можно убедитсяпопытавшись разложить r на простые множители, т.е. запустив команду factorize(r)1 .
Однако, в строке 7 вызывается функция f i, котораяуспешно разлагает на простые множители число еще бо́льшее, чем r.Дело здесь в том, что в разложении этого числа на простые множителисомножителей значительно больше двух и они значительно меньше 2130 .1:2:random_new_seed(300)$p := nextprime(2^65);p := 36893488147419103363q := nextprime(2^70);3:1Маловероятно, что читатель дождется окончания работы команды.
-:)Глава 15. Примеры66q := 11805916207174113034494: r := p*q;r := 435561429658801234788917892689326893989875: phi := (p-1)*(q-1);phi := 435561429658801234776743041600678589921766: a := ort(phi);a := 115570610974896038147173022465830642270157: x := fi(phi);x := 12098899069404431023195996380389161267208: alpha := power_mod(a, x - 1, phi);alpha := 421177072851213137195300282846994139808239: m := random(r-1) + 1;m := 2424588478576364301035322186271086163359410: m1 := power_mod(m, a, r);m1 := 770545496319102272916354110766080202751711: m2 := power_mod(m1, alpha, r);m2 := 2424588478576364301035322186271086163359412: m2 - m;015.3Построение численных алгоритмовВ данном разделе приводятся примеры использования системы «Reduce»для построения некоторых алгоритмов численных методов.15.3.1Формулы численного дифференцированияОдним из методов конструирования формул численного дифференцирования является метод неопределенных коэффициентов.
Требуетсянайти величины a1 , . . . , an (неопределенные коэффициенты), которые длялюбой достаточно гладкой в окрестности точки x ∈ R функции u : R →R удовлетворяют соотношениюa1 u(x − (j − 1)h) + · · · + aj u(x) + · · · + an u(x + (n − j)h) ≈dm u(x). (15.3.4)dxmДля решения уравнения (15.3.4) функции u из левой части уравненияразлагают относительно точки x ∈ R в ряд Тейлора до порядка n − 1,Глава 15.
Примеры67далее приравнивают коэффициенты при производныхdi u,dxii = 0, . . . , n − 1нулю, что дает линейную систему уравнений на коэффициенты a1 , . . . , an .Для вычисления остаточного члена надо производить разложение в рядТейлора до порядка n + 1.Функция numerical_diff (h, m, n, j) реализует этот алгоритм. В строках 4–6 создается список коэффициентов a1 , . . . , an . В строках 7–9 создается список переменных g0 , . . . , gn+1 , через которые обозначаются производные функции u. В строках 10–23 вычисляется разность w разложениялевой части уравнения (15.3.4) в ряд Тейлора до порядка n + 1 и правой части этого уравнения.
В строках 24–27 конструируется список изкоэффициентов при переменных g0 , . . . , gn−1 выражения w. Полученнаясистема решается относительно переменных a1 , . . . , an . В строках 28–33вычисляется остаточный член. Он может содержать два слагаемых сразличными степенями шага h. Для выделения главной составляющейсначала выделяется слагаемое со старшей степенью и вычитается (еслив этом есть необходимость) из предварительно вычисленного остаточного члена. Для правильной работы функции lterm необходимо сброситьфлаг mcd.Функция numerical_diff (h, m, n, j) возвращает список, первые n элементов которого содержат коэффициенты a1 , . .
. , an , а последний элемент равен остаточному члену.12345678910111213procedure numerical_diff(h,m,n,j);beginscalar s_out, s1, u, v, w, j1, j2, vars, f;vars := {};for j1 := 1:n dovars := append(vars, {mkid(a,j1)});f := {};for j1 := 0:(n + 1) dof := append(f, {mkid(g,j1)});x1 := -(j-1)*h;w := -part(f,m+1);for j1 := 1:n dobeginГлава 15. Примеры1415161718192021222324252627282930313233343568v := 1;u := part(f,1);for j2 := 1:(n + 1) dobeginv := v*x1/j2;u := u + part(f,j2 + 1)*v;end;w := w + part(vars,j1)*u;x1 := x1 + h;end;s1 := {};for j1 := 1:n dos1 := append(s1, {df(w,part(f,j1))});s1 := solve(s1,vars);w := sub(s1,w);off mcd;v := lterm(w,h);if w neq v thenw := w - v;on mcd;return append(sub(s1,vars),{w});end;Примеры использования функции numerical_diff :1: numerical_diff(h,1,3,1);{( - 3)/(2*h),2/h,( - 1)/(2*h),( - g3*h**2)/3}2: numerical_diff(h,2,5,1);{35/(12*h**2),( - 26)/(3*h**2),19/(2*h**2),( - 14)/(3*h**2),11/(12*h**2),(5*g5*h**3)/6}15.3.2Метод АдамсаФормулы метода Адамса решения задачи Коши для системы обыкновенных дифференциальных уравненийdy= f (t, y)dtГлава 15.
Примеры69имеют видy(t + τ ) = y(t) + τmXαmj f (t − jτ, y(t − jτ )),j=0где коэффициенты αmj определяются из формулαmjZ1 Ymξ−j=dξ.j−ij=0,j6=i(15.3.5)0Функция adams_coef (m, x) вычисляет коэффициенты (15.3.5) и возвращает их в виде списка. Параметр x в заголовке функции выглядитлишним и может возникнуть желание переместить его в описание локальных переменных. Однако «Reduce» отказывается производить интегрирование по локальной переменной. Можно ее вообще не описывать,но тогда, если до вызова функции переменной x было присвоено какоето конкретное значение, то функция не сработает. Поэтому надежнеевставить переменную x в список формальных параметров и при вызовефункции в качестве фактического параметра использовать свободнуюпеременную.procedure adams_coef(m,x);beginscalar s_out, j, j1, f, g;s_out := {};for j1 := 0:m dobeginf := for j := 0:(j1-1) product (x+j)/(j-j1);f := (for j := (j1+1):m product (x+j)/(j-j1))*f;g := int(f,x);s_out := append(s_out, {sub(x=1,g) - sub(x=0,g)});end;return s_out;end;Примеры использования функции adams_coef :1: adams_coef(3,x);{55/24,( - 59)/24,37/24,( - 3)/8}2: adams_coef(4,x);{1901/720,( - 1387)/360,109/30,( - 637)/360,251/720}Глава 15.
Примеры15.470Система обыкновенных дифференциальных уравнений с постоянными коэффициентамиОбщее решение системы обыкновенных дифференциальных уравненийdx= Ax + b, A ∈ L(Rn , Rn ), b ∈ Rn , x : R → Rndtимеет видx = eAt x̄ + c0 + c1 t + · · · + ck tk ,где k не превышает кратность нулевого собственного значения матрицыA, x̄ — произвольный постоянный вектор, а постоянные вектора c0 , c1 , . . .
, ckопределяются из системы уравнений:c1 = Ac0 + b,2c2 = Ac1 ,................kck = Ack−1 ,0 = Ack .Пусть A = P JP −1 , где J жорданова форма матрицы A, тогда предыдущая система может быть записана в виде.c̄1 = J c̄0 + b̄,2c̄2 = J c̄1 ,................kc̄k = J c̄k−1 ,0 = J c̄k .где c̄j = P −1 cj и b̄ = P −1 b. Пусть матрица J состоит из клеток Жордана J1 , . . . , Jm , собственные значения и размерности которых равны соответственно λ1 , .
. . , λm и d1 , . . . , dm . Предыдущая система распадаетсяна независимые системы для каждой клетки Жордана. Если λl 6= 0, тоc̄0l = −Jl−1 b̄ и c̄jl = 0 для j > 0. Если λl = 0, то c̄0l = 0 и c̄jl = Jlj b̄для j > 1. Здесь c̄jl — компоненты вектора c̄j соответствующие клеткеЖордана Jl .Процедура get_jcell(m) получает матрицу m в форме Жордана ивозвращает список клеток Жордана матрицы m: {{d1 , λ1 }, . .
. , }, где dj— размерность, а λj — собственное значение j-ой клетки Жордана.Глава 15. Примеры71Следующий пример матрицы включающий две клетки Жордана демонстрирует способ выделения клеток Жордана из матрицы состоящейиз нескольких клеток Жордана: если j-я строка является последнейстрокой матрицы или mjj+1 6= 1, то j-я строка — последняя строка клетки Жордана.λ1 1 0 0 0 λ1 0 0 m= 0 0 λ2 1 0 0 0 λ2Именно это условие и проверяется в 10-ой строке процедуры.В 5-ой строке вводится новая матричная переменная mat2 и ей присваивается матрица m — это может показаться излишним, тем более,что элементы матрицы mat2 в процедуре изменяться не будут. Но, какотмечалось в разделе 12, обратиться к элементам матрицы m «Reduce»не позволяет, а к элементам матрицы mat2 уже можно. При этом надоиметь ввиду, что всякий раз при вызове процедуры 5-я строка порождает(или переопределяет) глобальную переменную mat2.1234567891011121314151617181920procedure get_jcell(m);beginscalar s_out, s1, n, j, j1;s_out := {};mat2 := m;n := part(length(mat2),1);j1 := 0;for j := 1:n dobeginif j = n or mat2(j,j+1) neq 1 thenbegins1 := {j1+1,mat2(j,j)};s_out := append(s_out, {s1});j1 := 0;endelsej1 := j1 + 1;end;clear mat2;return s_out;Глава 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
