Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона
Представлены теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона, что существенно уменьшает количество операций, необходимых для перевода чисел из системы остаточных классов в десятичную систему исчисления. При этом соответствующий подбор модулей по...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/124690 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона / Я.Н. Николайчук, М.Н. Касянчук, И.З. Якименко // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 3-8. — Бібліогр.: 15 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-124690 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1246902017-10-03T03:02:46Z Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона Николайчук, Я.Н. Касянчук, М.Н. Якименко, И.З. Кибернетика Представлены теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона, что существенно уменьшает количество операций, необходимых для перевода чисел из системы остаточных классов в десятичную систему исчисления. При этом соответствующий подбор модулей позволяет достичь эффективного использования всех регистров разрядной сетки. Представлено теоретичні основи аналітичного обчислення коефіцієнтів базисних чисел перетворення Крестенсона, що істотно зменшує кількість операцій, необхідних для переведення чисел з системи залишкових класів у десяткову систему числення. При цьому відповідний підбір модулів дозволяє досягнути ефективного використання усіх регістрів розрядної сітки The paper presents the theoretical foundations for the analytical transformation of coefficients of basic numbers of Krestenson’s transformation, which significantly reduces the number of operations required to convert from residue number system to decimal one. The appropriate selection of modules allows the efficient use of all the word length registers. F 2014 Article Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона / Я.Н. Николайчук, М.Н. Касянчук, И.З. Якименко // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 3-8. — Бібліогр.: 15 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/124690 519.7 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Кибернетика Кибернетика |
| spellingShingle |
Кибернетика Кибернетика Николайчук, Я.Н. Касянчук, М.Н. Якименко, И.З. Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона Кибернетика и системный анализ |
| description |
Представлены теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона, что существенно уменьшает количество операций, необходимых для перевода чисел из системы остаточных классов в десятичную систему исчисления. При этом соответствующий подбор модулей позволяет достичь эффективного использования всех регистров разрядной сетки. |
| format |
Article |
| author |
Николайчук, Я.Н. Касянчук, М.Н. Якименко, И.З. |
| author_facet |
Николайчук, Я.Н. Касянчук, М.Н. Якименко, И.З. |
| author_sort |
Николайчук, Я.Н. |
| title |
Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона |
| title_short |
Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона |
| title_full |
Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона |
| title_fullStr |
Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона |
| title_full_unstemmed |
Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона |
| title_sort |
теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования крестенсона |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2014 |
| topic_facet |
Кибернетика |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/124690 |
| citation_txt |
Теоретические основы аналитического вычисления коэффициентов базисных чисел преобразования Крестенсона / Я.Н. Николайчук, М.Н. Касянчук, И.З. Якименко // Кибернетика и системный анализ. — 2014. — Т. 50, № 5. — С. 3-8. — Бібліогр.: 15 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT nikolajčukân teoretičeskieosnovyanalitičeskogovyčisleniâkoéfficientovbazisnyhčiselpreobrazovaniâkrestensona AT kasânčukmn teoretičeskieosnovyanalitičeskogovyčisleniâkoéfficientovbazisnyhčiselpreobrazovaniâkrestensona AT âkimenkoiz teoretičeskieosnovyanalitičeskogovyčisleniâkoéfficientovbazisnyhčiselpreobrazovaniâkrestensona |
| first_indexed |
2025-07-09T01:52:44Z |
| last_indexed |
2025-07-09T01:52:44Z |
| _version_ |
1837132380129722368 |
| fulltext |
ß.Í. ÍÈÊÎËÀÉ×ÓÊ, Ì.Í. ÊÀÑßÍ×ÓÊ, È.Ç. ßÊÈÌÅÍÊÎ
ÓÄÊ 519.7 ÒÅÎÐÅÒÈ×ÅÑÊÈÅ ÎÑÍÎÂÛ ÀÍÀËÈÒÈ×ÅÑÊÎÃÎ
ÂÛ×ÈÑËÅÍÈß ÊÎÝÔÔÈÖÈÅÍÒΠÁÀÇÈÑÍÛÕ
×ÈÑÅË ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÊÐÅÑÒÅÍÑÎÍÀ
Àííîòàöèÿ. Ïðåäñòàâëåíû òåîðåòè÷åñêèå îñíîâû àíàëèòè÷åñêîãî âû÷èñëåíèÿ êîýôôèöèåí-
òîâ áàçèñíûõ ÷èñåë ïðåîáðàçîâàíèÿ Êðåñòåíñîíà, ÷òî ñóùåñòâåííî óìåíüøàåò êîëè÷åñòâî
îïåðàöèé, íåîáõîäèìûõ äëÿ ïåðåâîäà ÷èñåë èç ñèñòåìû îñòàòî÷íûõ êëàññîâ â äåñÿòè÷íóþ
ñèñòåìó èñ÷èñëåíèÿ. Ïðè ýòîì ñîîòâåòñòâóþùèé ïîäáîð ìîäóëåé ïîçâîëÿåò äîñòè÷ü ýô-
ôåêòèâíîãî èñïîëüçîâàíèÿ âñåõ ðåãèñòðîâ ðàçðÿäíîé ñåòêè.
Êëþ÷åâûå ñëîâà: ñèñòåìà îñòàòî÷íûõ êëàññîâ, ñèñòåìà ìîäóëåé, áàçèñíûå ÷èñëà, ïðåîá-
ðàçîâàíèå Êðåñòåíñîíà, òåîðåòèêî-÷èñëîâûå áàçèñû.
ÂÂÅÄÅÍÈÅ
 íàñòîÿùåå âðåìÿ îäíîé èç ãëàâíûõ òåíäåíöèé â ðàçâèòèè ñðåäñòâ âû÷èñëèòåëüíîé
