Подъем решений показательных уравнений в конечных кольцах тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 511 225+511 23

Поповян Илья Ардашесович

ПОДЪЁМ РЕШЕНИЙ ПОКАЗАТЕЛЬНЫХ УРАВНЕНИЙ В КОНЕЧНЫХ КОЛЬЦАХ

01 01 06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 2007

ООЗОТ1758

003071758

Работа выполнена на кафедре теории чисел Механико-математического факультета Московского государственного университета имени М В Ломоносова

Научный руководитель. Официальные оппоненты:

Ведущая организация

кандидат физико-математических наук, доцент М А Черепнев

доктор физико-математических наук, профессор В Г Чирский, кандидат физико-математических наук, Е В Горбатов

Владимирский государственный педагогический университет

Защита диссертации состоится 18 мая 2007 г в 16 ч 15 мин на заседании диссертационного совета Д 501 001 84 в Московском государственном университете им M В Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ, Механико-математический факультет, ауд 14-08

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (главное здание МГУ, 14 этаж)

Автореферат разослан 18 апреля 2007 г

Ученый секретарь диссертационного совета Д 501 001 84 в МГУ профессор

В H Чубариков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

В современной криптографии важную роль играет понятие односторонней функции Односторонней называется такая вычислимая за полиномиальное время, то есть за время, равное многочлену от длины входа, функция, задача обращения которой неполиномиальна Согласно У Диффи1 в середине 70-х годов Дж Гилл предложил использовать в качестве одностороннего отображения возведение в степень по модулю простого числа Позже оно было обобщено до возведения в степень в произвольной конечной циклической группе, то есть если (G, х) - циклическая группа, G = < g >, то

Z G п H- gn

Задача обращения этого отображения называется (обобщенной) задачей дискретного логарифмирования (GDLP), а при G = (Z/(p))*, где р -простое рациональное число, эта задача называется просто задачей дискретного логарифлмрования (DLP) На ее предположительной неполи-номиальности основана стойкость многих асимметричных криптосхем, таких как, например, схема распределения ключей Диффи-Хэллмэна1 или схема электронной подписи Эль-Гамаля2 и ее варианты, DSA3 и ГОСТ-34 10-94

Естественным обобщением DLP является GDLP для G — (Z/(m))*, где m G Z - составное Задача полиномиального сведения GDLP в (Z/mZ)* к DLP в группах (Z/ptZ)*, соответствующих всем простым делителям рг числа m, решена Решение состоит в применении китайской теоремы об остатках для сведения задачи в (Z/mZ)* к задаче в (Z/pfcZ)*,pfc||m, и так называемого подъема решения

Подъемом решения в кольце целых рациональных чисел называется задача сведения GDLP в (Z/p^Z)* к DLP в (Z/pZ)* Одним из первых эту задачу в более общей постановке рассмотрел Г Ризель4 и предложил использовать для ее решения аппарат частных Ферма Свойства частных

!W Difiïe and M E Hellman, New Directions m Cryptography IEEE Tïansactions on Information Theory, Vol IT-22, No 6, November 1976, pp 644-654

2T ElGamal , A public key cryptosystem and a signature scheme based on discrete logarithms IEEE Transactions on Information Theory, Vol IT-31, No 4, July 1985, pp 469-472

3FIPS 186 , Digital signature standard Federal Information Processing Standards Publication 186, U S Department of Commerce/ N IS T , National Technical Information Service, Springfield, Virginia, 1994

4H Riesel, Some soluble cases of the discrete logarithm problem BIT, v28, no4, 1988

Ферма позволили ему свести задачу подъема решения к линейным сравнениям, и использовать решения последних для нахождения дискретных логарифмов в (Z/(m))* при некоторых значениях тп, в частности, при m — рк

В 2002 году вышла статья Ю В Нестеренко5, в которой он показал возможность использования р-адических логарифмов вместо частных Ферма для подъема решения в кольце Z, а также установил связь между этими функциями

Частные Ферма обладают следующим свойством их значения на первообразных корнях по модулю р не делятся на р Это свойство обеспечивает несократимость линейных сравнений, возникающих в процессе подъема решения, что, в свою очередь, позволяет эффективно их решать В работе M А Черепнева6 предложен способ модификации частного Ферма таким образом, чтобы указанное свойство выполнялось и для произвольного элемента g G (Z/pZ)*

