Об аналитическом методе факторизации составных чисел
Трудности факторизации чисел сводятся к тому, что в кольце целых чисел существует одно уравнение, представляющее их произведение. Применение колец вычетов по модулю позволяет получить второе уравнение....
Saved in:
| Date: | 2013 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Series: | Комп’ютерні засоби, мережі та системи |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/69702 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об аналитическом методе факторизации составных чисел / М.В. Семотюк // Комп’ютерні засоби, мережі та системи. — 2013. — № 12. — С. 5-10. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-69702 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-697022015-07-16T09:40:23Z Об аналитическом методе факторизации составных чисел Семотюк, М.В. Трудности факторизации чисел сводятся к тому, что в кольце целых чисел существует одно уравнение, представляющее их произведение. Применение колец вычетов по модулю позволяет получить второе уравнение. Труднощі факторизації чисел зводяться до того, що в кільці цілих чисел існує одне рівняння, що представляє їх добуток. Використання кілець залишків по модулю дозволяє отримати друге рівняння. Difficulties factoring composite numbers reduced to the fact, that in the ring of integers there is only one equation that represents is a product of the numbers. The use of residue rings modulo allows you to get the second equation. This significantly reduces the computational cost. 2013 Article Об аналитическом методе факторизации составных чисел / М.В. Семотюк // Комп’ютерні засоби, мережі та системи. — 2013. — № 12. — С. 5-10. — Бібліогр.: 6 назв. — рос. 1817-9908 http://dspace.nbuv.gov.ua/handle/123456789/69702 512(075) ru Комп’ютерні засоби, мережі та системи Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
Трудности факторизации чисел сводятся к тому, что в кольце целых чисел существует одно уравнение, представляющее их произведение. Применение колец вычетов по модулю позволяет получить второе уравнение. |
| format |
Article |
| author |
Семотюк, М.В. |
| spellingShingle |
Семотюк, М.В. Об аналитическом методе факторизации составных чисел Комп’ютерні засоби, мережі та системи |
| author_facet |
Семотюк, М.В. |
| author_sort |
Семотюк, М.В. |
| title |
Об аналитическом методе факторизации составных чисел |
| title_short |
Об аналитическом методе факторизации составных чисел |
| title_full |
Об аналитическом методе факторизации составных чисел |
| title_fullStr |
Об аналитическом методе факторизации составных чисел |
| title_full_unstemmed |
Об аналитическом методе факторизации составных чисел |
| title_sort |
об аналитическом методе факторизации составных чисел |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2013 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/69702 |
| citation_txt |
Об аналитическом методе факторизации составных чисел / М.В. Семотюк // Комп’ютерні засоби, мережі та системи. — 2013. — № 12. — С. 5-10. — Бібліогр.: 6 назв. — рос. |
| series |
Комп’ютерні засоби, мережі та системи |
| work_keys_str_mv |
AT semotûkmv obanalitičeskommetodefaktorizaciisostavnyhčisel |
| first_indexed |
2025-07-05T19:09:27Z |
| last_indexed |
2025-07-05T19:09:27Z |
| _version_ |
1836835214875164672 |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2013, № 12 5
М. Semotyuk
AN ANALYTICAL METHOD
FOR FACTORING COMPOSITE
NUMBERS
Difficulties factoring composite
numbers reduced to the fact, that in
the ring of integers there is only one
equation that represents is a product
of the numbers. The use of residue
rings modulo allows you to get the
second equation. This significantly
reduces the computational cost.
Key words: factorization, the residue
ring modulo, the inverse elements.
Труднощі факторизації чисел зво-
дяться до того, що в кільці цілих
чисел існує одне рівняння, що
представляє їх добуток. Викори-
стання кілець залишків по модулю
дозволяє отримати друге рівняння.
Ключові слова: факторизація,
кільце залишків по модулю, зворо-
тні елементи.
Трудности факторизации чисел
сводятся к тому, что в кольце
целых чисел существует одно
уравнение, представляющее их
произведение. Применение колец
вычетов по модулю позволяет
получить второе уравнение.
Ключевые слова: факторизация,
кольцо вычетов по модулю, об-
ратные элементы.
М.В. Семотюк, 2013
УДК 512(075)
М.В. СЕМОТЮК
ОБ АНАЛИТИЧЕСКОМ МЕТОДЕ
ФАКТОРИЗАЦИИ СОСТАВНЫХ ЧИСЕЛ
Введение. Отыскание простых множителей
натурального числа называют для краткости
«факторизацией». Факторизация больших
чисел – чрезвычайно трудоемкая задача, да-
же с помощью электронных вычислительных
машин [1]. В работе [2] показано, что суще-
ствует точный метод факторизации состав-
ных чисел, основанный на решении системы
логических уравнений. Однако применение
этого метода на практике сталкивается с
трудностями решения этой системы уравне-
ний на современных ЭВМ в силу использо-
вания большого количества весьма мелких
логических операций. Однако, как и алго-
ритм Шора [3], он эффективен для фактори-
зации чисел на квантовом компьютере.
Основная часть. Все трудности факто-
ризации составных чисел исходят из того,
что в кольце целых чисел Z существует все-
го лишь одно уравнение, представляющее
факторизуемое число, вида
C = a · b, (1)
где а и b – числа, из которых состоит это
число. Однако в кольце вычетов mZ можно
получить второе уравнение. Тогда, согласно
определению, в кольце вычетов mZ [4] суще-
ствуют обратные элементы по отношению
операции сложения такие, что
aa ′+ mZ 0, bb ′+
mZ 0,
m – модуль этого кольца вычетов mZ , кото-
рые определяются как
maa =′+ , mbb =′+ , (2)
или
ama −=′ , bmb −=′ , (3)
М.В. СЕМОТЮК
Комп’ютерні засоби, мережі та системи. 2013, № 12 6
где a', b′ – обратные элементы (дополнения до m) чисел a и b этого же кольца.
Тогда
ba ′⋅ = a · (m – b) = m · a – a · b,
откуда
– a · b= ba ′⋅ - m · a.
Однако
С' = m2 – C,
где С' – обратный элемент в кольце вычетов mZ по отношению к C, где модуль
кольца равен m2.
Тогда в кольце вычетов mZ можно записать
С' mZ ba ′⋅ – m · a. (4)
Таким образом, получено второе уравнение (3), которое вместе с (1) состав-
ляет следующую систему уравнений:
⋅−′⋅=′
⋅=
.
,
ambaC
baC
(5)
Очевидно, что решение этой системы возможно если
m > ba ′⋅ , (6)
что разделяет второе уравнение системы (4) на две части. Тогда
ba ′⋅ = (С') mod m. (7)
Используя алгоритм Эвклида, легко находим решение. Или еще проще
– m · a = С' – (С') mod m,
что равносильно
– a = int (С'/m),
откуда
a = m – int (С'/m). (8)
Пример. Пусть a = 5, b = 7, С = 35, m = 8, С '= 64 – 35 = 29.
Тогда a = 8 – int (29/8) = 5.
Круг факторизуемых чисел для данного способа можно расширить, если по-
ложить, что b = m + b'. Тогда
C = a · b= a · (m + b') = m · a + a · b',
а с учетом (5) имеем
a = int (С/m). (9)
Пример. Пусть a = 3, b = 17, С = 51, m = 16. Тогда a = int (51/16) = 3.
Данные два выражения (7) и (8) совместно с известной теоремой Ферма [5], ос-
нованной на представлении числа разность квадратов
C = x2 – y2, (10)
где x = (a+b)/2, y = (a – b)/2, позволяют эффективно факторизовать составные
числа на ЭВМ за приемлемое время, ибо выражение (10) эффективно, когда
числа a и b близки по величине, при этом выражения (8) и (9) эффективны, если
числа a и b существенно различаются.
ОБ АНАЛИТИЧЕСКОМ МЕТОДЕ ФАКТОРИЗАЦИИ …
Комп’ютерні засоби, мережі та системи. 2013, № 12 7
Однако существует метод факторизации, не требующий применения выра-
жения (8). Он исходит из следующих предпосылок. Перемножив формулы вы-
ражения (2) имеем
( aa ′+ ) · ( bb ′+ ) = m2.
Далее с учетом выражений (3) полученная запись примет вид
a · b + (m – a) · b + a · (m – b) + ba ′⋅′ = m2,
a · b + m · b – a · b +m · a – a · b + ba ′⋅′ = m2,
m · (a + b) – a · b + ba ′⋅′ = m2, (11)
а в кольце вычетов mZ имеем разновидность известного звездного произведения
[6]
a · b mZ m · (a + b) + ba ′⋅′ . (12)
Из выражений (11) находим
a +b = (m + a · b – ba ′⋅′ )/ m,
а вместе с (1) имеем систему уравнений
=⋅
⋅′−⋅+=
.
)/ ( + 2
Сba
mbabamba
(13)
Если же выбрать модуль m таким образом, что
m > ba ′⋅′ , (14)
то из (12) в кольце mZ следует соотношение
( ba ′⋅′ ) mod m mZ (a · b) mod m. (15)
Тогда систему уравнений можно переписать
=⋅
⋅−⋅+=
Сba
mmbabamba ,)/ mod )( ( + 2
или
=⋅
−+=+
.Сba
mmССmba ,)/ mod )( ( 2
(16)
Решение этой системы уравнений приводит к квадратному уравнению вида
a2 – ka + C = 0.
Ее корни равны
а1,2 =
2
С*4кк 2 −± , (17)
где
k = m)/m mod )C(C m( 2 −+ . (18)
Здесь же заметим, что k/2 есть ни что иное, как переменная x из формулы
Ферма (10)
x = k/2= m)/2m mod )C(C m( 2 ⋅−+ , (19)
при этом переменная у этой же формулы равна
М.В. СЕМОТЮК
Комп’ютерні засоби, мережі та системи. 2013, № 12 8
y =
2
42 Ск ⋅−
=
2
402 CmmCCm ⋅−−+ )/ mod )((
. (20)
Пример. Пусть числа а и b равны 11 и 13 соответственно. Выберем модуль
m = 16. Тогда
С = 11 · 13 = 143, m2 = 256, k = (256 + 143 – (143) mod 16)/16 = 24
и а1,2 =
2
14342424 2 ⋅−±
=
2
224 ± , a = a1 = 11, b = a2 = 13.
Условие (14) может и не выполнятся. Тогда можно изменить представле-
ние (3)
a = m + a1, b = m+ b1 (21)
и
C = a · b = (m+ a1) · (m + b1) = m2 + m · (a1 + b1) + a1 · b1,
откуда
m · (a1 + b1) = C – m2 – a1 · b1,
a1+ b1 = (C – m2 – a1 · b1)/m
или
a + b = a1 + b1 + 2 · m = (C – m2 – a1 · b1)/m+2 · m
и, окончательно, система уравнений с условием
m > a1 · b1,
запишется
=⋅
⋅+−−=
Сba
mmmСmСba ,2)/ mod )( ( + 2
(22)
и решить ее не составляет никаких трудностей.
Заметим, что кроме представлений по выражениям (3) и (21), существует
еще два представления чисел а и b, одно из которых
a = m + a1, b = m – b' , (23)
тогда
C = a · b = (m + a1) · (m – b') = m2 + m · (a1 – b') – a1· b' =
= m2 + m · a1 – a1 · b – m · b'. (24)
Из выражений (22) имеем
a1 = a – m и b' = m – b (25)
и подставляя эти значения в (23), получаем
C = m2 + m · a1 – a1 · b' – m · b' = m2 + m · (a – m) – a1 · b' – m · (m – b) =
= m2 – m2 + m · a – a1 b' + m · b – m2.
Приводя подобные члены, имеем
C = m · (a + b) – a1 · b '– m2. (26)
Нетрудно заметить, что если в качестве модуля m выбрать число
m = (a + b)/2, (27)
то тогда частный случай выражения (26) при таком модуле представляет собой
ОБ АНАЛИТИЧЕСКОМ МЕТОДЕ ФАКТОРИЗАЦИИ …
Комп’ютерні засоби, мережі та системи. 2013, № 12 9
не что иное, как формулу Ферма (10).
Действительно, заменив переменные в соответствии с (25), (27) имеем
C = m · (a + b) – a1 · b' – m2 = m · (a + b) – (a – m) · (m – b) – m2,
C = ((a + b)/2) · (a + b) – (a – (a + b)/2)) · ((a + b)/2) – b) – ((a + b)/2)2.
Выполнив указанные в последнем выражении операции и приводя подобные
члены, получим известную формулу Ферма (10)
C = ((a + b)/2)2 – ((a – b)/2)2.
Далее, если член a1·b' в выражении (25) удовлетворяет условию
a1 · b '< m, (28)
то из выражения (26) следует
a + b = (C + m2 + (C ') mod m)/m,
где a1 · b' = (C ') mod m.
Окончательно, система уравнений с условием a1 · b' < m запишется как
=⋅
++=
.
,m)/m )mod' (Cm (C + 2
Сba
ba
(29)
Впрочем, представление чисел а и b, в котором
a = m – a1, b = m + b' ,
не имеет смысла рассматривать, так как b' должно быть отрицательным числом.
Следовательно, оно сводится к представлению (3) и системе уравнений (16).
Заметим, что всегда существует модуль m такой, что, по крайней мере, ус-
ловие (28) всегда выполняется, так как из представления (22) следует, что вы-
полняется следующее соотношение:
a > m > b. (30)
Действительно, полагая m = a – 1 и учитывая, что b' = m – b, (т. е. b' меньше m)
имеем по выражению (28) 1· b' < m, что и требовалось доказать.
Заметим, что в указанном методе факторизации с применением колец выче-
тов mZ возможно применение двух модулей m1 и m2 таких, что
m1 > a, m2 > b и a > b, (31)
что обычно имеет место на практике.
Тогда модуль кольца вычетов равен m1 · m2 и
C = a · b = (m1 – a') · (m2 – b') = m1 · m2 – m2 · a' – m1· b' + a'· b'.
Заменив a' на m1 – a и b' на m2 – b имеем
C = m1 · m2 – m2 · a ' – m1 · b'+ a '· b'= m1 · m2 – m2 · (m1 – a) – m1 · (m2 – b) + a' · b'
или
C = m1 · m2 – m1 · m2 + m2 · a – m1 · m2 + m1 · b + a '· b' =
= – m1 · m2 + m2 · a + m1 · b + a '· b',
откуда
m2 · a + m1 · b = C + m1 · m2 – a '· b'.
Полагая, что a ' · b' = (C) mod m2 имеем уравнение
М.В. СЕМОТЮК
Комп’ютерні засоби, мережі та системи. 2013, № 12 10
m2 · a + m1 · b = C + m1· m2 – (C) mod m2 . (32)
Вместе с (1) получаем следующую систему уравнений:
=⋅
⋅+=⋅+⋅
.Сba
,mCmmCbmam 22112 mod )(- (33)
Решить данную систему не представляет никаких трудностей, так как в конеч-
ном счете это обыкновенное квадратное уравнение.
Выводы. Таким образом, изложенное выше показывает, что применение
кольца вычетов по простому модулю позволяет создать аналитический метод
факторизации составных чисел. Он сводит процедуру факторизации к решению
системы алгебраических уравнений второго порядка. Решением этой системы, в
свою очередь, является обыкновенное квадратное уравнение. Это достигается
путем грубого выбора соответствующего модуля кольца вычетов, что в конеч-
ном счете существенно сокращает вычислительные затраты на факторизацию в
целом.
1. Бойко А.А., Зиятдинов Д.Б., Ишмухаметов Ш.Т. Об одном подходе к проблеме фактори-
зации натуральных чисел. – М.: Изв. вузов. матем., 2001. – № 4. – С. 15 – 22.
2. Семотюк М.В. О существовании точного метода факторизации составных чисел //
УСиМ. – 2011. – № 6. – С. 46 – 52.
3. Shor P. Polynomial –Time Algorithms for Prime Factorization and Discrete Logarithms on a
Quantum Computer // SIAM Jour. Comp. – 1997. – Vol. 26, N 5. – Р. 1484 – 1509.
4. Семотюк М.В. Заметки по машинной алгебре/монография. – Киев: Сталь, 2012. – 250 с.
5. Коблиц Н. Курс теории чисел и криптографии. – М.: Научное издательство ТВП, 2001. –
254 с.
6. Ван дер Варден Б.Л. Алгебра. – М.: Наука, 1979. – 624 с.
Получено 12.09.2013
http://www.padabum.com/data/%D0%A4%D0%B8%D0%B7%D0%B8%D0%BA%D0%B0/%D0%9A%D0%BE%D0%B1%D0%BB%D0%B8%D1%86%20%D0%9D.%20-%20%D0%9A%D1%83%D1%80%D1%81%20%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8%20%D1%87%D0%B8%D1%81%D0%B5%D0%BB%20%D0%B8%20%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D0%B8.%20%D0%9C..%202001.pdf
|