+7(800)707-21-74
Бесплатно по России

Вычислительно сложные задачи по теории чисел: Учебное пособие

В наличии Цена за шт.

451

Количество
Купить

Акции и скидки Поделиться


  • Артикул:00166952
  • Автор: Гречников Е.А.
  • ISBN: 978-5-211-06342-6
  • Обложка: Твердый переплет
  • Издательство: МГУ (все книги издательства)
  • Город: Москва
  • Страниц: 312
  • Формат: 60x90/16 (~145х215 мм)
  • Год: 2012
  • Вес: 534 г
Развернуть ▼

В учебном пособии подробно рассматриваются четыре задачи, привлекающие внимание исследователей на протяжении последних десятилетий: разложение больших составных чисел на множители, дискретное логарифмирование в мультипликативной группе вычетов по простому модулю, решение больших разреженных систем линейных уравнений над конечными полями, вычисление ранга эллиптических кривых, определенных над полем рациональных чисел.
Наиболее быстрые алгоритмы решения первых двух задач основаны на так называемом алгоритме решета числового поля, сводящем их к решению больших разреженных систем линейных уравнений над конечными полями. Системы эти настолько велики, что к ним не применимы обычные алгоритмы решения. Используются специальные блочные итерационные алгоритмы.
Эта область прикладной теории чисел активно развивается во всем мире в связи с приложениями в криптографии. Из-за отсутствия нижних оценок сложности решения этих теоретико-числовых задач, единственным способом проверки надежности используемых криптографических алгоритмов служит их практическая проверка с использованием самых совершенных алгоритмов и наиболее мощной вычислительной техники.
Содержание
Предисловие
Часть I. Решение линейных систем уравнений
Введение
Глава 1. Скалярные алгоритмы и приближения Паде
1.1. Приближения Паде
1.1.1. Алгоритм Евклида
1.1.2. Подходящие дроби как решения систем линейных уравнений
1.1.3. Промежуточные дроби
1.1.4. Алгоритм Берлекемпа - Месси
1.2. Алгоритм Видемана
1.2.1. Алгоритм Видемана и приближения Паде
1.3. Алгоритм Ланцоша
1.3.1. Алгоритм Ланцоша и приближения Паде
1.3.2. Схема Горнера и ортогональные многочлены
Глава 2. Блочный алгоритм Видемана - Копперсмита
2.1. Описание алгоритма
2.2. Построение матричных приближений Паде
2.2.1. Приведенный базис
2.2.2. Сдвиг степеней
2.3. Вероятность получения ненулевого решения
2.3.1. Обзор многомерного случая
2.3.2. Одномерный случай
Глава 3. Параллельные алгоритмы Видемана и Ланцоша
3.1. Краткое описание алгоритмов
3.1.1. Алгоритм Видемана
3.1.2. Алгоритм Ланцоша
3.1.3. Блочные алгоритмы над полем GF(2)
3.1.4. Вычислительные вопросы
3.2. Последовательные версии алгоритмов
3.2.1. Алгоритмы Видемана
3.2.2. Алгоритмы Ланцоша
3.3. Параллельные версии алгоритмов
3.3.1. Параллельное умножение матрицы на вектор
3.3.2. Параллельный алгоритм Видемана
3.3.3. Параллельный алгоритм Ланцоша
3.4. Некоторые замечания
Часть II. Алгоритм просеивания и его применения
Введение
Глава 1. Разложение на множители больших чисел
1.1. Алгоритм факторизации методом решета числового поля
1.2. Порядок А и его свойства
1.2.1. Простые идеалы первой степени в кольце А
1.2.2. Показатели
1.2.3. Расширение идеалов кольца А
1.3. Оценка индекса порядка А
1.4. Обоснование алгоритма
1.5. Извлечение квадратного корня в поле алгебраических чисел
Глава 2. Алгоритм дискретного логарифмирования
2.1. λ-функции и виртуальные логарифмы
2.1.1. λ-функции
2.1.2. Чистая образующая главного идеала
2.1.3. Определение виртуального логарифма идеала
2.1.4. Основная теорема
2.2. Алгоритм дискретного логарифмирования методом решета числового поля
2.3. Комментарии и обоснование алгоритма
2.3.1. Разложение простых чисел в произведение простых идеалов
2.3.2. Уравнения системы
2.3.3. Вычисление индивидуальных логарифмов
Глава 3. Просеивание
3.1. Просеивание на решетках
Глава 4. Выбор многочленов
4.1. Характеристики многочленов
4.1.1. Размер многочлена
4.1.2. Гладкость многочлена
4.1.3. Фунции Мерфи Е и е
4.2. Классические алгоритмы
4.2.1. Разложение по основанию m
4.2.2. Алгоритм Монтгомери
4.3. Современные алгоритмы
4.3.1. Алгоритм Монтгомери - Мерфи
4.3.2. Алгоритм Кляйнюнга
4.3.3. Оптимизация многочленов
Часть III. Эллиптические кривые над полем рациональных чисел
Введение
Глава 1. Рациональные точки на эллиптических кривых
1.1. Основные определения
1.2. Точки кручения
1.3. Высоты и их свойства
1.4. Редукция по простому модулю
Глава 2. Нахождение ранга эллиптической кривой
2.1. Алгоритм Берча - Суиннертон - Дайера и его обоснование
2.2. Реализация алгоритма Берча - Суиннертона - Дайера
2.2.1. Отыскание 2- накрытий
2.2.2. Отбор неэквивалентных 2- накрытий
2.2.3. Поиск р-адических точек на 2- накрытиях
2.2.4. Поиск рациональных точек на 2- накрытиях и эллиптических кривых
Глава 3. Построение базиса группы рациональных точек
3.1. Общая схема алгоритма
3.2. Нахождение высот рациональных точек
3.2.1. Разложение канонической высоты в сумму локальных высот
3.2.2. Вычисление локальной высоты в архимедовом случае
3.2.3. Замена параметра
3.2.4. Оценка ошибки при вычислении локальной высоты
3.2.5. Вычисление локальной высоты в неархимедовом случае
3.3. Работа с 2- накрытиями
3.4. Факторгруппа E(Q)/2E(Q)
3.5. Оценка нижней границы высот рациональных точек
3.5.1. Вычисление эллиптических логарифмов
3.5.2. Вычисление суммы DЕ(n)
3.5.3. Вычисление константы α
3.5.4. Основной алгоритм
3.6. Выделение базиса из полного набора независимых точек
3.7. Поиск рациональных корней многочленов
Глава 4. Задача дискретного логарифмирования на эллиптической кривой
Введение
4.1. Обзор некоторых методов
4.2. Исчисление "xedni"
Список литературы