Естественным теоретико-числовым обобщением задачи подъема решения показательного сравнения в Z является аналогичная задача с заменой кольца целых Z на кольцо целых Z^ какого-либо конечного расширения К поля Q

В 1979 году H Накагоши7 получил полное, хотя и не всегда конструктивное, описание мультипликативной группы (Zк/рм) , однако результат был малопригоден для практического применения Почти 20 лет спустя, в 1998 году, Г Коэн, Ф Диаз-и-Диаз и M Оливер8, работая над алгоритмами вычислений в теории полей классов, впервые дали конструктивное описание мультипликативного базиса группы (Z^/m)* по произвольному идеалу ш кольца Z к Рассматривая задачу нахождения представления произвольного элемента в заданном мультипликативном базисе группы (Z^-/m)*, они свели ее к аналогичной задаче в (Zk/PN) > где р - простой идеал, такой что р^Цгп Далее они заметили, что для решения последней, являющейся родственной задаче подъема решения, вполне естественно попытаться воспользоваться р-адическим логарифмом, и указали, что такой подход действительно срабатывает почти для

6Нестерекко Ю В , Частные Ферма и р -адические логарифмы "Труды по дискретной математике", т 5, M "Физматлит", 2002, с 173-188

еЧерепнев M А , О некотором свойстве дискретного логарифма Тез докл XII межд конф "Проблемы теоретической кибернетики" H Новгород, 1999

7Nakagoshi N , The structure of the multiplicative group of residue classes modulo Nagoya

Math J , Vol 73 (1979), 41-60

8 Cohen H , Diaz y Diaz F , Oliver M , Computing ray class groups, conductors and discriminants Math Comp , Vol 67 222, 1998, pp 773-795

всех идеалов Однако при большом значении параметра , гДе е _ индекс ветвления идеала р, а р - простое рациональное, такое что р|(р), применить р-адический логарифм не удается Поэтому вместо использования р -адического логарифма они предложили индуктивный метод, названный квадратичным, позволяющий за [log2 N] итераций получить представление произвольного элемента в заданном мультипликативном базисе уже для произвольного простого идеала р

Продолжая тематику, в 1999 году в своей книге9 Г Коэн предложил обобщить квадратичный метод при помощи так называемого логарифма Артина-Хассе Также он заметил, что для решения задачи нахождения представления произвольного элемента в заданном мультипликативном базисе группы () можно использовать комбинированный метод, совмещающий квадратичный метод и подход с р-адическим логарифмом, однако подробных решений не привел В 2003 году вышла статья Ф Гесса, Ч Паули и М Поста10, в которой указанный комбинированный метод был реализован, при этом были также получены оценки его сложности в терминах операций с матрицами и арифметических операций с алгебраическими числами в соответствующих факторах

В диссертации исследуется задача подъема решений показательных сравнений в кольцах целых произвольных конечных расширений поля рациональных чисел

Научная новизна работы.

Основные результаты диссертации являются новыми и состоят в следующем

1 Доказаны теоремы о подъеме решений показательных сравнений в кольцах целых алгебраических чисел, дающие новые явные формулы для вычисления решений с использованием логарифма Артина-Хассе и р -адического логарифма Получены формулы для эффективного вычисления логарифма Артина-Хассе и р-адического логарифма На основе этих результатов построен полиномиальный алгоритм подъема решений показательных сравнений в кольцах целых алгебраических чисел

2 Подсчитана функция Кармайкла для некоторых специальных групп, связанных с группой главных единиц кольца целых р-адического пополнения произвольного поля алгебраических чисел

3 Построены аналоги частных Ферма на подгруппах группы главных

9Cohen Н , Advanced Topics m Computational Number Theory GTM 193, Spnnger-NY, 1999

I0Hess F , Pauli S , Pohst M E , Computing the multiplicative group of residue class rings Math Comp , Vol 72 243, 2003, pp 1531-1548

единиц кольца целых р -адического пополнения произвольного поля алгебраических чисел, которые позволяют упростить процедуру подъема решений показательных сравнений в кольцах целых алгебраических чисел Получены формулы, связывающие построенные аналоги частных Ферма с логарифмом Артина-Хассе и р-адическим логарифмом, обобщающие полученные ранее формулы для целых рациональных аргументов

Цель работы.

