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

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

900

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

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


Развернуть ▼

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

Содержание
Часть 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. y-функции и виртуальные логарифмы
2.1.1. y-функции
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. Вычисление суммы De(n)
3.5.3. Вычисление константы а
3.5.4. Основной алгоритм
3.6. Выделение базиса из полного набора независимых точек
3.7. Поиск рациональных корней многочленов
Глава 4. Задача дискретного логарифмирования на эллиптической кривой
Введение
4.1. Обзор некоторых методов
4.2. Исчисление “xedni”
Список литературы


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

Диски

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

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

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

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

Календари

Книги

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

Курвиметры

Ленты с тиснением

Линейки

Авиационные и военные линейкиДетские линейкиМедицинские линейкиПортновские линейкиТехнические линейкиТрафареты с чертежными шрифтамиЧертежные линейки

Маркировочная продукция

Маркировка трубопровода "Вода"Маркировка трубопровода "Воздух"Маркировка трубопровода "Газ"Маркировка трубопровода "Жидкость"Маркировка трубопровода "Кислота"Маркировка трубопровода "Пар"Маркировка трубопровода "Прочие вещества"Маркировка трубопровода "Щелочь"

Материалы для типографии (мини-типографии)

Бумага для оргтехникиКлейПереплетные материалыПленка для печати и ламинацииФольга для тиснения

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

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

Носки и портянки

Одноразовая одежда

Охрана труда

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

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

Плакаты

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

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

Полотенца

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

Сувениры

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

Тир

Рогатки спортивные

Ткани

Товары "Юнармия"

Береты

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

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

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

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

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

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

Товары для спорта, туризма и охоты

Походные сумки, рюкзаки и мешочки для храненияСигнальное снаряжениеТовары для фитнеса

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

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

Упаковка, упаковочные материалы

Коробки картонные

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

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