x-uni.com
регистрация / вход
сейчас на линии 65 чел.
x-uni.com
x-uni.com
 
Математика
Биология
Литература
Русский язык
ВИДЕО
Физика
Химия
История
Английский
 
ВИДЕО
 
 
регистрация / вход
сейчас на линии 65 чел.
Вычислительно сложные задачи теории чисел, Гречников Е.А., Михайлов С.В., Нестеренко Ю.В., 2012

Вычислительно сложные задачи теории чисел, Гречников Е.А., Михайлов С.В., Нестеренко Ю.В., 2012

Вычислительно сложные задачи теории чисел, Гречников Е.А., Михайлов С.В., Нестеренко Ю.В., 2012.

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

Параллельные версии алгоритмов.
Как можно заметить из оценок (3.5) и (3.6), на время работы алгоритмов влияют два основных фактора - сложность вычисления произведения матрицы на вектор и количество таких произведений, необходимое для срабатывания алгоритма.

Наиболее трудоемкими с вычислительной точки зрения операциями в обоих алгоритмах являются операции вычисления произведения матрицы на вектор и скалярного произведения векторов. Как уже упоминалось выше, в алгоритме Видемана можно избавиться от скалярного произведения векторов, взяв в качестве и блок единичных базисных векторов. В алгоритме Ланцоша наличие скалярного произведения векторов принципиально, и избавиться от него не удается.

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

Скачать бесплатно на сайте fileskachat.com
Скачать бесплатно на сайте yadi.sk

Предложения интернет-магазинов

Задачи в целых числах

Автор(ы): Далингер Виктор Алексеевич   Издательство: Илекса, 2013 г.

Цена: 126 руб.   Купить

В учебном пособии рассматриваются задачи, решаемые в целых числах: диофантовы уравнения; классические задачи, решаемые в целых числах; текстовые задачи, в которых неизвестные есть целые числа, и др. Учебное пособие рассчитано на учащихся и учителей математики средних общеобразовательных школ, гимназий, лицеев, ССУЗов, а также на студентов и преподавателей физико-математических специальностей педагогических институтов и университетов. Оно окажет помощь в организации соответствующего элективного курса для классов математического профиля и для подготовки к ЕГЭ (задачи С6). Учебное пособие будет полезно всем, кто интересуется математикой, в частности, проблемами теории чисел.


Математика. Теория вероятностей и дискретная математика: Элементы теории, решение задач

Автор(ы): Баюк Олег Александрович, Маркарян Елена Георгиевна   Издательство: Просвещение, 2013 г.  Серия: Сложные темы ЕГЭ

Цена: 333 руб.   Купить

Пособие предназначено учащимся общеобразовательных учреждений (школ, гимназий, колледжей) для углублённого изучения теории вероятностей и связанных с ней разделов дискретной математики (теории множеств, математической логики, комбинаторики, теории графов и математической статистики) в целях успешной сдачи ЕГЭ по математике. В пособии изложены основные теоретические сведения, необходимые для решения задач, приводятся решения типичных заданий ЕГЭ, а также содержатся задания для самостоятельной работы (с ответами, указаниями к решению или решениями). Книга может быть использована в качестве сборника задач на подготовительных курсах, факультативных занятиях, при самостоятельной подготовке к поступлению в вуз и при последующем обучении в вузе.


Математика. 3 класс. Рабочая тетрадь №1 учебнику М.И. Башмакова, М.Г. Нефедовой. ФГОС

Автор(ы): Башмаков Марк Иванович, Нефедова Маргарита Геннадьевна   Издательство: АСТ, 2015 г.  Серия: Планета знаний

Цена: 112 руб.   Купить

Тетрадь предназначена для работы в 3 классе по учебнику "Математика" (авт. М.И. Башмаков, М.Г. Нефедова) в 1-м полугодии. Задания разбиты на блоки, соответствующие разделам и темам учебника. Рабочие тетради построены в соответствии с учебником. Тетрадь содержит задания на повторение (вычисления в пределах 100, задачи на все арифметические действия), на отработку разрядного состава трехзначных чисел, устных вычислений в пределах 1000 (умножение и деление двузначного числа на однозначное, умножение и деление круглых чисел), письменных алгоритмов сложения и вычитания в пределах 1000. Рассматриваются новые типы текстовых задач: задачи на кратное сравнение, задачи с инверсией условия "это на (в) больше (меньше), чем...", задачи на определение длины пути, скорости, времени движения и другие. Приводятся тестовые задания с выбором ответа по основным учебным темам.


Задачи на смекалку. 5-6 классы. Пособие для учащихся общеобразовательных учреждений

Автор(ы): Шарыгин Игорь Федорович, Шевкин Александр Владимирович   Издательство: Просвещение, 2015 г.  Серия: Математика и информатика

Цена: 173 руб.   Купить

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

ПЕДСОВЕТ / ФОРУМ

Новости образования

Новости науки

флаг италииX-UNI рекомендует репетитора итальянского языка: yuliyavenezia (Скайп).

Репетитор по Скайпу без посредников

Неограниченная аудитория, свободный график. Начните свой бизнес здесь!