Оставьте отзыв о товаре
Рекомендуем
×

Журналы и бланки

БухгалтерияОхрана труда и техника безопасностиМЧСКадровая работа: Журналы, бланки, формыЖурналы, бланки, формы документов для органов прокуратуры и суда, минюста, пенитенциарной системыЖурналы, бланки, формы документов МВД РФКонструкторская, научно-техническая документацияЛесное хозяйствоПромышленностьГостиницы, общежития, хостелыСвязьЖурналы и бланки по экологииЖурналы и бланки, используемые в торговле, бытовом обслуживанииЖурналы по санитарии, проверкам СЭСЛифтыКомплекты документов и журналовНефтебазыБассейныГазовое хозяйство, газораспределительные системы, ГАЗПРОМЖКХЭксплуатация зданий и сооруженийЖурналы и бланки для нотариусов, юристов, адвокатовЖурналы и бланки для организаций пищевого производства, общепита и пищевых блоковЖурналы и бланки для организаций, занимающихся охраной объектов и частных лицЖурналы и бланки для ФТС РФ (таможни)Журналы для образовательных учрежденийЖурналы и бланки для армии, вооруженных силБанкиГеодезия, геологияГрузоподъемные механизмыДокументы, относящиеся к нескольким отраслямНефтепромысел, нефтепроводыДелопроизводствоЖурналы для медицинских учрежденийАЗС и АЗГСЭлектроустановкиТепловые энергоустановки, котельныеЭнергетикаШахты, рудники, метрополитены, подземные сооруженияТуризмДрагметаллыУчреждения культуры, библиотеки, музеиПсихологияПроверки и контроль госорганами, контролирующими организациямиРаботы с повышенной опасностьюПожарная безопасностьОбложки для журналов и удостоверенийАптекиТранспортРегулирование алкогольного рынкаАвтодороги, дорожное хозяйствоСамокопирующиеся бланкиСельское хозяйство, ветеринарияСкладСнегоплавильные пунктыСтройка, строительствоМетрологияКанатные дороги, фуникулерыКладбищаАрхивыАттракционыЖурналы для парикмахерских, салонов красоты, маникюрных, педикюрных кабинетов

Охрана труда

Удостоверения, Свидетельства

Зачетные книжки, студенческие билетыУдостоверения рабочих различных строительных специальностей

Членские книжки

ГК, ГСК, членские книжки, пропуска и пр.Садоводческие книжки, членские книжки СНТ

Печати и штампы

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

Книги

Нормативные правовые актыОбщественные и гуманитарные наукиРелигия. Оккультизм. ЭзотерикаОхрана труда, обеспечение безопасностиСанПины, СП, МУ, МР, ГНПодарочные книгиПутешествия. Отдых. Хобби. СпортНаука. Техника. МедицинаКосмосРостехнадзорДругоеИскусство. Культура. ФилологияКниги издательства "Комсомольская правда"Книги в электронном видеКомпьютеры и интернетБукинистическая литератураСНиП, СП, СО,СТО, РД, НП, ПБ, МДК, МДС, ВСНГОСТы, ОСТыЭнциклопедии, справочники, словариДомашний кругДетская литератураУчебный годСборники рецептур блюд для предприятий общественного питанияЭкономическая литератураХудожественная литература

Знаки безопасности, таблички, стенды

Вспомогательные знаки, таблички-наклейкиЗапрещающие знакиЗнаки для инвалидовЗнаки пожарной безопасностиЗнаки электробезопасностиИнформационные знаки для строительных площадокМедицинские и санитарные знакиПредписывающие знакиПредупреждающие знакиСтендыЗнаки для уборки и сбора мусораУказательные знакиЭвакуационные знакиЮмористические знакиЗнаки на автомобильНаклейки

Диски

Плакаты

Металлические изделия (металлическая мебель, конструкции, навесы)

Металлическая мебельМеталлические изделия для дачи и дома

Подарки нашим покупателям

Портреты знаменитых людей

Сувениры

Кружки для термопереносаБрелокиГудки и Рожки охотничьиСувениры, подарки для мужчинПредметы интерьераЗажигалкиПодарочные наборы игрБизнес сувениры, корпоративные подаркиГимн России. Эксклюзивное графическое оформление в багетном обрамлении

Товары для дома и офиса

Каски, защитные очки, маскиПланы эвакуацииСамоспасателиИндикаторы стерилизацииГрамоты и благодарностиСредства дезинфекцииФитолампы и прожекторыОгнетушителиКанцелярские товарыКухонные принадлежностиХозяйственные товарыЭлектроудлинители, тройники, катушкиКартонные коробкиЭлектроустановочные изделия

Товары для развития, игрушки

Бумажные модели

Юнармия

Погоны министерств и ведомств

Товары для здоровья, БАДы

Аюрведические товарыСредства гигиены, косметика из минералов Мертвого моря
;