Система остаточных классов - введение - История изменений

Isaeva в 13:44, 24 июня 2015

2015-06-24T13:44:00Z

Isaeva в 13:41, 24 июня 2015

2015-06-24T13:41:27Z

Isaeva в 12:55, 24 июня 2015

2015-06-24T12:55:40Z

Isaeva в 09:49, 24 июня 2015

2015-06-24T09:49:11Z

Isaeva в 13:57, 12 февраля 2015

2015-02-12T13:57:38Z

Isaeva в 13:48, 12 февраля 2015

2015-02-12T13:48:12Z

Isaeva в 13:13, 12 февраля 2015

2015-02-12T13:13:03Z

Isaeva в 13:00, 12 февраля 2015

2015-02-12T13:00:53Z

Isaeva в 11:45, 12 февраля 2015

2015-02-12T11:45:20Z

Isaeva в 12:58, 23 января 2015

2015-01-23T12:58:45Z

← Предыдущая		Версия 13:44, 24 июня 2015
Строка 127:		Строка 127:


−	Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с <math>n</math> равен единице.	+	Т.е. это количество таких натуральных чисел из отрезка <math>[1; n]</math>, наибольший общий делитель (НОД) которых с <math>n</math> равен единице.

← Предыдущая		Версия 13:41, 24 июня 2015
Строка 118:		Строка 118:

	Смотри также [[Описание КТО II\|Китайская теорема об остатках(КТО II)]], [[Описание КТО III\|Китайская теорема об остатках (КТО III)]].		Смотри также [[Описание КТО II\|Китайская теорема об остатках(КТО II)]], [[Описание КТО III\|Китайская теорема об остатках (КТО III)]].
		+

	== Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю ==		== Теоремы Эйлера и Ферма, их роль в вычислении мультипликативных обратных элементов по заданному модулю ==

← Предыдущая		Версия 12:55, 24 июня 2015
Строка 306:		Строка 306:

	= Литература =		= Литература =
		+
		+	Бухштаб А. А. Теория чисел – М: Наука, 1975 г.
		+
		+	Айерленд К. Классическое введение в современную теорию чисел. М: Мир, 1987.
		+
		+	Акушинский И. Л., Юдицкий Д. И. Машинная арифметика в остаточных классах. – М. Советское радио, 1968.
		+
		+	Амербаев В. М. Теоретические основы мащинной арифметики, - Алма –Ата: Наука, 1976.
		+
		+
		+	''Дополнительно'':
		+
		+	Куликов Л.Я. Алгебра и теория чисел: Учеб. пособие для педагогических институтов. — М.: Высш. школа, 1979. — 559 с. http://allmath.ru/highermath/algebra/theorychisel-ugu
		+
		+	Сизый С. В. Лекции по теории чисел. Учебное пособие для математических специальностей. Екатеринбург, Уральский государственный университет им. А.М.Горького, 1999. http://stu.sernam.ru/book_algebra.php

@@ Строка 134: / Строка 134: @@
 Частным случаем теоремы Эйлера является малая теорема Ферма.
@@ Строка 148: / Строка 147: @@
 == Числа Мерсенна, Ферма и операции над ними ==
-При рассмотрении отдельных классов простых чисел интерес представляет вопрос о простых числах специального вида, например, числа Мерсенна или числа Ферма.
+При рассмотрении отдельных классов простых чисел интерес представляет вопрос о простых числах специального вида, например, таких как числа Мерсенна или числа Ферма.
 '''Определение'''
@@ Строка 298: / Строка 297: @@
 Расширение системы оснований является одной из основных немодульных операций в СОК. Выполнение этой операции бывает необходимо при выполнении операции деления чисел, при вычислении позиционных характеристик, при обнаружении переполнения при выполнении сложения или умножения чисел.