1 Построить новый алгоритм подъема решений показательных сравнений в кольцах целых полей алгебраических чисел, оценить его эффективность

2 Оптимизировать выбор логарифмических функций, используемых для решения указанной задачи

Методы исследования.

Работа опирается на исследования в теории алгебраических чисел и р-адическом анализе, а также на теоретико-числовые алгоритмы Для исследования свойств р -адического логарифма, логарифма Артина-Хассе и оптимальных логарифмических функций, а также для вычисления порядков элементов применяются методы теории алгебраических чисел и р-адического анализа Для оценки сложностей предложенных алгоритмов - результаты теории сложности вычислений

Теоретическая и практическая ценность.

Работа носит теоретический характер Результаты диссертации могут найти применение в теории алгебраических чисел, р-адическом анализе и вычислительной теории чисел

Апробация работы.

Результаты диссертации докладывались на следующих семинарах и конференциях

1 Научно-исследовательский семинар по теории чисел под руководством Ю В Нестеренко и Н Г Мощевитина, механико-математический факультет МГУ (2003 г),

2 Семинар „Теоретико-числовые вопросы криптографии" под руководством М А Черепнева и Ю В Нестеренко, механико-математический факультет МГУ (2004-2006 гг)

3 Конференция „Математика и безопасность информационных технологий", МГУ (2003 г)

4 Конференция „Ломоносовские чтения", МГУ (2006 г)

5 Международная конференция „Диофантовы и аналитические проблемы теории чисел", МГУ (2007 г)

Публикации

Результаты диссертации опубликованы в двух работах автора [1-2], список которых приводится в конце автореферата Работ, написанных в соавторстве, нет

Структура и объем работы.

Диссертация изложена на 83 страницах Она состоит из введения, трех глав и списка литературы, включающего 36 наименований

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Пусть К - конечное расширение Q, Ъц ~ его кольцо целых Пусть также р - простой идеал Zк Рассмотрим показательное сравнение

ах = /3 mod pN, х е Z, (1)

где N G N\{1}, а,/3 Е %к\р Задача сведения нахождения решения сравнения (1) к нахождению решения сравнения

ах = (3 mod р, х G 2

называется задачей подъема решения показательного сравнения (1) в кольце Ък Решению этой задачи посвящена вторая глава диссертации В ней предложен алгоритм комбинированного типа с использованием логарифма Артина-Хассе и р -адического логарифма

Пусть идеал р лежит над р € Z и имеет индекс ветвления е и степень расширения /, то есть е € N ре||(р) и / 6 N : # р) = Pf Обозначим р = j^^yj +1 и пусть v обозначает р-адический показатель в Ък Зафиксируем также какой-либо элемент 7г £ Ък , такой что v(iv) = 1

Основной результат о подъеме решения разбивается на три случая и формулируется соответственно в одном утверждении и двух теоремах Первый, „вырожденный", случай состоит в том, что

vipP'-1 - 1) > N

Утверждение 2.1. Пусть а, @ £ %к\р, N £ N\{1} и а и(ар,~1 — 1) > N (допустимо а = оо) Тогда

х - д j jv ~ ^ / = 1 mod pN, or = р mod р , z £ Z < % _ . ^ ' ^ г ' [ ах = /3 mod р,х е Z

В следующей теореме рассматривается "низкий" случай, то есть

^(с/-1 - 1 )<N <р,

возникающий из-за того, что в Ък индекс ветвления е идеала р может быть больше р Для решения задачи подъема в этом случае используется специальная функция, логарифм Артина-Хассе, задаваемая многочленом

^ х*

.=1

Обладающий свойствами, аналогичными свойствам обычных логарифмов, логарифм Артина-Хассе позволяет в несколько этапов провести подъем решения сравнения (1)

Лемма 2.1. Пусть x,y,z £ х £ р, 1 < и{у) < u{z), тогда

I)

v{L{l + x)) = v{x)

Щ

¿((1 + у){ 1 + z)) = L{ 1 + у)+ L{ 1 + z) mod

Далее для у £ М скобки [у] обозначают верхнюю положительную целую часть, то есть при у Е Ж, у > 0 обозначим [у] £ N - минимальное, такое что \у] > у, а при у < 0 положим \у\ — О

Теорема 2 1. Пусть а,/3 £ %к\р, N £ {2, ,р}, а = ^(с/-1 -1)<М

ах =0 mod pN,xeZ t