òåõíèêè ÿâëÿåòñÿ ñîçäàíèå âûñîêîïðîèçâîäèòåëüíûõ âû÷èñëèòåëüíûõ óñòðîéñòâ [1].
Ýòî îáóñëîâëåíî íåîáõîäèìîñòüþ ðåøåíèÿ âåñüìà âàæíûõ äëÿ òåîðèè è ïðàêòèêè
ìàòåìàòèêè çàäà÷, òðåáóþùèõ âû÷èñëåíèé ñ öåëûìè ìíîãîðàçðÿäíûìè ÷èñëàìè èëè
âåëè÷èíàìè, èçìåíÿþùèìèñÿ â ñðàâíèòåëüíî áîëüøèõ äèàïàçîíàõ [2].
 ñâÿçè ñ ýòèì èíòåíñèâíî ðàçâèâàåòñÿ ïðèêëàäíîé è âû÷èñëèòåëüíûé àñïåê-
òû òåîðèè ÷èñåë, êîòîðûå ïðèìåíÿþòñÿ â òåõíîëîãè÷åñêèõ ñèñòåìàõ äëÿ íàäåæ-
íîñòè ïåðåäà÷è, õðàíåíèÿ è îáðàáîòêè öèôðîâîé èíôîðìàöèè. Ýòî ïðèâîäèò ê íå-
îáõîäèìîñòè ðåøåíèÿ áîëüøîãî êîëè÷åñòâà çàäà÷, êîãäà âîçíèêàþò âû÷èñëåíèÿ,
ïðè êîòîðûõ öåëî÷èñëåííûå ïåðåìåííûå ìîãóò íàìíîãî ïðåâûøàòü ðàçðÿäíóþ ñåò-
êó ñóùåñòâóþùèõ óíèâåðñàëüíûõ êîìïüþòåðíûõ ñðåäñòâ, ÷òî îñîáåííî àêòóàëüíî
ñ ðàçâèòèåì êðèïòîãðàôè÷åñêèõ ìåòîäîâ è ñðåäñòâ çàùèòû èíôîðìàöèè [3, 4].
ÀÍÀËÈÇ ÏÓÁËÈÊÀÖÈÉ
Ëþáàÿ âû÷èñëèòåëüíàÿ ñòðóêòóðà òåñíî ñâÿçàíà ñ òåîðåòèêî-÷èñëîâûìè áàçè-
ñàìè (Ò×Á), â êîòîðûõ çàäàí ñïîñîá êîäèðîâàíèÿ (ïðåäñòàâëåíèÿ) ýëåìåíòîâ
íåêîòîðîé êîíå÷íîé ìîäåëè äåéñòâèòåëüíûõ ÷èñåë ýëåìåíòàìè îäíîãî èëè íå-
ñêîëüêèõ àëôàâèòîâ [5].
Àðèôìåòè÷åñêèå ñâîéñòâà êàæäîé ñèñòåìû ñ÷èñëåíèÿ, êîòîðûå ïîðîæäàþòñÿ
ñîîòâåòñòâóþùèìè Ò×Á, ïðåæäå âñåãî îïðåäåëÿþòñÿ õàðàêòåðîì ìåæðàçðÿäíûõ
ñâÿçåé, âîçíèêàþùèõ â õîäå âûïîëíåíèÿ ñîîòâåòñòâóþùèõ àðèôìåòèêî-ëîãè÷åñ-
êèõ îïåðàöèé [6]. Èññëåäîâàíèÿ ïîêàçûâàþò [5, 7], ÷òî â ïðåäåëàõ îáû÷íûõ (äåñÿ-
òè÷íîé, äâîè÷íîé) ïîçèöèîííûõ ñèñòåì ñ÷èñëåíèÿ ñêà÷êîîáðàçíîãî óñêîðåíèÿ âû-
ïîëíåíèÿ àðèôìåòè÷åñêèõ îïåðàöèé ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿ ïðàêòè-
÷åñêè äîñòè÷ü íåâîçìîæíî. Ýòî îáúÿñíÿåòñÿ òåì, ÷òî çíà÷åíèå êàæäîãî ðàçðÿäà
ëþáîãî ÷èñëà, êðîìå ìëàäøåãî, çàâèñèò îò çíà÷åíèÿ íå òîëüêî îäíîèìåííûõ îïå-
ðàíäîâ, íî è îò âñåõ ìëàäøèõ ðàçðÿäîâ, ò.å. ïîçèöèîííàÿ ñèñòåìà ñ÷èñëåíèÿ îáëà-
äàåò ñòðîãî ïîñëåäîâàòåëüíîé ñòðóêòóðîé è íåîáõîäèìîñòüþ âûïîëíåíèÿ ñêâîç-
íûõ ïåðåíîñîâ, ÷èñëî êîòîðûõ ïðîïîðöèîíàëüíî ðàçðÿäíîñòè ïðîöåññîðà. Òàêèì
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 3
© ß.Í. Íèêîëàé÷óê, Ì.Í. Êàñÿí÷óê, È.Ç. ßêèìåíêî, 2014
îáðàçîì, èñïîëüçîâàíèå ïîçèöèîííûõ ñèñòåì ñ÷èñëåíèÿ ïðèâîäèò ê ñóùåñòâåííî-
ìó óìåíüøåíèþ áûñòðîäåéñòâèÿ, óâåëè÷åíèþ âû÷èñëèòåëüíîé è âðåìåííîé ñëîæ-
íîñòè èñïîëüçóþùèõñÿ àëãîðèòìîâ. Îñîáåííî ýòî àêòóàëüíî äëÿ ïîâûøåíèÿ ýô-
ôåêòèâíîñòè îáðàáîòêè ìíîãîðàçðÿäíûõ ÷èñåë [2].
Òàêèì îáðàçîì, äëÿ ðåøåíèÿ ìíîãèõ íàó÷íûõ, òåõíè÷åñêèõ è ïðèêëàäíûõ
çàäà÷ ìîùíîñòè ñîâðåìåííûõ êîìïüþòåðîâ ìîæåò áûòü íåäîñòàòî÷íî. Íåñìîòðÿ
íà òî, ÷òî ðåñóðñû ñâåðõíîâîé âû÷èñëèòåëüíîé òåõíèêè, êîòîðàÿ ôóíêöèîíèðóåò
â ïîçèöèîííîé ñèñòåìå ñ÷èñëåíèÿ, ïîñòîÿííî ñîâåðøåíñòâóþòñÿ è óâåëè÷èâàþò-
ñÿ, îíè â ïðèíöèïå íå ìîãóò áûòü áåçãðàíè÷íûìè. Ýòî îçíà÷àåò, ÷òî îáøèðíûå
êëàññû ñóùåñòâóþùèõ ìåòîäîâ è àëãîðèòìîâ â ïðåäåëàõ áûñòðîäåéñòâèÿ, îáåñ-
ïå÷èâàþùåãîñÿ ñîâðåìåííûìè âû÷èñëèòåëüíûìè ñèñòåìàìè, íå ìîãóò áûòü ðåà-
ëèçîâàíû ïðàêòè÷åñêè, ò.å. ïîçèöèîííûå ñèñòåìû ñ÷èñëåíèÿ â íàñòîÿùåå âðåìÿ
èñ÷åðïûâàþò ñâîè âîçìîæíîñòè äëÿ ïîñòðîåíèÿ âûñîêîïðîèçâîäèòåëüíûõ âû÷èñ-
ëèòåëüíûõ ñèñòåì. Ôóíäàìåíòàëüíàÿ ñòðàòåãèÿ òåîðåòè÷åñêèõ è ïðàêòè÷åñêèõ èñ-
ñëåäîâàíèé çàêëþ÷àåòñÿ â èñïîëüçîâàíèè ïîäõîäîâ, îñíîâàííûõ íà èíòåíñèâíîì
ïðèìåíåíèè â âû÷èñëèòåëüíûõ ñèñòåìàõ ðàçëè÷íûõ ôîðì ïàðàëëåëèçìà. Äàííîé
îñîáåííîñòüþ îáëàäàþò íåïîçèöèîííûå êîäû ñ ïàðàëëåëüíîé ñòðóêòóðîé. Íàèáî-
ëåå ïåðñïåêòèâíàÿ èç íèõ — ñèñòåìà îñòàòî÷íûõ êëàññîâ (ÑÎÊ), êîòîðàÿ ïîçâîëÿ-
åò ðåàëèçîâàòü èäåþ ðàñïàðàëëåëèâàíèÿ íà óðîâíå âûïîëíåíèÿ ýëåìåíòàðíûõ
àðèôìåòè÷åñêèõ îïåðàöèé ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿ [7, 8]. Ïðåäñòàâëå-
íèå îïåðàíäîâ â âèäå îñòàòêîâ îò äåëåíèÿ íà ñðàâíèòåëüíî íåáîëüøèå âçàèìíî
ïðîñòûå ìîäóëè ïîçâîëÿåò èçáåæàòü ìåæðàçðÿäíûõ ïåðåíîñîâ è íàìíîãî óìåíü-
øèòü ÷èñëà, íàä êîòîðûìè âûïîëíÿþòñÿ îïåðàöèè. Êðîìå òîãî, ÑÎÊ, áëàãîäàðÿ
ñâîåìó ïðèðîäíîìó âíóòðåííåìó ïàðàëëåëèçìó, â ïîñëåäíèå ãîäû âûäâèãàåòñÿ
êàê íàèáîëåå ïðèîðèòåòíàÿ áàçîâàÿ îñíîâà äëÿ ïåðåäîâûõ âûñîêîïðîèçâîäèòåëü-
íûõ êîìïüþòåðíûõ òåõíîëîãèé, â ÷àñòíîñòè, òàêèõ êàê ìóëüòèïðîöåññîðíàÿ [9],
ñóïåðêîìïüþòåðíàÿ, íåéðîñåòåâàÿ [10] è ò.ä.
ÒÅÎÐÅÒÈ×ÅÑÊÈÅ ÎÑÍÎÂÛ ÑÎÊ
Ôóíäàìåíòàëüíîé îñíîâîé ÑÎÊ ÿâëÿåòñÿ òåîðèÿ ÷èñåë, â ÷àñòíîñòè êèòàéñêàÿ
òåîðåìà îá îñòàòêàõ [11]. Ëþáîå öåëîå ïîëîæèòåëüíîå ÷èñëî N â äåñÿòè÷íîé ñèñ-
òåìå ñ÷èñëåíèÿ ïðåäñòàâëÿåòñÿ â ÑÎÊ â âèäå îñòàòêîâ ( , , , ) , , ,b b bk p p pk1 2 1 2
� �
îò äåëåíèÿ N íà êàæäûé èç ïîïàðíî âçàèìíî ïðîñòûõ ìîäóëåé:
N b b bk p p pk10 1 2 1 2
� � �( , , , ) , , , , ãäå b N pi i� mod , k — êîëè÷åñòâî ìîäóëåé.
Ïðè ýòîì äîëæíî âûïîëíÿòüñÿ óñëîâèå N P� –1 ( )P p
i
k
i�
�
�
1
.
Îáðàòíîå ïðåîáðàçîâàíèå èç áàçèñà Êðåñòåíñîíà â äåñÿòè÷íóþ ñèñòåìó
ñ÷èñëåíèÿ äîñòàòî÷íî ãðîìîçäêîå è îñíîâûâàåòñÿ íà èñïîëüçîâàíèè êèòàéñêîé
òåîðåìû îá îñòàòêàõ [12]:
N b B Pi i
i
k
�
�
�
�
�
�
�
�
�
1
mod , (1)
ãäå B M mi i i� , M P pi i� / , mi íàõîäèòñÿ èç âûðàæåíèÿ ( )M m pi i imod �1
è äîëæíî âûïîëíÿòüñÿ óñëîâèå B Pi
i
k
�
�
�
�
�
�
�
�
�
1
1mod .
 íàñòîÿùåå âðåìÿ èçâåñòíî òðè ñïîñîáà ïîèñêà îáðàòíîãî ýëåìåíòà: 1) ïî-
