Отправляет email-рассылки с помощью сервиса Sendsay

Система компьютерной алгебры GAP

Подписаться Бесплатная «Серебряная» новостная рассылка . Временно не выходит ,возобновит выход - нет информации Подписчиков 783 RSS
←   Сентябрь 2004   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://www.gap-system.org/ukrgap/
Открыта: 05-02-2002

Автор
Александр Борисович Коновалов

Статистика

783 подписчиков
0 за неделю
←   Все выпуски   →

Система компьютерной алгебры GAP - #41, 16-09-04 (сравнения в кольце целых чисел)


Информационный Канал Subscribe.Ru
Рассылка "Система компьютерной алгебры GAP"
(http://subscribe.ru/catalog/science.exact.gap/)
ведущий рассылки А.Б.Коновалов, a_konovalov@hotmail.com
выпуск 41 от 16 сентября 2004 г.
На сайте Украинской группы пользователей GAP в разделе "Изучаем алгебру с GAP (http://ukrgap.exponenta.ru/Examples/Examples.htm) опубликован материал по теме "Сравнения в кольце целых чисел", который содержится в данном выпуске рассылки.
Сравнения в кольце целых чисел
(по материалам дипломной работы Жатько Н.В., 2003 г.)

C помощью системы GAP несложно установить, сравнимы ли два целых числа по заданному натуральному модулю. Например, зададим два числа и проверим, сравнимы ли они по модулю 13 двумя способами: сначала сравним их остатки, а потом проверим, что их разность делится на модуль:

gap> a:=454564;
454564
gap> b:=123133;
123133
gap> a mod 13 = b mod 13;
false
gap> IsInt((a-b)/13);
false

Действительно, (a-b)/13 равняется 331431/13, и не является целым числом.

Теперь зададим другую пару чисел, которые уже будут сравнимы между собой по модулю 13:

gap> a:=454564;
454564
gap> b:=a-13*4020;
402304
gap> a mod 13 = b mod 13;
true
gap> IsInt((a-b)/13);
true

Исследуем, какой из способов проверки сравнимости более эффективен. Создадим для этого две функции, реализующие ее различными способами:

Первый способ (проверка того, что разность чисел делится на модуль):

gap> IsCongruent:=function(a,b,m)
> return(IsInt((a-b)/m));
> end;
function(a, b, m) ... end
gap> IsCongruent(a,b,13);
true
gap> IsCongruent(a+1,b,13);
false

Второй способ (сравнение остатков от деления на модуль):

gap> IsCongruent2:=function(a,b,m)
> return(a mod m = b mod m);
> end;
function(a, b, m) ... end
gap> IsCongruent2(a,b,13);
true
gap> IsCongruent2(a+1,b,13);
false

Сравним теперь их быстродействие. Для этого, например, проверим сравнимость по модулю 13 для всевозможных пар целых чисел от 10000 до 11000:

gap> for i in [10000..11000] do
> for j in [10000..11000] do
> IsCongruent(i,j,13);od;od;
gap> time;
3738
gap> for i in [10000..11000] do
> for j in [10000..11000] do
> IsCongruent2(i,j,13);od;od;
gap> time;
2774

Таким образом, мы видим, что использование остатков по модулю приводит к более быстрой функции.

Теперь обратимся к алгебраическим структурам, возникающим на базе отношения сравнимости. Как известно, классы вычетов образуют кольцо относительно операций сложения и умножения, индуцированных сложением и умножением целых чисел. В системе GAP это кольцо получается следующим образом:

gap> R:=Integers mod 15;
(Integers mod 15)

Действительно, R является кольцом, со всеми стандартными свойствами и атрибутами, присущими кольцам такого вида:

gap> IsRing(R);
true
gap> KnownPropertiesOfObject(R);
["IsEmpty", "IsTrivial", "IsNonTrivial", "IsFinite", "IsWholeFamily", "IsDuplicateFree", "IsAdditivelyCommutative", "IsLDistributive", "IsRDistributive"]
gap> KnownAttributesOfObject(R);
["Size", "Representative", "RepresentativeSmallest", "Enumerator", "EnumeratorSorted", "AsList", "AsSSortedList", "ZeroImmutable", "OneImmutable", "GeneratorsOfDomain", "MultiplicativeNeutral-Element", "GeneratorsOfRingWithOne"]

Элементами данного кольца являются классы вычетов (ясно, что их всего 15):

gap> Elements(R);
[ZmodnZObj(0, 15), ZmodnZObj(1, 15), ZmodnZObj(2, 15),
ZmodnZObj(3, 15), ZmodnZObj(4, 15), ZmodnZObj(5, 15),
ZmodnZObj(6, 15), ZmodnZObj(7, 15), ZmodnZObj(8, 15),
ZmodnZObj(9, 15), ZmodnZObj(10, 15), ZmodnZObj(11, 15),
ZmodnZObj(12, 15), ZmodnZObj(13, 15), ZmodnZObj(14, 15)]
gap> Size(R);
15

Мы видим, что каждый класс вычетов характеризуется двумя параметрами - своим представителем и модулем, по которому он рассматривается. Это дает пользователю возможность выполнять действия над классами вычетов без дополнительного указания модуля, по которому они рассматриваются, т.к. модуль будет определен автоматически (попробуйте выполнить самостоятельно действия над классами вычетов по одинаковым и разным модулям; объясните, почему в одном случае они возможны, а в другом - нет).

Мультипликативная группа данного кольца состоит из тех классов вычетов, элементы которых взаимно просты с модулем (т.е. если из каждого такого класса взять по одному элементу, то получится приведенная система вычетов по модулю 15). Тогда количество таких классов (т.е. порядок мультипликативной группы кольца R) определяется функцией Эйлера от числа 15. Функция Эйлера в GAP вычисляется с помощью функции Phi:

gap> Phi(15);
8
gap> Phi(Factorial(50));
4218559200885839042679312107816703841788854953574400000000000000

С другой стороны, представители восьми классов вычетов, образующих приведенную систему вычетов, могут быть получены так:

gap> PrimeResidues(15);
[1, 2, 4, 7, 8, 11, 13, 14]

Однако, полученное в последнем примере множество не имеет дополнительной алгебраической структуры. Для того, чтобы в действительности получить группу обратимых элементов рассматриваемого кольца как алгебраическую структуру, нужно поступать так:

gap> Units(R);
<group with 2 generators>
gap> Size(last);
8
Элементами этой группы, как и элементами построенного выше кольца, также являются не целые числа, а классы вычетов.

gap> Elements(Units(R));
[ZmodnZObj(1, 15), ZmodnZObj(2, 15), ZmodnZObj(4, 15),
ZmodnZObj(7, 15), ZmodnZObj(8, 15), ZmodnZObj(11, 15),
ZmodnZObj(13, 15), ZmodnZObj(14, 15)]

Напомним, что по теореме Эйлера, если a и m - взаимно простые числа, то a^Phi(m) сравнимо с 1 по модулю m. В качестве упражнения проверим, что это так, для всех целых чисел a от 2 до 1000 и m от 2 до 100:

gap> for a in [2..1000] do
> for m in [2..100] do
> if Gcd(a,m)=1 then
> if not (a^Phi(m) mod m = 1) then
> Print("FALSE \n");
> fi;
> fi;
> od;
> od;

Убедимся, что условие (a,m) = 1 действительно является существенным:

gap> 8^Phi(12) mod 12;
4

Действительно, в этом случае сравнимость с 1 не имеет места.

Теперь покажем, как с помощью GAP можно решать сравнения произвольной степени методом испытания полной системы вычетов. Сначала научимся задавать многочлены с целочисленными коэффициентами. Вначале зададим переменную x:

gap> x:=Indeterminate(Integers, "x");
x

Тогда мы можем задавать многочлены от переменной x и вычислять их значения в заданных точках с помощью функции Value:

gap> f:=2*x^3-3*x^2+2*x-1;
-1+2*x-3*x^2+2*x^3
gap> Value(f,1);
0
gap> Value(f,0);
-1

Теперь создадим функцию CongruenceSolution(f,m), которая будет искать решения сравнения методом испытания полной системы вычетов:

CongruenceSolution:=function(f,m)
local sol, i;
sol:=[];
for i in [0..m-1] do
if Value(f,i) mod m = 0 then
Add(sol, i);
fi;
od;
return sol;
end;

Вот пример работы с этой функцией (используется многочлен f из предыдущего примера):

gap> CongruenceSolution(f,15);
[]
gap> CongruenceSolution(f,99);
[47]
gap> f:=25*x^3-36*x^2+18*x+13;
13+18*x-36*x^2+25*x^3
gap> CongruenceSolution(f,12);
[5]

Упражнение: усовершенствуйте предложенную функцию с учетом того, что количество решений сравнения не превосходит его степени.

Теперь покажем, как решать сравнения первой степени с одной неизвестной с помощью функции Эйлера. Для этого составим следующую функцию:

CongruenceDegreeOneSolution:=function(a,b,m)
local sol, d, a1, b1, m1, alpha, k;
sol:=[];
d:=Gcd(a,m);
if d>1 and not IsInt(b/d) then
return [];
else
if d=1 then
Add(sol, (b*(a^(Phi(m)-1))) mod m);
return sol;
else
a1:=a/d; b1:= b/d; m1:=m/d;
alpha:=CongruenceDegreeOneSolution(a1, b1, m1);
for k in [0..d-1] do
Add(sol, k*m1+alpha);
od;
return sol;
fi;
fi;
return sol;
end;
Пример работы с данной функцией:

gap> CongruenceDegreeOneSolution(25, 15, 17);
[4]
gap> CongruenceDegreeOneSolution(3, 8, 13);
[7]
gap> CongruenceDegreeOneSolution(7, 4, 9);
[7]
gap> CongruenceDegreeOneSolution(7, 4, 19);
[6]
gap> CongruenceDegreeOneSolution(20, 10, 25);
[[3], [8], [13], [18], [23]]

В заключение приведем еще несколько полезных теоретико-числовых функций.

Функция OrderMod возвращает порядок числа n по модулю положительного целого числа m. Если n и m не взаимно просты, то порядок не определен, и тогда функция возвращает 0; если же они взаимно просты, то возвращается наименьшее положительное i, такое что ni сравнимо с 1 по модулю m.

gap> OrderMod(2, 7); OrderMod(3, 7);
3
6 # отсюда видно, что 3 - примитивный корень по модулю 7

Функция LogMod(n, r, m) вычисляет дискретный r-логарифм целого числа n по модулю целого числа m, т.е. число l, такое что rl сравнимо с n по модулю m, если такое число существует; в противном случае возвращается fail:

gap> l:= LogMod(2, 5, 7); 5^l mod 7 = 2;
4
true
gap> LogMod(1, 3, 3); LogMod(2, 3, 3);
0
fail

Функция PrimitiveRootMod(m) возвращает наименьший примитивный корень по модулю m, если он существует, и fail в противном случае:

gap> PrimitiveRootMod(409);
21
PrimitiveRootMod(30);
fail

Функция IsPrimitiveRootMod(r, m) проверяет, является ли r примитивным корнем по модулю m.

gap> IsPrimitiveRootMod(2, 541); IsPrimitiveRootMod(-539, 541);
true
true
gap> IsPrimitiveRootMod(4, 541);
false
gap> ForAny([1..29], r -> IsPrimitiveRootMod(r, 30));
false # не существует примитивного корня по модулю 30

Функция Legendre(n, m) вычисляет символ Лежандра n по m. Напомним, что значение символа Лежандра равно 1, если n – квадратичный вычет по модулю m (т.е. если существует целое r, такое что r2 сравнимо с n по модулю m), и -1 в противном случае. При этом если такое число r может быть найдено с помощью функции RootMod(n,m):

gap> Legendre(5, 11);
1 # 4^2 = 5 mod 11 разрешимо
gap> RootMod(5,11);
4 # одно из двух его решений
gap> Legendre(6, 11);
-1 # r^2 = 6 mod 11 неразрешимо
gap> Legendre(3, 35);
-1 # r^2 = 3 mod 35 неразрешимо
С уважением,
Александр Борисович Коновалов
председатель Украинской группы пользователей GAP (http://ukrgap.exponenta.ru/)
доцент кафедры алгебры и геометрии Запорожского государственного университета
E-mail: a_konovalov (at) hotmail.com
http://subscribe.ru/
http://subscribe.ru/feedback/		 Подписан адрес:
Код этой рассылки: science.exact.gap		 Отписаться
В избранное