' x = ylPl mod p\ уг 6 {0,1, ,p - 1}, (T1 1)

угЬ (aP'^-D) = L ^a-r-U^"1^ mod pait+\ (T1 2)

г = 0, , t — 2 при t > 2, yt_!L (a^-1^-1)) = Z, mod pN, (T1 3)

a'E^modp.iGZ (T14)

В следующей теореме рассматривается "высокий" случай, то есть

^{а?1-1 -1)<N, N> р.

Процедура подъема в этом случае состоит в использовании теоремы 2 1 при N = р для нахождения части решения и дополнительном однократном применении р-адического логарифма, определяемого на р-адическом пополнении Kv рядом

Logp(l + x) = jT(-l)n-i

п=1

х

П

Для 0 ф т] — 1 е р обозначим

где

г(т7) •= _ 1) _ .(/-^-Т1 _ 1} _ е.

Эти функции определяют мультипликативный порядок числа 77 в факторе {Ък/р"У

Теорема 2.2. Пусть а,(3 € %к\р, N <Е М, N > р, а = ~

ах = р mod pN,xeZ t

' X = у0 + ухр* mod Pt+R, у0, У1 е Z 0 < y0 <Pf',0< У\ < PR, (T2 1)

avo<j>>-i) = pV-i) mod (Tg 2)

yiLogp (aP'^-1^ = Logp ((/fcr*»)*"'-1)) mod тгл', (T2 3)

^ax = p modp,a:SZ (T2 4)

Третья глава диссертации посвящена формальному построению алгоритма подъема решения и другим вспомогательным вопросам, возникающим в связи с его вычислительной частью В частности, даются эффективные формулы для вычисления логарифма Артина-Хассе и р-адического логарифма Также приводится алгоритм решения линейного сравнения

mod г е Z,

возникающего в формулах (Т1 2),(Т1 3),(Т2 3)

В теоремах 2 1 и 2 2 используются логарифмические функции, вычисление значений которых по определениям представляется непрактичным В следущих двух утверждениях приводятся формулы, позволяющие вычислить эти функции за полиномиальное по р число умножений в кольце 7LK

Следущее утверждение дает простое тождество для логарифма Ар-тина-Хаесе

Утверждение 3 1 Пусть х - переменная, имеет место сравнение

L( 1 + х) = ------- mod ре

Р

Утверждение 3 2 дает полиномиально вычислимое р -адическое приближение для р -адического логарифма

Утверждение 3.2. Пусть Me N U {0},77 € Kv,u{jj] > р Тогда имеет место сравнение

(1 4- ' 1 - 1

Logp( 1 + г,)= ( -- mod

т>1 » I

где

при М > р,

сг='~

иначе

К1-{а})]

Наконец, проводится рассчет вычислительной сложности предлагаемого алгоритма подъема решения При получении оценок растущими параметрами считались лишь р и N

Теорема 3.5. Сложность алгоритма подъема решения равна Т — 0{\og3{pN) loglog(pJV))

В последней, четвертой, главе диссертации строятся новые логарифмические функции, применение которых приводит к нескратимости сравнений вида (Т1 2), (Т1 3) и (Т2 3)

Предложенные в первой главе функции, логарифм Артина-Хассе и р-адический логарифм, обладают неприятным свойством А именно, сравнения (Т1 2), (Т1 3) и (Т2 3) для любого элемента а являются сократимыми, то есть их левая часть содержится в идеале р В случае с частными Ферма этого эффекта можно было избежать используя их модификацию, предложенную М А Чбрепневым В связи с этим возникла задача построить логарифмические функции, пригодные к использованию для подъема решения вместо логарифма Артина-Хассе и р-адического логарифма, но не обладающие упомянутым свойством Такие функции были названы оптимальными логарифмическими функциями

Новые логарифмические функции строятся по аналогии с частными Ферма Для всех s G N рассмотрим множества

Us ={Ve Z„ 1/(17 - 1) > s}, и для М G N, т] G Us определим функции

VK(«M) _ 1

Qs,n"{v) =--м--(2)