ñëåäîâàòåëüíûì ïåðåáîðîì mi , ïîêà íå áóäåò âûïîëíÿòüñÿ óñëîâèå
M m pi i imod �1; 2) ñ ïîìîùüþ ôóíêöèè Ýéëåðà: m M pi i i� �
1mod
�
M pi
p
i
i�( ) 1
mod ; 3) ñ ïîìîùüþ ðàñøèðåííîãî àëãîðèòìà Åâêëèäà.
Âñå îíè äîñòàòî÷íî ãðîìîçäêè, òðåáóþò áîëüøèõ âû÷èñëèòåëüíûõ çàòðàò
è âðåìåííûõ ðåñóðñîâ ïðè âûïîëíåíèè äåëåíèé ñ îñòàòêîì, âîçâåäåíèè â ñòå-
ïåíü, íàõîæäåíèè ôóíêöèè Ýéëåðà. Ïðè÷åì âñå îïåðàöèè äîëæíû âûïîëíÿòüñÿ
íàä î÷åíü áîëüøèìè ÷èñëàìè, ÷òî ìîæåò ïðèâåñòè ê ïåðåïîëíåíèþ ðàçðÿäíîé
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
ñåòêè. Ê íåäîñòàòêàì ñëåäóåò îòíåñòè òàêæå îòñóòñòâèå âîçìîæíîñòè àíàëèòè-
÷åñêîãî îïðåäåëåíèÿ îáðàòíîãî ýëåìåíòà.
ß.Í. Íèêîëàé÷óê ïðåäëîæèë ñîâåðøåííóþ ôîðìó ÑÎÊ (ÑÔ ÑÎÊ), â êîòî-
ðîé ïîäáîð ìîäóëåé òàêîé, ÷òî M pi imod �1, ò.å. mi �1 [13]. Äàëüíåéøåå ðàçâè-
òèå äàííàÿ òåîðèÿ ïîëó÷èëà â ðàáîòàõ [14, 15]. Ïîêàçàí ìåòîä âûáîðà ñèñòåìû
ìîäóëåé äëÿ ÑÔ ÑÎÊ è ðàçðàáîòàíà åå ìîäèôèêàöèÿ, â êîòîðîé mi � �1. Îäíàêî
â ýòèõ ñëó÷àÿõ íå ñîâñåì ðàöèîíàëüíî èñïîëüçóþòñÿ ðåãèñòðû ðàçðÿäíîé ñåòêè,
êîëè÷åñòâî êîòîðûõ, êàê ïðàâèëî, ðàâíî ñòåïåíè äâîéêè.
Èñõîäÿ èç ñêàçàííîãî âûøå, öåëü äàííîé ïóáëèêàöèè — ðàçðàáîòêà ìåòîäîâ
ïîäáîðà ìîäóëåé äëÿ ýôôåêòèâíîãî èñïîëüçîâàíèÿ ðåãèñòðîâ ðàçðÿäíîé ñåòêè,
à òàêæå âûâåäåíèå àíàëèòè÷åñêîé ôîðìóëû äëÿ ïîèñêà îáðàòíîãî ýëåìåíòà ïðè
ñîîòâåòñòâóþùåì ïîäáîðå ìîäóëåé.
ÒÅÎÐÅÒÈ×ÅÑÊÈÅ ÎÑÍÎÂÛ ÀÍÀËÈÒÈ×ÅÑÊÎÃÎ ÍÀÕÎÆÄÅÍÈß
ÊÎÝÔÔÈÖÈÅÍÒΠÁÀÇÈÑÍÛÕ ×ÈÑÅË ÑÎÊ
Ðàññìîòðèì íàáîð ìîäóëåé:
ð
ð
ð
ð
p
p
n
n
n
n
i
n i
1
2
3
2
4
4
2
2 1
2 1
2 1
2 1
2 1
2
�
� �
� �
� �
� ��
– ,
,
,
,
,
�
�
k
n
k
n
k
k
p
�
�
� �
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
2
2
2 1
2 1
3
2
,
.
(2)
Èç ñèñòåìû (2) íåòðóäíî âèäåòü, ÷òî êàæäûé ñëåäóþùèé ìîäóëü íà äâå åäè-
íèöû áîëüøå îò ïðîèçâåäåíèÿ âñåõ ïðåäûäóùèõ. Ýòèì îïðåäåëÿåòñÿ âçàèìíàÿ
ïðîñòîòà ìîäóëåé, ïîñêîëüêó âñå îíè íå÷åòíû. Êðîìå òîãî, äèàïàçîí ðàññìàòðè-
âàåìûõ äåñÿòè÷íûõ ÷èñåë äëÿ âîçìîæíûõ ðàñ÷åòîâ îãðàíè÷èâàåòñÿ âûðàæåíèåì
P n k
�
�
2 12 1
, ãäå n — ñòåïåíü äâîéêè â ìîäóëå ð1.
Äëÿ íàõîæäåíèÿ îáðàòíîãî ýëåìåíòà m M pi i i�
1mod çàïèøåì ñèñòåìó
óðàâíåíèé:
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
M n n n n n
n
i
1
2 4 22 1 2 1 2 1 2 1 2 1
2
2
mod ( ) ( )( )( ) ( )
(
� � � � ��
�
� �
�
2 2
2
2
3 2
1 2 1 2 1
2 1 2 1 2
k kn n
n n nM
� �
� �
�)( ) ( );
( ) ( )(
mod
mod � � �
� �
�
� �
1 2 1 2 1
2 1 2 1
4 2
2 2
2
3 2
)( ) ( )
( )( ) (
n n
n n
i
k k
� �
� mod 2 1
2 1 2 1 2 1 2 1
2
3
2 2 4 2 2
n
n n n n
n
M
i
�
� �
� ��
);
( ) ( )( ) ( )
(
mod � �
�
� �
� � �2 2 23 2
1 2 1 2 1
k kn n)( ) ( )mod ;
����������������������
M i
n n n ni i k k
mod ( ) ( ) ... ( )(2 1 2 1 2 1 22 2 2 22 2 3� � � �
� �
�
� ��
2 2
1 2 12
1
) ( )
(
mod ;
mod
n
k
i
M
����������������������
2 1 2 1 2 1 2 12 2 2 23 3 2 3n n n n
k
k k k k
M
� � � �
� �
� �) ( )( ) ( )mod ;
mod mod .( ) ( ) ( )2 1 2 1 2 12 2 22 2 2n n nk k k� � �
� �
�
(3)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 5
 ïåðâîì óðàâíåíèè (3) äëÿ êàæäîãî ìíîæèòåëÿ ïðàâîé ÷àñòè ïîëó÷àåòñÿ