-Задачу расширения системы оснований можно сформулировать следующим образом: найти остаточное представление числа по новому основанию (новым основаниям), если известно представление числа по другим основаниям остатки от деления на другие числа.
+Задачу расширения системы оснований можно сформулировать следующим образом: найти остаточное представление числа по новому основанию (новым основаниям), если известно представление числа по другим основаниям (остатки от деления на другие числа).
 Один из путей расширения системы оснований состоит в переводе числа в позиционную систему счисления и вычисления остатка от деления на новый модуль. Этот путь не является рациональным с точки зрения числа операций.

@@ Строка 185: / Строка 185: @@
-== Выбор системы счисления ==
+== Выбор СОК как системы счисления ==
 Под системой счисления понимают совокупность символический метод записи чисел, представление чисел с помощью письменных знаков, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов.
@@ Строка 209: / Строка 209: @@
 Напротив, непозиционные коды с параллельной структурой позволяют реализовать распараллеливание операций на уровне выполнения элементарных арифметических действий.
-В качестве такой непозиционной системы удобна система остаточных классов.
+В качестве такой непозиционной системы удобна система остаточных классов (СОК).
-Основным достоинством системы остаточных классов является сравнительная простота выполнения модульных операций (сложения, вычитания, умножения), недостатком - большая трудоемкость операций, которые требуют знания всего числа в целом, называемых немодульными (например, сравнение чисел).
+Базовые арифметические операции в СОК делятся на две группы: модульные и немодульные.
 Смотри [[Представление числа в системе остаточных классов|Представление числа в системе остаточных классов]].
@@ Строка 218: / Строка 224: @@
 == Модульные операции над числами в системе остаточных классов ==
 Смотри [[Модульные операции|Модульные операции]].

← Предыдущая		Версия 13:48, 12 февраля 2015
Строка 185:		Строка 185:


−	== Выбор системы ~~остаточных классов для представления чисел~~ ==	+	== Выбор системы счисления ==

	Под системой счисления понимают совокупность символический метод записи чисел, представление чисел с помощью письменных знаков, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов.		Под системой счисления понимают совокупность символический метод записи чисел, представление чисел с помощью письменных знаков, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов.

@@ Строка 53: / Строка 53: @@
 Подробнее о свойствах сравнений и классах вычетов смотри [[Сравнения и их основные свойства| Сравнения и их основные свойства]]
 == Теорема о делении с остатком. Алгоритм Евклида ==
@@ Строка 184: / Строка 185: @@
-== Представление числа в системе остаточных классов. Модульные операции ==
+== Выбор системы остаточных классов для представления чисел ==
-−
-Всякая вычислительная структура тесно связана с системой счисления, в которой она работает.
 Под системой счисления понимают совокупность символический метод записи чисел, представление чисел с помощью письменных знаков, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов.
@@ Строка 204: / Строка 203: @@
 В непозиционных системах счисления величина, которую обозначает цифра, не зависит от её положения в числе. При этом система может накладывать ограничения на положение цифр.
 В обычной позиционной системе счисления (ПСС) значение разряда любого числа, кроме младшего, являющегося результатом двухместной арифметической операции, зависит не только от значения одноимённых операндов, но и от всех младших разрядов, т. е. ПСС обладает строго последовательной структурой.
@@ Строка 212: / Строка 213: @@
 Основным достоинством системы остаточных классов является сравнительная простота выполнения модульных операций (сложения, вычитания, умножения), недостатком - большая трудоемкость операций, которые требуют знания всего числа в целом, называемых немодульными (например, сравнение чисел).
-Смотри [[Представление числа в системе остаточных классов|Представление числа в системе остаточных классов]], [[Модульные операции|Модульные операции]].
+Смотри [[Представление числа в системе остаточных классов|Представление числа в системе остаточных классов]].

@@ Строка 178: / Строка 178: @@
 == Представление числа в системе остаточных классов. Модульные операции ==