где Xs(nM) - функция Кармайкла фактор-группы Us/Um > равная по определению НОК порядков образов элементов ц = 1 mod в (Ъ„/ъмУ

Затем доказываются утверждения об их свойствах Во-первых, показывается, что эти функции обладают логарифмическим свойством

Лемма 4.2 Пусть tj, £ £ Us, тогда

Qs,= Qs,*"(v) + mod ТГМ,

то есть отображение

Q,,«» -(Us, X)->(Z„/7TM,+) является гомоморфизмом

В лемме 4 3 вычисляются значения Xs(irM) для некоторых s, М € N

Лемма 4.3. Пусть s, N £ N

1 Если s > р, то

л .(*")= рГ*К!

2 Если s < р, то

В лемме 4 4 вычисляется период функций (2), что позволяет применять их к сравнениям

Лемма 4.4. Пусть s,N £ N

1 Пусть N > s > р, тогда при Д £ Uдг

Qs>7in(A) = 0 mod

2 Пусть s < р, тогда при А 6 Usp

Qs,^p(A) = 0 mod тгтш<е'5р>

Лемма 4 5 позволяет подобрать параметры таким образом, чтобы добиться оптимальности построенных функций

Лемма 4.5 Пусть s,N £ N, а г) £ Us\Cfs>+i, sf £ N,s' > s 1 Пусть s' > p, тогда

' N — s"

v {Q*,Mv)) = e 10

+ s' — N

2 Пусть s' < р, тогда s' < и

(a) Если s' < то у (Qs^'piv)) = ~ s)p

(b) Если s' то v (Qs,wr(v)) > (s' - s)p

В конце четвертой главы доказываются формулы, выражающие логарифм Артина-Хассе и р-адический логарифм через оптимальные логарифмические функции (2)

Утверждение 4 3. Пусть s G N, s < и г] G US\US+1, а

£ G <г}> С Us/Usp, тогда найдется la^tv{ri) G , такое что

"(h,*"(Tl)) — s>

и верна формула

т = Qs,MO l*Mv) mod

Утверждение 4.4. Пусть М G N U {0}, a rj Е Us, s G N, s > p Тогда

LogP(v) = —pсп-З .+.r¥l (V) mod

pi e I S.T 1 1

где

{p при M > p > 2,

2(1_{fi})] иначе

И наконец, формулируются теоремы 4 1 и 4 2, демонстрирующие возможность использования новых логарифмических функций для подъема решения

Теорема 4.1 Пусть а G ZK\p,/? е (а) С ZK/pN, N G N 1 < N < ^зу + 1 Пусть также а — v(ap/~1 — 1) < N, a t — [logp(^)] Тогда система сравнений

®,L(ap,(p'~1)) = Ц(рагЯ£mod

х, G Ъ 0 < хг < р,

7 = 0, ,t~ 1,

эквивалентна системе сравнений

= Qap^Wa-^'^-V) mod

X, G Z 0 < хг < р, г — 0, 1

Теорема 4.2 Пусть а, /3 G %к\р, N G N, N > р Обозначим а = i/(api(i>/~1) — 1), где t = |k>gp » и пУстъ а < 00

Предположим теперь, что & Ъ ■ 0 < xq < рг таково, что выполнено

cfoV-D = pip'-V mod

тогда сравнение

х Log^^-V) = Logpiifia-^-V) mod ttn, x G Z эквивалентно сравнению

^ = (((/За-^)^-1))) mod х G Z

Автор выражает глубокую благодарность своему научному руководителю, кандидату физико-математических наук, доценту Михаилу Алексеевичу Черепневу, за постановку задачи и постоянное внимание к работе

Автор благодарен заведующему кафедрой, члену-корреспонденту РАН, профессору Ю В Нестеренко, и всем сотрудникам кафедры теории чисел Механико-математического факультета МГУ за творческую обстановку и доброжелательное отношение

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Поповян И А Подъем решения показательного сравнения Матем заметки, т 80 (2006), № 1, с 76-86

[2] Поповян И А Оптимальные логарифмические функции для подъема решения показательного сравнения Диск матем , т 19 (2007), № 2, с 53-66

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова Подписано в печать /С ОЦ 07

Формат 60 х 90 1/16 Уел печ л 0,76

Тираж 100 экз Заказ 23

1 Введение

1.1 Подъём решения.

1.1.1 Случай целых рациональных чисел

1.1.2 Случай целых алгебраических чисел.

1.1.3 Другие группы.

1.2 Результаты диссертации.

1.2.1 Подъём решения.

1.2.2 Оптимизация подъёма решения.

2 Подъём решения

2.1 Обозначения и леммы.