îñòàòîê 2, ïîýòîìó M n k n
1
12 1 2 2 1mod mod( ) ( )
�
. Âî âòîðîì óðàâíåíèè (3)
îñòàòîê îò ïåðâîãî ìíîæèòåëÿ ðàâíÿåòñÿ
2, âñå îñòàëüíûå ðàâíÿþòñÿ 2, ïîýòîìó
M n k n
2
12 1 2 2 1mod mod( ) ( )� �
�
.
Âî âñåõ îñòàëüíûõ óðàâíåíèÿõ, àíàëîãè÷íî âòîðîìó, ïåðâûé îñòàòîê
ñîñòàâëÿåò
2, äðóãèå ðàâíÿþòñÿ 2, ïðè÷åì ñ óâåëè÷åíèåì íîìåðà óðàâíåíèÿ íà
åäèíèöó êîëè÷åñòâî ìíîæèòåëåé (ñîîòâåòñòâåííî, è äâîåê) òîæå óìåíüøàåòñÿ íà
åäèíèöó.  ðåçóëüòàòå òàêèõ âû÷èñëåíèé ïîëó÷èì ñèñòåìó:
M
M
n k n
n k n
1
1
2
1
2 1 2 2 1
2 1 2 2
mod mod ;
mod mod
( ) ( )
( ) (
�
� �
�
1
2 1 2 2 13
2 2 2
)
( ) ( )
;
mod mod ;
m
M
M
n k n
i
� �
�
���������������
od mod( ) ( );( )2 1 2 2 12 1 22 2n k i ni i�
�
� �
�
���������������
M
M
k
n
k
n
k
k
�
�
� �
� �
�
�
�
�
�
1
2
2
2 1 4
2 1 2
3
2
mod
mod
( ) ;
( ) .
�
��
�
�
�
�
�
�
�
(4)
Òåïåðü èùåì âåëè÷èíû m M pi i i�
1mod . Â ïåðâîì óðàâíåíèè ñòåïåíü äâîé-
êè â ïðàâîé ÷àñòè çàïèøåì òàê: k a n k
� �1 1 1, ãäå 0 1� �k n. Òîãäà
2 2 1 2 2 2 1 2 2 11 1 1k n n a k n k n
� �
�
mod mod mod( ) ( ) ( ) ( ) . Îòñþäà âèäíî, ÷òî
m
n
k
n k
1
2
2
2
1
1� �
. (5)
Àíàëîãè÷íî èç âòîðîãî óðàâíåíèÿ èìååì k a n k
� �1 2 2 . Òîãäà
� �
� � �
�
2 2 1 2 2 2 1 1 21 2 2 2 2k n n a k n a k
mod mod mod( ) ( ) ( ) ( ) ( )2 1n � �
�
� � �
�
�
�
( ) ( )
( ),
(
1 2 2 1
2 2 1
2 2 1
2 2
2
2
1 2a k n
k n
k n
a
mod
mod
mod ), a2
�
�
�
��
Ðàññìîòðèì äâà âîçìîæíûõ ñëó÷àÿ.
1. à2 íå÷åòíîå; ê 2 2n � íóæíî äîáàâèòü ìîäóëü 2 1n � ñòîëüêî ðàç, ÷òîáû
ñóììà äåëèëàñü íà 2 2k
(ò.å. âòîðîå ñëàãàåìîå äîëæíî ðàâíÿòüñÿ 2 2k
). Èòàê,
2 2 2 1 2 2 2 2 2 2 2 2 2 2 22 2 2 2n n k n n k k n n k n� � �
� � � �
�
�
�� �
( )( ) 2 2k
.
Ïîäåëèâ íà 2 2k
, ïîëó÷èì îáðàòíûé ýëåìåíò: m n n k
2 2 2 12�
�
.
2. à2 ÷åòíîå; ïîëó÷åííîå çíà÷åíèå m2 íóæíî çàïèñàòü ñ ïðîòèâîïîëîæíûì
çíàêîì è ïðèáàâèòü ìîäóëü m n n k n n k
2 2 2 1 2 1 22 2�
� � �
( ) ( )mod . Èòàê,
îêîí÷àòåëüíàÿ ôîðìóëà èìååò âèä
m
a
a
n n k
n k2
2
2
2 2 1
2
2
2
�
��
�
�
��
,
,
(6)
Àíàëîãè÷íî èç òðåòüåãî óðàâíåíèÿ
m
a
a
n n k
n k3
2 2
3
2
3
2 2 1
2
3
3
�
��
�
�
��
,
,
(7)
ãäå k3 è à3 îïðåäåëÿþòñÿ èç ðàâåíñòâà k na k
� �2 2 3 3 .
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5
÷åòíîå.
íå÷åòíîå,
íå÷åòíîå,
÷åòíîå,
íå÷åòíîå,
÷åòíîå.
Èç i-ãî óðàâíåíèÿ èìååì
m
a
a
i
n n k
i
n k
i
i i
i
i
i
�
��
�
�
��
� �
�
2 2 1
2
2 2
2
2 2
2
,
,
(8)
ãäå k ³ è à ³ îïðåäåëÿþòñÿ èç ðàâåíñòâà k i na ki
i i
� �
( )1 2 2 .
Ðàññìîòðèì ( )k
1 -å óðàâíåíèå. Íåò íåîáõîäèìîñòè ðàñïèñûâàòü k i
1, ïî-
ñêîëüêó 2 22 2 3
� �
n k
. Äâàæäû äîáàâèâ ìîäóëü ê 2 22 3n k�
� è ïîäåëèâ íà
4,
ïîëó÷èì
mk
n k
�
�
1
2 22
3
. (9)
Àíàëîãè÷íî äëÿ ïîñëåäíåãî k-ãî óðàâ-
íåíèÿ
2 2
2
2 1
2
2 1
2
2n
n
k
k�
�
�
�
�( ) . Äîáà-
âèâ ìîäóëü, ïîëó÷èì
mk
n k
� �
2 2 12
. (10)
 òàáë. 1 ïðèâåäåíû çíà÷åíèÿ pi , M i ,