-Всякая вычислительная структура тесно связана с системой счисления, в которой она работает. Под системой счисления понимают совокупность приёмов обозначения (записи) чисел, или, точнее, способ кодирования (представления) элементов некоторой конечной модели действительных чисел словами одного или более алфавитов. Кодирование представляет собой инъективное отображение диапазона системы счисления на декартово произведение его алфавитов, т. е. <math>F:D\mapsto A</math>, где <math>A = A_1 \times  A_2 \times \ldots \times A_n</math>.
+Всякая вычислительная структура тесно связана с системой счисления, в которой она работает.
-−
-Иначе говоря, отображение <math>F</math> элементу <math>x\in D</math> ставит в соответствие кодовое слово <math>(x_1, x_2, \ldots , x_n) </math>, где <math>x_i = A_i (i=1,\ldots,n) </math> - <math>i</math>-я цифра, <math>n</math> – длина кода.
-−
-С помощью обратного отображения <math>F^{-1}</math>, которое называют декодированием, можно определить систему счисления.
 К любой кодовой системе применимы следующие требования:
@@ Строка 192: / Строка 189: @@
-Таким образом, коды чисел являются именами числовых объектов, составляющих числовой диапазон. Диапазоны как модели вещественных чисел должны с максимально доступной полнотой и простотой отражать свойства числового множества.
+Системы счисления подразделяются на позиционные, непозиционные и смешанные. ([https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F#.D0.9D.D0.B5.D0.BF.D0.BE.D0.B7.D0.B8.D1.86.D0.B8.D0.BE.D0.BD.D0.BD.D1.8B.D0.B5_.D1.81.D0.B8.D1.81.D1.82.D0.B5.D0.BC.D1.8B_.D1.81.D1.87.D0.B8.D1.81.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F Система счисления])
-Всякое представление чисел рабочего диапазона является лишь составным элементом соответствующей машинной арифметики и не может рассматриваться отдельно от неё. Арифметические свойства той или иной системы счисления прежде всего определяются характером межразрядных связей, появляющихся в ходе выполнения операций над кодовыми словами. Исследования показали, что в рамках обычной позиционной системы счисления (ПСС) значительного ускорения выполнения операций добиться невозможно. Это объясняется тем, что в ПСС значение разряда любого числа, кроме младшего, являющегося результатом двухместной арифметической операции, зависит не только от значения одноимённых операндов, но и от всех младших разрядов, т. е. ПСС обладает строго последовательной структурой. Сегодня, предпочтение отдаётся вычислительным структурам, обладающими способностями к параллельной обработке информации. Этими особенностями обладают непозиционные коды с параллельной структурой, которые позволяют реализовать идею распараллеливания операций на уровне выполнения элементарных арифметических действий.
 Представление чисел в виде набора остатков от деления на выбранные натуральные модули - основания системы называется системой остаточных классов - СОК (residue number system - RNS) или модулярной системой счисления - МСС (modular system).
-Основным достоинством системы остаточных классов является сравнительная простота выполнения модульных операций (сложения, вычитания, умножения). Кроме модульных операций, в цифровых устройствах часто выполняются и такие операции, которые требуют знания всего числа в целом. Данные операции являются немодульными и относятся к классу позиционных операций, которые являются наиболее трудоемкими в непозиционной СОК.
+Основным достоинством системы остаточных классов является сравнительная простота выполнения модульных операций (сложения, вычитания, умножения), недостатком - большая трудоемкость операций, которые требуют знания всего числа в целом, называемых немодульными (например, сравнение чисел).
 Смотри [[Представление числа в системе остаточных классов|Представление числа в системе остаточных классов]], [[Модульные операции|Модульные операции]].

@@ Строка 122: / Строка 122: @@
 '''Определение'''
-Функция Эйлера <math>phi (n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>.
+Функция Эйлера <math>\varphi(n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>.
@@ Строка 130: / Строка 130: @@
 '''Tеоремa Эйлера'''
-Если <math>a</math> и <math>p</math> взаимно просты, то <math>a^{phi(p)} \equiv 1 \pmod p</math>, где <math>phi (n)</math> - функция Эйлера.
+Если <math>a</math> и <math>p</math> взаимно просты, то <math>a^{\varphi(p)} \equiv 1 \pmod p</math>, где <math>\varphi(n)</math> - функция Эйлера.