Разрешимость задачи дискретного логарифмирования в кольцах вычетов

Math-Net.Ru
Общероссийский математический портал
О. Н. Василенко, О разрешимости задачи дискретного логарифмирования в кольцах вычетов,
Фундамент. и прикл. матем., 2002, том 8, выпуск 3, 647–653
https://www.mathnet.ru/fpm684
Использование Общероссийского математического портала Math-Net.Ru подразумевает, что вы прочитали и согласны с пользовательским соглашением
https://www.mathnet.ru/rus/agreement
Параметры загрузки:
IP: 88.147.173.85
29 августа 2025 г., 08:58:57
О разрешимости задачи дискретного
логарифмирования в кольцах вычетов
Московский
О. Н . В А С И Л Е Н К О
государственный
университет
им. М. В. Ломоносова
УДК 511.9
К л ю ч е в ы е слова: дискретное логарифмирование, криптография.
Аннотация
Статья посвящена разрешимости задачи дискретного логарифмирования
по составному модулю. Доказаны две теоремы, дающие необходимые и до­
статочные условия для разрешимости в некоторых случаях. Также предложен
метод проверки разрешимости, аналогичный алгоритму Полига—Хеллмана для
решения задачи дискретного логарифмирования.
Abstract
О. N. Vasilenko, On the solvability of the discrete logarithm problem in
residue classes, Fundamentalnaya i prikladnaya matematika, vol. 8 (2002), no. 3,
pp. 647-653.
The article is devoted to solvability of the discrete logarithm problem modu­
lo composite number. Two theorems are proved, giving necessary and sufficient
conditions for solvability in some cases. Also one method is suggested for prov­
ing solvability, analogous to the Pohlig—Hellman algorithm for solving the discrete
logarithm problem.
Мы обозначаем (m, n) и [m, n] наибольший делитель и наименьшее общее
к р а т н о е целых чисел
тип.
Пусть s Е N , s > 1, s нечётно и известно полное разложение s на простые
множители qi:
iR
(i)
Пусть т а к ж е известно полное разложение д8- — 1 на простые множители:
J
>f/ ,
i =i =IL
i
Пусть a,b <Е Ж, (a,s)
= (b,s)
i = l,...,k.
(2)
= 1. Мы будем исследовать р а з р е ш и м о с т ь
уравнения
а* = 6 ( m o d s ) .
Фундаментальная
и прикладная математика, 2002, том 8, № 3, с. 647—653.
© 2002 Центр новых информационных технологий МГУ,
Издательский дом «Открытые системы»
(3)
648
О. Н. В А С И Л Е Н К О
Мы будем обозначать (р(х) функцию Эйлера, Х(х) — функцию К а р м а й к л а :
A(j)"1 . . .р"*) = [(pip"1), . . ., ср(р"*)], где a j G N, Pi — различные нечётные про­
стые числа. Также обозначим для нечётного числа г Q(x,r) частное Ферма:
Q(x,r) = ((хх(г> — 1)/г) (mod г); оно определено при х £ Ж, (х,г) = 1. Кроме
т о г о , i/p (га) обозначает к р а т н о с т ь вхождения простого числа р в разложение га
на множители, (Ж/тЖ)* — группа о б р а т и м ы х по модулю га элементов, ord(n
(mod га)) — порядок элемента п £ (Ж/тЖ)*.
Посмотрим сначала, как можно р е ш а т ь уравнение (3). Пусть д, — перво­
образные корни по модулям q"'; их можно найти перебором, зная (2). Пусть
с8- удовлетворяет сравнениям с8- = gi (mod <?"'), с8- = 1 (mod ()g • J ) при j 7^ *'•
Тогда Cj (mod s) имеет порядок <p(q"') = Mi и (Ж/вЖ)* = ( C I ) M I X . . . X (с^)мк
есть разложение группы ( Z / s Z ) * в прямое произведение циклических.
Пусть
а = cf 1 . . . с£к (mod s), b = cf1 . . . cffc (mod s).
(4)
Числа Ai находим из уравнений дУ = a (mod q"') (аналогично Bi), т о есть нам
надо уметь р е ш а т ь уравнение
ду = h (mod qu),
(5)
где q — простое нечётное число, и £ N, д — первообразный корень по моду­
лю qu. Из [5] известно, ч т о у (mod cp(qu)) есть единственное решение системы
уравнений
Q(</,<Z u - 1 )-j/ = Q(A,<Z u - 1 )(mod< Z "- 1 ),
у= [log/г] 1 (mod q-
l),
где [log/г] 1 есть решение уравнения qz = h (mod q). Таким образом, реше­
ние (5), и следовательно нахождение чисел Ai, Bi, сводится к дискретному
логарифмированию по простому модулю q. В общем случае это трудная зада­
ча (см. обзоры [2,3,6]). Известно её быстрое решение лишь в случае, когда q — l
раскладывается на маленькие простые числа (алгоритм Полига-Хеллмана [4]).
Допустим, ч т о нам всё же известны числа Ai, Bi в (4). Тогда из (3) следует,
ч т о gf'x = gfi (mod q"<), i=l,...,k,
откуда
А{х = В{ (mod <p(q^)),
i = l , . . . , A.
(6)
Ч т о б ы система уравнений (6) имела решение, необходимо, ч т о б ы числа
Di = (Ai,ip(q"'))
делили Bi. Если это выполняется, т о из (6) следует, ч т о
Для разрешимости системы уравнений (7) необходимо и достаточно, ч т о б ы
при всех г ф j правые части г'-го и j ' - r o уравнений были сравнимы по модулю
(<p(q"')/Di, Lp(q-3)/Dj).
В этом случае мы найдём решение (7):
х0
Di
'•'•'
Dk
(8)
ЗАДАЧА ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В КОЛЬЦАХ ВЫЧЕТОВ
649
Для уравнения (3) искомое х определено по модулю порядка ord(a (mod s)),
делящего A(s); э т о т порядок можно найти, зная (1) (см. а л г о р и т м в [1, гл. 1]).
В теории групп хорошо известна следующая лемма.
Л е м м а 1. Для определённых
выше чисел Di выполнено
ord(a (mod s))
Di
'
'
равенство
Dk
Следовательно, (8) есть искомое решение уравнений (3) в случае, когда оно
разрешимо.
В некоторых случаях уравнение (3) для составного модуля s всё же реша­
ется достаточно быстро, если оно разрешимо. Такие примеры есть в [5]. Они
строятся с помощью А-низких чисел. Однако и здесь приходится для най­
денного по соответствующей формуле с частным Ф е р м а значения х делать
проверку.
Таким образом, мы видим, ч т о проверка разрешимости уравнения (3)
представляет собой отдельную задачу. Э т о проявляется при решении систем
(6) и (7), а т а к ж е в хороших примерах с А-низкими числами.
Рассмотрим теперь вопрос о разрешимости (3). Для удобства изложения
приведём хорошо известную лемму о порядках элементов.
п
Л е м м а 2. Пусть q — нечётное простое число, q — 1 = Г] р-3 есть разло3=1
жение q — 1 на простые множители, и £ N, а, Ь £ (Ж/'qu7L)*, a ^ 1 (mod qu), g —
первообразный
корень по модулю qu.
1. Если ord(a (mod qu)) = д"" 1 "/ 3 » f[ p"i~Pi,
то a = gq^° Ш=гР/1
(mod qu),
3=1
где 0 < / < cp(qu). При этом если и>1и/Зо<и
(]j < Ctj, ТО Pj
— 1, или и = 1, т о q j /; если
\l.
2. Сравнение ax = Ь (mod qu) разрешимо тогда и только тогда,
ord(& (mod qu)) \ ord(a (mod <?")).
когда
Л е м м а 3 . Уравнение (3) разрешимо тогда и только тогда, когда
шима система
уравнении
разре­
А{Х = Bi (mod q"'~ ),
_
aiJ
AiX = Bi (mod Pij j ,
j = l,...,Wi,
i = l , . . . , A.
(9)
Д о к а з а т е л ь с т в о . ax = b (mod s) т о г д а и только тогда, когда ci 'x = ci '
(mod g"') для i = l,...,k.
Для э т о г о необходимо и достаточно, ч т о б ы
AiX = Bi (mod <p(q"')), i = 1, . . . ,k, ч т о равносильно системе
А{х = В{ ( m o d ^ - - 1 ) ,
V
i=i
650
О. Н. В А С И Л Е Н К О
Т е о р е м а 1. Пусть в (2) рц = 2, ац = 1, г = 1, . . ., к (числа д8Пусть также все простые числа д8 и pij, j = 2, . . ., Wi, i = 1, . . ., k,
нечётны).
различны.
wг
Пусть a ^ 1 (mod q"'), ord(a (mod ?"')) = g ! 1 ' - 1 - ' 3 ' 0 JJ р"Г~
", * =
l,...,k,
j=i
причём /38-о < Ui — 1, если w8 > 1, и fyj < ац для всех j =
Пусть также для г = 1, . . ., k ord(& (mod <?"')) | ord(a (mod q"'))разрешимо тогда и только тогда, когда
6g,"
i_l2
Vi = _ F ( m o d g ^ ) ,
l,...,Wi,i=l,...,k.
Уравнение (3)
i=l,...,k,
где F = 1 или F = — 1.
Д о к а з а т е л ь с т в о . Если к = 1, т о утверждение теоремы тривиально сле­
дует из леммы 2. Пусть к > 1. Из (4) и леммы 2, пункт 1, следует, ч т о
^ = <zf i 0 II#- L '-> » = !.•••.*.
i=i
где (Li, cp(q"')) = 1. З а м е т и м , ч т о если и8- = 1, т о /Зг'о = 0, и можно с ч и т а т ь ,
ч т о qt \ Li. Пусть
W г
ord(& (mod q^))
= q ^
1
- ^ Цр^~^,
i=i
i=l,...,k,
т о г д а 78j ^ /3jj при всех j = 0, . . ., Wi, i = 1, . . ., к.
Из леммы 2 получаем,
wг
ч т о В,- = q]'° П J?7;J • Mi.
Применим лемму 3 и сведём разрешимость (3) к
3=1
разрешимости (9). Если мы рассмотрим уравнение А^х = Bi (mod q"'~ ) из
этой системы, т о оно будет равносильно уравнению
W г
Wг
Pi
П # • Ux = qT°- ° UP™-M< ( m ° d <h'-1-"'°),
3=1
(Ю)
3=1
которое разрешимо (если щ = 1, т о это очевидно, если щ > 1, т о g8- j L8-). Если
мы рассмотрим уравнение вида
А{х
= В{ (mod p^),
j>l,
(11)
т о оно т а к ж е будет разрешимо, т а к как vPi\Ai)
= fyj <i b>Pt(Bi). При этом
модули в (10) и (11) различны по условию. Следовательно, пользуясь китай­
ской теоремой об о с т а т к а х , мы видим, ч т о для разрешимости (9) необходимо
и достаточно, ч т о б ы была разрешима система
А{Х = В{ (mod 2),
i=l,...,k.
Так как ац = 1, т о /Зц = 0 для г = 1,...,к,
Ai = 1 (mod 2), г = 1, . . ., к. Следовательно,
(12)
и числа Li нечётны. Значит,
(12) разрешима т о г д а и только
ЗАДАЧА ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В КОЛЬЦАХ ВЫЧЕТОВ
тогда, когда 58- = £"(1x100! 2), г = 1,...,к,
q
-
2
b ''
" ' з = (д^
теоремы.
)-
в>
= (—I)-
8,
где Е = 0 или Е = 1.
651
Далее,
(mod 9"'). Из э т о г о следует утверждение
•
З а м е ч а н и е . Если s из (1) удовлетворяет условиям теоремы 1 и элемент а
(mod s) имеет порядок A(s), т о разрешимость (3) легко проверяется (мы пред­
полагаем, ч т о разложения (1) и (2) известны нам и порядки элементов поэтому
можно быстро находить). Элементы максимального порядка можно с т р о и т ь с
помощью перебора и китайской теоремы об о с т а т к а х . Кроме т о г о , поскольку
на практике простые числа д8 можно с т р о и т ь т а к , ч т о б ы было известно пол­
ное разложение д8 — 1 на простые множители, т о мы можем з а д а в а т ь модуль s
т а к , ч т о б ы теорема 1 была применима для проверки разрешимости (3).
W г
Т е о р е м а 2. Пусть q\, . . ., q^ — р а з л и ч н ы е простые числа, д8 —1 = 2 Г | р-'3,
i =2
г = 1, . . ., к, где рц — нечётные простые числа. Пусть числа pij, j = 2, . . ., iu8,
г = 1, . . ., к, различны, s = q\ . . . q^, (b, s) = 1. Пусть t £ N, 1 <it <i k, a (mod g8)
имеет порядок g8- — 1 для i = 1, . . ., t и порядок (g8 — l ) / 2 для i = t + 1, . . ., k.
Уравнение (З) разрешимо тогда и только тогда, когда
b\
(
\ i\)
где (-) — символ
"
fb\
(
b \
\qtj'
\qt+ij
(b
"
\qk,
Лежандра.
З а м е ч а н и е . Определение и свойства символа Л е ж а н д р а можно найти в
[7, гл. 5].
Д о к а з а т е л ь с т в о . Из (4) и условия теоремы следует, ч т о числа А{ взаимно
просты с ip(qi) = qi — 1 для г = 1, . . ., t, а для г = t + 1, . . ., к А{ четны и взаимно
просты с (qi — 1)/2. Из леммы 3 получаем систему
AiX = Bi (mod 2),
Л'ж = Bi (mod p 8 / J ) ,
Она разрешима т о г д а и только тогда, когда разрешима система
AiX = 58- (mod 2),
х = Bi (mod 2),
58=0(mod2),
г = 1, . . ., к,
i=l,...,t,
i = t +
l,...,k.
При этом Bi четно т о г д а и только тогда, когда (—) = 1. Утверждение теоремы
теперь очевидно.
•
В теоремах 1 и 2 единственным общим делителем чисел д8 — 1 и qj — 1 при
i ф j является число 2. Э т о позволяет получить необходимые и достаточные
условия разрешимости (3).
652
О. Н. ВАСИЛЕНКО
Опишем теперь один метод проверки разрешимости (3), напоминающий
Полига-Хеллмана [4]. Предположим, ч т о в обозначениях (1)-(4) простые чи­
сла qi и rj2 таковы, ч т о для некоторого простого числа р оц = vp{qi — 1) J> l,
г = 1,2. Тогда в системе (9) будет присутствовать подсистема из двух урав­
нений
Ахх = Bi ( m o d » " 1 ) ,
v(13)
;
А2х = В2 (modp"2).
К а к проверить её совместность? Сначала надо найти величины А{ (mod ра').
Bi (mod ра'), г = 1,2. Из (4) следует, ч т о
(9U,_la
-13,-1
9
"•'
t 1;L
-'».-'
{q" ~
9i
(modg"'),
1,2.
±
(14)
W )B,
(mod о- •),
Если затабулировать значения (gq'
*>"• У (mod q"') при j = 0, . . -,ра' — 1,
г = 1, 2, т о по этой таблице можно найти значения А{ (mod pa'), Bi (mod ра').
Э т о позволит з а т е м решить систему (13) и, следовательно, убедиться в её
разрешимости. Такая проверка разрешимости (13) займёт мало времени, если
значения р"', i = 1,2, невелики. Таким образом, если в (3) степени общих
простых делителей чисел д8- — 1 невелики, т о проверка разрешимости (3) может
б ы т ь проведена достаточно быстро.
Возможность быстрой проверки разрешимости (3) может б ы т ь использо­
вана в к р и п т о г р а ф и и . Для пары чисел а, Ь разрешимость или неразреши­
мость (3) составляет один бит информации. Если м ы хотим построить пару
а, Ь, для которой (3) неразрешимо, т о следует в ы б р а т ь такое а, ч т о Li = ord(a
(mod q™')), i = 1,2, — достаточно большие чётные числа. Далее случайно
выбираем числа жг' (mod Li), i = 1,2, разной чётности и з а т е м строим такое
Ь (mod s), ч т о Ь = ах' (mod q™'), г = 1, 2. Для пары а, Ь т о г д а (3) неразреши­
мо, поскольку из Ь = ах (mod s) следует, ч т о ах = ах' (mod q"') для г = 1,2,
откуда х = ж j (mod Li), i = 1,2, ч т о невозможно в силу чётности Li и разной
чётности Xi. Построение пары а, Ь с разрешимым (3) т р у д а не представляет.
Предположим теперь, ч т о абонент получил пару а, Ь. Если он знает разло­
жения (1), (2) и если s и а удовлетворяют условиям теорем 1 или 2 или
метода, описанного после теоремы 2, т о проверка разрешимости (3) прово­
дится быстро. Если же s составное, но разложения (1) и (2) неизвестны, и
простые числа д8- достаточно велики, т о проверка разрешимости (3) является,
по-видимому, трудной задачей. Эвристически можно предположить, ч т о э т а
проверка по сложности сопоставима со сложностью задачи ф а к т о р и з а ц и и s и
задачи дискретного логарифмирования по простым модулям д8-. Аналогично,
построение пары а, Ь, для которой (3) неразрешимо, будет затруднительным
без знания (1) и (2). При фиксированном а случайное Ь будет д а в а т ь разре7
г-»
o r d ( a ( m o d s))
шимую пару а, о с вероятностью г = — s —Vr
^
X(s)
"• <J - 4 4 .
ЗАДАЧА ДИСКРЕТНОГО ЛОГАРИФМИРОВАНИЯ В КОЛЬЦАХ ВЫЧЕТОВ
653
Литература
[1] Cohen H. A course in c o m p u t a t i o n a l algebraic n u m b e r theory. — Berlin: Springer- Verlag, 1993.
[2] McCurley K. T h e discrete logarithm problem / / P r o c . of Symp. in Appl. M a t . —
1990. — Vol. 42. — P. 49-74.
[3] Odlyzko A. Discrete logarithms in finite fields a n d their cryptographic significance / /
Lect. Notes in C o m p u t . Sci. — 1985. — Vol. 209. — P. 224-314.
[4] Pohlig S. C , Hellman M. A n improved algorithm for c o m p u t i n g logarithms over G F ( p )
a n d its cryptographic significance / / I E E E T r a n s . Inf. Theory. — 1978. — Vol. 24. —
P. 106-110.
[5] Riesel H. Some soluble cases of t h e discrete logarithm problem / / B I T . — 1998. —
Vol 28. — P. 8 3 9 - 8 5 1 .
[6] Schirokauer O., Weber D., Denny T . Discrete logarithms: t h e effectiveness of t h e index
calculus m e t h o d / / Lect. Notes in C o m p u t . Sci. — 1996. — Vol. 1122. — P. 337-362.
[7] В и н о г р а д о в И. М. Основы т е о р и и чисел. — М.: Наука, 1972.
Статья поступила в редакцию
в апреле 1998 г.