mi , à òàêæå äèàïàçîí âîçìîæíûõ ðàñ÷åòîâ
äëÿ k � 5 è ðàçëè÷íûõ çíà÷åíèé n. Èç òàá-
ëèöû âèäíî, ÷òî âåëè÷èíû M1, m1, M 2 , m2
ïðè ìàëûõ n ìîãóò ïðèíèìàòü ðàçëè÷íûå
çíà÷åíèÿ, ÷òî çàâèñèò îò ÷åòíîñòè èëè íå-
÷åòíîñòè êîýôôèöèåíòà à³ . Äðóãèå çíà÷å-
íèÿ M ³ , m³ èìåþò âèä, ñîîòâåòñòâóþùèé ñòåïåíè äâîéêè.
Íà ðèñ. 1 ïîêàçàíà ëîãàðèôìè÷åñêàÿ çàâèñèìîñòü ñòåïåíè n äëÿ ìîäóëÿ ð1 îò êî-
ëè÷åñòâà ìîäóëåé k äëÿ 512-ðàçðÿäíîãî ïðîöåññîðà ñîãëàñíî âûðàæåíèþ n k�
210 .
Èç ðèñóíêà âèäíî, ÷òî log 2 n ëèíåéíî óáûâàåò ñ óâåëè÷åíèåì êîëè÷åñòâà ìîäóëåé k.
ÇÀÊËÞ×ÅÍÈÅ
Ñîîòâåòñòâóþùèé ïîäáîð ìîäóëåé ïîçâîëÿåò äîñòè÷ü ýôôåêòèâíîãî èñïîëüçîâàíèÿ
âñåõ ðåãèñòðîâ ðàçðÿäíîé ñåòêè, à òàêæå ïîëó÷èòü àíàëèòè÷åñêóþ ôîðìóëó äëÿ ïî-
èñêà îáðàòíîãî ýëåìåíòà mi , ÷òî ñóùåñòâåííî óìåíüøàåò êîëè÷åñòâî îïåðàöèé, íå-
îáõîäèìûõ äëÿ ïåðåâîäà ÷èñåë èç ÑÎÊ â äåñÿòè÷íóþ ñèñòåìó ñ÷èñëåíèÿ.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ì å ë ü í è ê À . À . Àðõèòåêòóðà êîìïüþòåðà. — Ëóöê: Âîëûíñêàÿ îáëàñíàÿ òèïîãðàôèÿ,
2008. — 470 ñ.
2. Ç à ä ³ ð à ê à  . Ê . , Î ë å ê ñ þ ê Î . Ñ . Êîìï’þòåðíà àðèôìåòèêà áàãàòîðîçðÿäíèõ ÷èñåë. —
Êè¿â: Âèùà øê., 2003. — 264 ñ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2014, òîì 50, ¹ 5 7
íå÷åòíîå,
÷åòíîå,
Ò à á ë è ö à 1
n p1 M1 m1 p2 M2 m2 p3 M3 m3 p4 M4 m4 p5 M5 m5 P
2 2 12
1 1 2 12 � 4 4 2 14 � 2 74
2 2 18 � 2 38
26 2 116 � ,
2 116
215 2 132
3 23 1
2 4 2 13 � 2 5 2 16 � 2 76
23 2 112 � 2 312
210 2 124 � 2 124
223 2 148
4 2 14
1 1 2 14 � 1 1 2 18 � 2 78 – 25 2 116 � 2 316
214 2 132 � 2 132 – 231 2 164 –
5 2 15 – 16 2 2 15 � 2 155 – 2 2 110 � 2 710 – 27 2 120 � 2 320 – 218 2 140 � 2 140 – 239 2 180 –
6 2 16 – 16 22 2 16 � 2 156 – 22 2 112 � 2 712 – 29 2 124 � 2 324 – 222 2 148 � 2 148 – 247 2 196 –
… … … … … … … … … … … … … … … … …
i 2 1i
16 2 4i
2 1i � 2 15i
2 4i
2 12i � 2 72i – 22 3i
2 14i � 2 34i – 24 2i
2 18i � 2 18i – 28 1i
2 116i –
Ðèñ. 1. Ãðàôèê ëîãàðèôìè÷åñêîé çàâèñè-
ìîñòè ñòåïåíè n äëÿ ìîäóëÿ ð1 îò êîëè-
÷åñòâà ìîäóëåé k
0 2 4 6 8 k
10
8
6
4
2
log2 n
3. Ô å ð ã þ ñ ñ î í Í . , Ø í a é å ð Á . Ïðàêòè÷åñêàÿ êðèïòîãðàôèÿ: Ïåð. ñ àíãë. — Ì.: Èçäàòå-
ëüñêèé äîì «Âèëüÿìñ», 2005. — 424 ñ.
4. Ç à ä ³ ð à ê à Â . , Î ë å ê ñ þ ê Î . Êîìï’þòåðíà êðèïòîëîã³ÿ. — Êè¿â: Âèùà øê., 2002. — 504 ñ.
5. Í è ê î ë à é ÷ ó ê ß . Í . Òåîðèÿ èñòî÷íèêîâ èíôîðìàöèè. — Òåðíîïîëü: ÎÎÎ «Òåðíî-ãðàô»,
2010. — 536 ñ.
6. Ð à á è í î â è ÷ Ç . Ë . , Ð à ì à í à ó ñ ê à ñ  . À . Òèïîâûå îïåðàöèè â âû÷èñëèòåëüíûõ ìàøè-
íàõ. — Êèåâ: Òåõí³êà, 1980. — 264 ñ.
7. À ê ó ø ñ ê è é È . ß . , Þ ä è ö ê è é Ä . È . Ìàøèííàÿ àðèôìåòèêà â îñòàòî÷íûõ êëàññàõ. —
Ì: Ñîâ. ðàäèî, 1968. — 440 ñ.
8. Ò î ð ã à ø å â  . À . Ñèñòåìà îñòàòî÷íûõ êëàññîâ è íàäåæíîñòü ÖÂÌ. — Ì.: Ñîâ. ðàäèî,
1973. — 117 ñ.
9. Í è ê î ë à é ÷ ó ê ß . Í . ,  î ë û í ñ ê è é Î . È . , Ê ó ë û í à Ñ .  . Òåîðåòè÷åñêèå îñíîâû ïî-
ñòðîåíèÿ è ñòðóêòóðà ñïåöïðîöåññîðîâ â áàçèñå Êðåñòåíñîíà // Âåñòí. Õìåëüí. íàö. óí-òà. —
2007. – 1, ¹ 3. — Ñ. 85–90.
10. Ï ð è ì å í å í è å èñêóññòâåííûõ íåéðîííûõ ñåòåé è ñèñòåì îñòàòî÷íûõ êëàññîâ â êðèïòîãðà-
ôèè / Í.È. ×åðâÿêîâ, À.È. Ãàëóøêèí, À.À. Åâäîêèìîâ, À.Â. Ëàâðèíåíêî, È.Í. Ëàâðèíåíêî. —
Ì.: Ôèçìàòëèò, 2012. — 270 ñ.
11. Á ó õ ø ò à á À . À . Òåîðèÿ ÷èñåë. — Ì.: Ïðîñâåùåíèå, 1966. — 384 ñ.
12. Á î ð î ä è í Î . È . Òåîðèÿ ÷èñåë. — Êèåâ: Âûñø. øê., 1970. — 275 ñ.
13. Í è ê î ë à é ÷ ó ê ß . Ì . Ðàçðàáîòêà òåîðèè è êîìïëåêñîâ òåõíè÷åñêèõ ñðåäñòâ ôîðìèðîâàíèÿ,
ïåðåäà÷è è îáðàáîòêè öèôðîâûõ ñîîáùåíèé â íèçîâûõ âû÷èñëèòåëüíûõ ñåòÿõ àâòîìàòèçèðî-
âàííûõ ñèñòåì: Äèñ. … äîêòîð òåõí. íàóê. — Êèåâ: Àêàäåìèÿ íàóê ÓÑÑÐ, Èí-ò êèáåðíåòèêè
èì. Â.Ì. Ãëóøêîâà, 1991. — 573 ñ.
14. Ê à ñ ÿ í ÷ ó ê Ì . Í . Òåîðèÿ è ìàòåìàòè÷åñêèå çàêîíîìåðíîñòè ñîâåðøåííîé ôîðìû ñèñòåìû
îñòàòî÷íûõ êëàññîâ // Òð. Ìåæäóíàð. ñèìïîçèóìà «Âîïðîñû îïòèìèçàöèè âû÷èñëåíèé
(ÏÎΖÕÕÕV)». — Ò. 1. — Êèåâ; Êàöèâåëè. — 2009. — Ñ. 306–310.
15. Ê à ñ ÿ í ÷ ó ê Ì . Êîíöåïöèÿ òåîðåòè÷åñêèõ ïîëîæåíèé ñîâåðøåííîé ôîðìû ïðåîáðàçîâàíèÿ
Êðåñòåíñîíà è åãî ïðàêòè÷åñêîå ïðèìåíåíèå // Îïòèêî-ýëåêòðîííûå èíôîðìàöèîííî-ýíåðãå-
òè÷åñêèå òåõíîëîãèè. — 2010. — ¹ 2 (20). — Ñ. 43–48.
Ïîñòóïèëà 03.12.2013
|