Пояснительная записка к курсовой работе
по дискретной математике.
Мультипликативно обратные элементы в поле вычетов.
СОДЕРЖАНИЕ
ПРОВЕДЕНИЕ АНАЛИЗА СВОЙСТВ, ХАРАКТЕРИЗУЮЩИХ ЗАДАННУЮ ТЕМУ.. 3
ПОСТРОЕНИЕ ПРОГРАММНОЙ МОДЕЛИ.. 5
Построение алгоритма программы.. 6
Составление программы на BORLANDC++3.1. 8
ВЫВОДЫ ПО ВСЕЙ КУРСОВОЙ РАБОТЕ.. 9
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ… 10
ПРОВЕДЕНИЕ АНАЛИЗА СВОЙСТВ, ХАРАКТЕРИЗУЮЩИХ ЗАДАННУЮ ТЕМУ
Полем называется множество с двумя определёнными операциями — сложением и умножением, причем имеют место следующие аксиомы:
- Множество образует абелеву группу по сложению;
- Поле замкнуто относительно умножения, и множество ненулевых элементов образует абелеву группу по умножению;
- Закон дистрибутивности:
Единичный элемент относительно сложения принято обозначать через 0 и называть нулём, аддитивный обратный элементу a элемент — через — a; единичный элемент относительно умножения обозначать 1 и называть единицей, мультипликативный обратный к элементу a элемент — через a-1.
Поле с конечным числом элементов называют полями Галуа GF(q).
Вычеты по mod(m) определяют разбиение множества целых чисел на m классов эквивалентности: {C0, C1, C2, …, Cm-1}, где Ci={i, i+m, i+2m, …}. Например, для неотрицательных целых чисел по mod(4) имеется четыре класса —
C0={0, 4, 8, 12, …} C2={2, 6, 10, 14, …}
C1={1, 5, 9, 13, …} C3={3, 7, 11, 15, …}
Для представителей можно ввести операции сложения и умножения по mod(4):
0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | |||
0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | |
1 | 1 | 0 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | |
2 | 2 | 3 | 0 | 1 | 2 | 0 | 2 | 3 | 1 | |
3 | 3 | 2 | 1 | 0 | 3 | 0 | 3 | 1 | 2 |
Для многочлена, как и для чисел, можно ввести сравнение многочлена a(x) по модулю многочлена q(x): a(x)=r(x) mod q(x). Следовательно, можно говорить и о поле многочленов GF(q) над числовым полем GF(p). Если GF(2) и q(x)=x3+1, то имеем поле многочленов GF(x3+1), состоящее из восьми многочленов: {0, 1, x, x+1, x2, x2+1, x2+x, x2+x+1}. Здесь p называется характеристикой поля GF(p); характеристика определяет размерность или порядок полей многочлена: q=pn=23=8, где n — степень многочлена q(x). Перемножая и складывая многочлены по данному модулю можно составить таблицу умножения и сложения. для GF(x2+x+1), размерность которого в два раза меньше описанного выше поля {0, 1, x, x+1} таблицы умножения и сложения представлены выше (если каждому элементу последнего множества сопоставить в соответствие число {0, 1, 2, 3}).
Наибольший общий делитель двух заданных положительных чисел s и t может быть вычислен с помощью итеративного применения алгоритма деления. Эта процедура известна как алгоритм Евклида. Предположим, что t<s; алгоритм Евклида сводится к последовательности шагов:
s=Q(1)t+t(1)
t=Q(2)t(1)+t(2)
t(1)=Q(3) t(2)+t(3)
……….
t(n-2)=Q(n)t(n-1)+t(n)
t(n-1)=Q(n+1)t(n)
где остановка процесса наступает при получении нулевого остатка. Последний ненулевой остаток t(n) равен наибольшему общему делителю. Этот факт будет доказан в следующей теореме. Матричные обозначения позволяют кратко записать шаги алгоритма Евклида в виде:
Теорема. (Алгоритм Евклида).[2][3] Для двух заданных положительных чисел s и t, где s>t, пусть s(0)=s и t(0)=t. Решение рекуррентных уравнений:
при r=1, …, n даётся величиной
где n равно наименьшему целому числу, для которого t(n)=0.
Доказательство:
Так как t(r+1)<t(r) и все остатки неотрицательны, то в конце концов наступит n, для которого t(n)=0, так что завершение работы алгоритма произойдёт обязательно, легко проверить, что
Поэтому
так что s(n) должно делить оба числа s и t и, следовательно, делит НОД[s, t]. Далее
так что любой делитель чисел s и t делит s(n). Следовательно, НОД[s, t] делит s(n) и делится на s(n). Таким образом
s(n)=НОД[s, t]
Это завершает доказательство.
Из этой теоремы вытекает несколько важных следствий. Пусть
Тогда получаем следствие:
Для любых чисел s и t найдутся такие целые числа a и b, что
НОД[s, t]=as+bt
Доказательство
Достаточно доказать следствие для положительных s и t. Так как
и s(n)=НОД[s, t], то утверждение выполняется при и
.
Следствие 2:
Получаемые в процессе алгоритма Евклида матричные элементы и
удовлетворяют равенствам:
Доказательство
Используя выписанные выше выражения для обратной матрицы и обращая первое равенство из доказательства прошлого следствия получаем
Утверждение вытекает отсюда непосредственно.
Теорема. (малая теорема Ферма).[1] Если m – простое число и a – произвольное целое число, не делящееся на m, то am-1=1 (mod m).
Доказательство.
a*am-2=am-1=1 (mod m).
Следствие. Если m – простое число, то в кольце Zm выполняется равенство a-1=am-2.
Пример: если a=2, m=5, то 2-1=25-2(mod 5)=8(mod 5)=3(mod 5). Тогда 2-1=3.
Нахождение обратных элементов с использованием алгоритма Евклида[1]
Так как у поля модуль m – простое число, то для нахождения обратного элемента для элемента x можно найти уравнение ax+my=1. Тогда слагаемое my равно нулю (вычисления производятся по модулю m). Следовательно, элемент a является обратным к элементу x.
Нахождения обратных чисел можно реализовать с помощью малой теоремы Ферма.
В соответствии с малой теоремой Ферма a-1=am-2.
ВЫВОДЫ
В соответствии с вышеописанными теоремами программа должна находить обратный элемент используя малую теорему Ферма или алгоритм Евклида. Программа должна работать для достаточно широкого спектра значений модуля, по которому производятся вычисления и элемента для которого вычисляется обратный элемент. То есть программа не должна вычислять обратный элемент, например, только для чисел, которые меньше 3 или 5 (для этих чисел обратный элемент в поле вычетов по такому маленькому модулю можно вычислить и без компьютера). То есть программа должна быть предназначена для вычисления обратного элемента для достаточно большого (в разумных пределах) числа. Также программа должна проверять корректность входных данных. То есть, в случае, если НОД введённого модуля и элемента должно равняться единице, в противном случае программа должна сообщать, о том, что данный элемент не имеет обратного.
ПОСТРОЕНИЕ ПРОГРАММНОЙ МОДЕЛИ
Напишем программу нахождения обратного числа для данного элемента в данном поле.
Поле возьмём по модулю простого числа.
Выбор метода
По началу кажется, что нахождение обратных элементов в поле проще всего реализовать с помощью малой теоремы Ферма. Но на практике из-за ограниченности разрядной сетки машины этот алгоритм использовать достаточно затруднительно. Например, для вычисления обратного элемента для 9 в поле по модулю 23:
921=109418989131512359209.
Можно приводить числа по данному модулю после каждого умножения, что решит эту проблему для не очень больших чисел. Но для достаточно больших чисел эта проблема останется.
Причём значение имеет даже последняя девятка. хранения такого большого числа в компьютере и выполнения с ним операций вызывает определённые трудности. Следовательно, лучше реализовать алгоритм Евклида, работающий со стандартными типами данных, хотя для некоторых случаев (при небольших числах) алгоритм, построенный на следствии малой теоремы Ферма будет подходить больше.
Построение алгоритма программы
Напишем программу, реализующую нахождение обратного элемента с использованием алгоритма Евклида. По алгоритму Евклида (учитывая, что НОД[a, m]=1) выполняются следующие соотношения:
s=Q(1)t+t(1)
t=Q(2)t(1)+t(2)
t(1)=Q(3) t(2)+t(3)
……….
t(n-3)=Q(n-1)t(n-2)+t(n-1)
t(n-2)=Q(n)t(n-1)+t(n)
t(n-1)=Q(n+1)t(n)+1
Для нахождения уравнения ax+my=1 выразим с помощью предпоследнего уравнения число 1 через t(n-1)и t(n-2):
1= t(n-1) -Q(n+1)t(n)
1= t(n-1)— Q(n+1)* (t(n-2)- Q(n)t(n-1))
1= (1+Q(n+1) *Q(n))*t(n-1)— Q(n+1) *t(n-2)
1= — Q(n+1) *t(n-2)+ (1+Q(n+1) *Q(n))*t(n-1)
Как отсюда видно множитель — Q(n+1) «перешёл» из правого слагаемого (из слагаемого с большим) в левое слагаемое (с меньшим индексом). Проверим дальше. Теперь выразим 1 через t(n-2) и t(n-3):
1= — Q(n+1) *t(n-2)+ (1+Q(n+1) *Q(n))*t(n-1)
1= — Q(n+1) *t(n-2)+ (1+Q(n+1) *Q(n))*( t(n-3)— Q(n-1)t(n-2))
1= (1+Q(n+1) *Q(n))*t(n-3)+ ((1+Q(n+1) *Q(n))*( — Q(n-1)) — Q(n+1))t(n-2) (1)
Как видно снова множитель из правого слагаемого перешёл в левое слагаемое. Правое слагаемое составилось из прошлого множителя правого слагаемого, умноженного на следующее частное, и прошлого левого слагаемого. То есть, если на данном шаге перед слагаемым t с меньшим индексом стоит множитель a, а перед другим слагаемым – b, то для следующего шага перед слагаемым с меньшим индексом будет стоять b, а перед другим слагаемым b*a-a.
На основании полученной закономерности составим алгоритм нахождения НОД по алгоритму Евклида. Для хранения Q(i)проще всего использовать стек, так как в данном случае на каждом шаге будет необходим Q(i), который был сохранён последним.
Графическая схема алгоритма, осуществляющего нахождение НОД с помощью алгоритма Евклида:
Этот алгоритм при использовании для нахождения обратных элементов в качестве числа t должен получать модуль в котором производить вычисления, а в качестве числа s элемент, для которого необходимо найти обратный элемент. Тогда в выходной переменной s2 будет получаться обратный элемент для числа s. Естественно при получении входных данных модуль t должен быть таким, что полученная структура была бы полем. То есть число t должно быть простым. (когда t – простое, то НОД[t, s]=1 и в полученном выражении слагаемое с t сокращается).
Составление программы на BORLANDC++3.1
Для хранения модуля и введённого числа подходит тип long (для того, чтобы программа могла работать с более длинными числами).
Для реализации стека был составлен специальный модуль, в котором были реализованы стандартные процедуры работы со стеком (PUSH (добавление элемента в стек), POP (извлечение элемента из стека), EMPTY (проверка стека на пустоту)).
С использованием стека была разработана процедура, вычисляющая с помощью алгоритма Евклида НОД двух чисел и возвращающая также полученное уравнение.
Для реализации интерфейса, понятного пользователю в данном случае не обязательно использовать графический режим, так как программа не работает с графическими объектами. Для работы с текстовым экраном был выбран стандартный модуль <CONIO.H>, поскольку в нём содержатся все необходимые процедуры: для вывода текстовой информации на экран, изменения цвета, для создания текстового окна и считывания информации, вводимой пользователем
ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ
Для проверки работоспособности программы достаточно вычисленный обратный элемент умножить на данный элемент и взять остаток от деления полученного числа на модуль, по которому производились вычисления. Если получится единица, то обратный элемент вычислен верно. Для сравнения были произведены вычисления с использованием малой теоремы Ферма и калькулятора.
a
(элемент, для которого находится обратный эдемент) |
m
(модуль, по которому производятся вычисления) |
am-2 | a(m-2) (mod(m))
(найденный вручную обратный элемент) |
Значение обратного элемента, вычисленное с помощью разработанной программы | a*a-1 (mod m)
|
9 | 23 | 109418989131512359209 | 18 | 18 | 1 |
2 | 5 | 8 | 3 | 3 | 1 |
56 | 101 | 1,176561609770433870981098575571e+173 | 92 | 92 | 1 |
999 | 1001 | 3,6806348825922326789470084006052e+2996 | 720 | 500 | для вычисленного вручную:
562 для вычисленного с помощью программы: 1 |
1111 | 30001 | не удалось вычислить | не удалось вычислить | 22494 | 1 |
77777 | 100001 | не удалось вычислить | не удалось вычислить | 35714 | 1 |
4555 | 7653765 | не удалось вычислить | не удалось вычислить | не существует обратного элемента | — |
344533 | 10000001 | не удалось вычислить | не удалось вычислить | 1644429 | 1 |
44256323 | 843553333 | не удалось вычислить | не удалось вычислить | 759177439 | 1
|
Как видно в таблице весь последний столбец занят единицами, кроме той строки, для которой не существует обратного элемента. Следовательно, программа работает верно.
ВЫВОДЫ ПО ВСЕЙ КУРСОВОЙ РАБОТЕ
Анализируя составленную программу можно сделать вывод, что с помощью алгоритма Евклида можно достаточно быстро найти обратный к данному элемент по данному модулю. При тестировании программы работала с числами около одного или двух миллиардов практически мгновенно. Никакого замедления не было замечено.
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
- Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики: Учебник. — М.: ИНФРА-М; Новосибирск: НГТУ, 2003. — 280 с. — (Серия «Высшее образование»).
- Блейхут, Ричард Э. Быстрые алгоритмы цифровой обработки сигналов Р. Блейхут; Пер. с англ. И.И. Грушко
- Теория и практика кодов, контролирующих ошибки Р. Блейхут; Пер. с англ. И. И. Грушко, В. М. Блиновского; Под ред. К. Ш. Зигангиров
ПРИЛОЖЕНИЕ
Листинг программы:
Модуль «STEK.CPP»:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
//В этом модуле описаны процедуры работы со стеками //константы для реализации процедур const true=1; const false=0; //Эта структура описывает 1 ячейку стека struct TStek{ long info; TStek * last; }; //создаём указатель NULL TStek Zero; TStek * NULLS=&Zero; //////////////////////////////////////////////////////////////////////////// //Функция Push служит для занесения значения переменной в стек //Если нет места лдя занесения переменной в стек, то функция возвращает //0(false), иначе 1(true) int Push(TStek *f,long x) { TStek *lf; if (!(lf=new TStek)) return false; (*lf).last=(*f).last; (*lf).info=(*f).info; (*f).info=x; (*f).last=lf; return true; } //////////////////////////////////////////////////////////////////////////// //Функция служит для извлечения переменной из стека //Функция возвращает значение переменной, находившейся в вершине стека long Pop(TStek * f) { TStek *lf; long x=(*f).info; lf=(*f).last; (*f).info=(*lf).info; (*f).last=(*lf).last; delete(lf); return x; } //////////////////////////////////////////////////////////////////////////// //Функция служит для проверки стека на пустоту //Возвращаемые значения: //Если стек пуст, то функция возвращает 1(true), иначе 0(false) int Empty(TStek *f) { if ((*f).last==NULLS) return true; else return false; } //////////////////////////////////////////////////////////////////////////// //Функция инициалтзирует Стек TStek * InitStek(TStek* f) { f=new TStek; (*f).last=NULLS; return f; } void DeleteStek(TStek *f) { delete(f); } |
Распечатка главной программы «REVKLID3.CPP»:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 |
#include <conio.h> #include <ALLOC.H> #include "STEK.CPP" //#include "MOUSE.CPP" #define version 2.1 #define _RELEASE ///////////////////////////////////////////////////////////////////////////// //Прототипы всех функций long RAlgEvklid(long t,long s,long * s1,long * s2); void PrintHelp(); void VerifyT(long t); void all(long s, long t); ///////////////////////////////////////////////////////////////////////////// char cmod[5]="mod "; char cexit[5]="exit"; char call[5]="all "; int cm=0,cm2=0; void main(void) { directvideo=1; _setcursortype(_SOLIDCURSOR); textbackground(BLACK); clrscr(); textmode(C80); unsigned char MaxX=80,MaxY=25; int n=25,m=1; window(2,2,MaxX/3-2*m,MaxY-m); textbackground(BLUE); textcolor(WHITE); clrscr(); PrintHelp(); window(MaxX/3,2,MaxX-2,MaxY-m); clrscr(); long s,t; cprintf("\r\nПрограмма вычисляет обратный элемент в поле вычетов. "); cprintf("\r\nПо какому модулю производить вычисления: \r\n"); cscanf("%li",&t); VerifyT(t); while (cm!=-4) { cm=0; textcolor(WHITE); cprintf("\r\n\r\nВведите число, для которого хотите вычислить обратный элемент:\r\n"); char command[128]=""; s=-1; textcolor(GREEN); cscanf("%li",&s); if (s==-1) { cscanf("%s",&command); textcolor(YELLOW); for (n=0; n<=3;n++) { if (command[n]==cmod[n]) cm++; if (command[n]==cexit[n]) cm--; if (command[n]==call[n]) cm2++; } #ifdef _DEBUG cprintf("\r\ncm=%li, cm2=%li\r\n",cm,cm2); #endif if (cm==3) { cscanf("%li",&t); VerifyT(t); } if (cm2==3) { all(s,t); cm2=0; } continue; } textcolor(WHITE); if (s>=t)//Приведение данного числа под данный модуль { cprintf("\r\n%li(mod %li)=",s,t); s=s % t; cprintf("%li",s); } if (s>0) { long s1,s2; long NOD; NOD=RAlgEvklid(s,t,&s1,&s2); cprintf("\r\nНОД[%li,%li]=%li*%li+%li*%li=%li",s,t,s1,s,t,s2,NOD); if (s1<0) s1=s1+t; #ifdef _RELEASE double vr=NOD; vr=(s*s1)%t; cprintf("\r\nПроверка результата: %li*%li=%li (mod %li)",s,s1,long(vr),t); #endif if (NOD==1) cprintf("\r\nОбратный элемент к числу %li это %li.",s,s1); else { textcolor(RED); cprintf("\r\nОшибка! НОД не равно единице."); textcolor(WHITE); } } else { textcolor(RED); cprintf("\r\nОшибка! Введите число больше 0.",t); textcolor(WHITE); } } } ///////////////////////////////////////////////////////////////////////////// //Функция вычисляет НОД с при помощи расширенного алгоритма Евклида long RAlgEvklid(long t,long s,long * s1,long * s2) { TStek * Mods=InitStek(Mods);//Объявление и инициализация стека для хранения остатков (вычетов) TStek * Q=InitStek(Q);//Объявление и инициализация стека для хранения результатов int Change=false; //int FillValue=sizeof(TStek); if (t>s)//Число s должно быть больше числа t { long buffer=t; t=s; s=buffer; Change=true; } long result=t; long t2=s; long t1=result; #ifdef _DEBUG long bbbb; #endif while (t1!=0) //Реализация алгоритма Евклида { result=t1; t1=t2 % result; #ifdef _DEBUG // bbbb=t2/result; // Push(Mods,t1);//Запись остатка от деления в стек, для последующего вычисления уравнения // cprintf("t1=%i, t2=%i, result=%i, t2/result=%i",t1,t2,result,bbbb); #endif if (!Push(Q,long(t2/result)))//Запись результата деления в стек, для последующего вычисления уравнения cprintf("\r\n\r\nНехватка памяти.\r\n\r\n"); #ifdef _DEBUG cprintf("s/t=%li, s=%li, t=%li, t2/result=%li\r\n",s/t,s,t,long(t2/result)); #endif t2=result; } int count=0; long b=1;// if (Empty(Q)) cprintf("\r\nСтек пуст\r\n"); else cprintf("Стек не пуст"); // if (!Empty(Q)) {b=Pop(Q); count++;cprintf("\r\n%i",b);}; if (!Empty(Q)) {b=-Pop(Q); count++;cprintf("\r\n%i",b);} long buffer;long bbb=1;long a=1; // cprintf("b=%li, bbb=%li, a=%li\r\n",b,bbb,a); while (!Empty(Q))//Вычисление уравнения (чисел s1 и s2) { buffer=b; bbb=Pop(Q); count++; b=a-(b*bbb); a=buffer; #ifdef _DEBUG cprintf("b=%li, bbb=%li, a=%li\r\n",b,bbb,a); #endif } #ifdef _DEBUG cprintf("\r\nКоличество элементов в стеке=%i\r\n", count); #endif if (Change) { buffer=b; b=a; a=buffer; } //cprintf("a=%li, b=%li\r\n",a,b); (*s1)=b; (*s2=a); // if () // { // buffer=a; // a=b; b=buffer; // } DeleteStek(Mods); DeleteStek(Q); return result; } ///////////////////////////////////////////////////////////////////////////// //Функция выводит помощь на экран void PrintHelp() { //cprintf("************************"); cprintf("Программа вычиляет\r\n"); cprintf("число, обратное к дан-\r\n"); cprintf("ному по данному модулю.\r\n"); cprintf("При запуске программа \r\n"); cprintf("запрашивает модуль, по\r\n"); cprintf("которому будут произ-\r\n"); cprintf("водиться вычисления\r\n\r\n"); cprintf("Вы в любой момент мо-\r\n"); cprintf("жете изменить модуль \r\n"); cprintf("введя команду:\r\n"); textcolor(RED); cprintf("mod <новый модуль>\r\n\r\n"); textcolor(WHITE); cprintf("Для вычисление обрат-\r\n"); cprintf("ных элементов для\r\n"); cprintf("всего поля введите:\r\n"); textcolor(RED); cprintf("all\r\n\r\n"); textcolor(WHITE); cprintf("Для выхода из программы"); cprintf("введите:\r\n"); textcolor(RED); cprintf("exit"); textcolor(WHITE); } ///////////////////////////////////////////////////////////////////////////// //Функция проверяет модуль void VerifyT(long t) { cprintf("Новый модуль: %li",t); if (t<0) { textcolor(LIGHTRED); cprintf("\r\nОшибка! Недопустимое значение переменной."); cprintf("\r\nПеременная не должна принимать отрицательные значения."); textcolor(WHITE); } else { char ch1; cprintf("\r\nПроверить, является ли данное число простым? (y/n)\r\n"); cscanf("%c",ch1); ch1=getch(); if (ch1=='y') { short int pole=1; long n; n=2; if ((t%2==0)&&(t!=2)) pole=0; else { for (n=3; n<t;n=n+2) { cprintf("%li\r",n); if (t%n==0) { pole=0; break; } } } if (!pole) { textcolor(RED); cprintf("Число %li не является простым.\r\nОно делится, например, на %li. Измените модуль.\r\n",t,n); } else cprintf("Число %li является простым.\r\n",t); } } textcolor(WHITE); cprintf("Проверка завершена.\r\n"); } //////////////////////////////////////////////////////////////////////////////// //Функция вычисляет обратные элементы для всех элементов поля void all(long s, long t) { char ch; char KeyEsc=27; long s1,s2, NOD; double vr; #define Zagolovok cprintf("\r\nЭлемент |Обратный |Обр.*Элем.(mod %li)",t); Zagolovok cscanf("%c",&ch); for (s=1; s<t; s++) { NOD=RAlgEvklid(s,t,&s1,&s2); if (s1<0) s1=s1+t; vr=(s*s1)%t; if (NOD==1) cprintf("\r\n%11li|%11li|%11li",s,s1,long(vr)); else cprintf("\r\n%11li| -| -",s); if (s % 21==0) { cprintf("\r\nНажмите любую клавишу..."); cscanf("%c",&ch); if (ch==KeyEsc) break; Zagolovok } } cprintf("\r\nВывод завершён. Нажмите любую клавишу..."); cscanf("%c",&ch); } |