2.2 Теоремы о подъёме решения

2.3 Случай делителей нуля.

3 Вычислительные вопросы

3.1 Вычисление логарифмов.

3.1.1 Вычисление логарифма Артина-Хассе.

3.1.2 Вычисление р-адического логарифма

3.2 Решение линейных сравнений.

3.3 Алгоритмы подъёма решения.

3.4 Оценки сложности.

4 Оптимальные логарифмические функции

4.1 Оптимальные логарифмические функции.

4.2 Функции (^»Р и логарифм Артина-Хассе.

4.3 Функции Qs^m и р-адический логарифм Литература

Глава

В современной криптографии важную роль играет понятие односторонней функции, то есть такой функции, которая вычислима за полиномиальное от длины входа время, но задача её обращения неполиномиальна. Согласно У. Диффи ([1]) в середине 70-х годов Дж. Гилл предложил использовать в качестве одностороннего отображения возведение в степень по модулю простого числа. Позже оно было обобщено до возведения в степень в произвольной конечной циклической группе, т.е. если (G, х) -циклическая группа, G =<д>, то

Задача обращения этого отображения называется (обобщенной) задачей дискретного логарифмирования (GDLP), а при G = (Z/(p))*, где р -простое рациональное число, эта задача называется просто задачей дискретного логарифмирования (DLP). На ее предположительной неполино-миальноети основана стойкость множества асимметричных криптосхем, таких как, например, схема распределения ключей Диффи-Хэллмэна [1] или схема электронной подписи Эль-Гамаля [2] и ее варианты, DS А [3] или ГОСТ-34.10-94.

История алгоритмов для решения DLP началась, конечно, с алгоритмов, имеющих в общем случае экспоненциальную сложность, таких как "Baby-Step, Giant-Step" Шенкса [4], р- и А-методы Полларда [5], алгоритм Полига-Хэллмэна [6] и др. Одним из первых субэкспоненциальный алгоритм для БЬР предложил Адлеман в [7], а в [8] было предложено уже три таких алгоритма. Позже для решения БЬР был адаптирован ([9]) и улучшен ([10]) алгоритм решета числового поля, используемый в то время для решения задачи разложения составного числа на множители. Упомянутые алгоритмы имели субэкспоненциальную оценку сложности, полученную лишь эвристически, пока в работе [11] она не была строго доказана. На сегодняшний день, все соврменные алгоритмы для решения задачи БЬР являются субэкспоненциальными.

Параллельно развивались алгоритмы для решения задачи СБЬР. Так в работе [12] был предложен субэкспоненциальный алгоритм для решения СБЬР в С = ¥рп. Этот алгоритм имел несколько улучшений, пока в частном случае С = F2m не был улучшен так сильно ([13],[14]), что стал на сегодняшний день алгоритмом, имеющим наилучшую оценку сложности из всех известных алгоритмов дискретного логарифмирования. В качестве С также рассматривалась группа точек на эллиптической кривой (на сегодня одно из перспективнейших направлений), группа классов идеалов конечного расширения и др.

Естественным обобщением БЬР является СЭЬР для С = (Ъ/{т))*, где т е Ъ - составное. Задача полиномиального сведения ОБЬР в (Z/mZ)+ к БЬР в группах (Ъ/р^Ъ)*, соответствующих всем простым делителям Рг числа ш, решена. Решение состоит в применении китайской теоремы об остатках для сведения задачи в (Ъ/тЪ)* к задаче в {Ъ/ркЪ)*, рк\\т, и так называемого подъёма решения.

1.1 Подъём решения

1. W. Diffie and M. E. Hellman New Directions in Cryptography, 1.EE Transactions on Information Theory, Vol. IT-22, № 6, November 1976, pp. 644-654.

2. T. ElGamal A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, Vol. IT-31, № 4, July 1985, pp. 469-472.

3. FIPS 186 Digital signature standard, Federal Information Processing Standards Publication 186, U.S. Department of Commerce/ N.I.S.T., National Technical Information Service, Springfield, Virginia, 1994.

4. D. Shanks Class number, a theory of factorization, and genera , Proc. Symp. Pure Math. 20 (1971), pp. 415-440.

5. J.M. Pollard Monte Carlo methods for index computation (mod p) , Math. Comp. 32(1978), № 143, pp. 918-924.

6. S.C. Pohlig, M.E. Hellman An improved algorithm for computing logarithms over GF(p) and its cryptographic significance, IEEE Transactions on Information Theory, 24 (1978), pp. 106-110.

7. L.M. Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, Proceedings of the IEEE 20th Annual Symposium on Foundations of Computer Science (1979), pp. 55-60.

8. D. Coppersmith, A.M. Odlyzko, R. Schroeppel, Discrete logarithms in GF(p), Algorithmica, 1 (1986), pp. 1-15/

9. C. Pomerance Fast, rigorous factorization and discrete logarithm algorithms, Discrete Algorithms and Complexity, Academic Press (1987), pp. 119-143.

10. M.E. Hellman, J.M. Reyneri Fast computation of discrete logarithms in GF(q), Advances in Cryptology- Proceedings of Crypto 82 (1983), pp. 3-13.

11. D. Coppersmith Fast evaluation of logarithms in fields of characteristic two, IEEE Transactions on Information Theory, 30 (1984), pp. 587-594.

12. A.M. Odlyzko Discrete logarithms in finite fields and their cryptographic significance, Advances in Cryptology-Proceedings of EUROCRYPT 84 (LNCS 209) (1985), pp. 224-314.

13. H. Riesel Some soluble cases of the discrete logarithm problem. BIT, 28 (1988), № 4.

14. Нестеренко Ю. В., Частные Ферма ир-адические логарифмы. "Труды по дискретной математике", М. "Физматлит"(2002), т. 5, сс. 173-188.

15. Черепнев М. А. О некотором свойстве дискретного логарифма. Тез. докл. XII межд. конф. "Проблемы теоретической кибернетики". Н. Новгород, 1999.

16. Боревич 3. И., Шафаревич И. Р. Теория чисел. М. "Наука", 1964.

17. Nakagoshi N. The structure of the multiplicative group of residue classes modulo Nagoya Math. J., Vol. 73 (1979), pp. 41-60.

18. Cohen H., Diaz у Diaz F., Oliver M. Computing ray class groups, conductors and discriminants. Math. Сотр., Vol. 67 (1998), № 222, pp. 773-795.

19. Cohen Н., Advanced Topics in Computational Number Theory. GTM 193, Springer-NY, 1999.

20. Hess F., Pauli S. , Pohst M. E. Computing the multiplicative group of residue class rings. Math. Сотр., Vol. 72 (2003), № 243, pp. 1531-1548.

21. Поповян И. А. Подъём решения показательного сравнения. Матем. заметки, т. 80 (2006), № 1, сс. 76-86.

22. Поповян И. А. Оптимальные логарифмические функции для подъёма решения показательного сравнения. Диск, матем., т. 19 (2007), № 2, сс. 53-66.

23. Василенко О. Н. О дискретном логарифмировании в некоторых группах. Вестн. Моск. ун-та. Сер. 1. Матем. Механ. (2000), №5, сс. 53—55.

24. Sauerberg J., Cohen L. S. D. Fermat Quotients over Function Fields. Finite Fiealds and Theier Applications, Vol. 3 (1997), №4, pp. 275-286.

25. Satoh K., Araki K. Fermat quotients and the polynomial time discrete log alogorithm for anomalous elliptic curve. Commentarii Math, Univ, Sancti Pauli, Vol.47 (1998), № 1, pp. 81-92.

26. Kunihiro N., Koyama K. Two discrete log algorithms for super-anomalous elliptic curves and their applications. IEICE Trans. Fundamentals, Vol. E83-A(2000), № 1.

27. Cepp Ж. П. Курс арифметики. M. "Мир", 1972.

28. Hasse Н. Zahlentheorie. Akademie-Verlag, Berlin, 2 Aufl., 1963.

29. Cohen HA Course In Computational Algebraic Number Theory. GTM, Springer-NY, 1993.

30. Виноградов И. M. Основы теории чисел. М. "Гос. Изд. Тех.-Теор. Литературы", 1953.

31. Artin Е., Tate J. Class Field Theory. NY, Amsterdam, Benjamin, 1967.

32. Pohst М. Е. Computational Algebraic Number Theory. Birkhauser, 1993.

33. Hafner J. L. , McCurley K. S. Asymptotically fast triangularization of matrices over rings., SIAM J. Comput. 20 (1991), pp. 1068-1083.

34. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., „Мир", 1979.