|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[7] называемые суммы Якоби. Сумма Якоби J{Xl;X2) = ~ Xl(z)X2(l - Х) определяется для двух характеров Xi-,X2 по модулю q. Если характеры имеют порядок р. то соответствующая сумма Якоби принадлежит кольцу Z[£jJ. Поскольку числа р. участвующие в алгоритме, сравнительно невелики, то вычисления с суммами Якоби производятся в полях существенно меньшей степени, чем вычисления с суммами Гаусса. Это главная причина, по которой суммы Якоби предпочтительнее для вычислений. При Х1Х2 ф Хо выполняется классическое соотношение связывающее суммы Гаусса с суммами Якоби и позволяющее переписать сравнение теоремы 3 в терминах сумм Якоби (см. [16]). Так. при р = 3 и q = 7 соответствующее сравнение, справедливое для простых N. отличных от 2. 3. 7. принимает вид В 1984 г. в работе [17] было внесено существенное усовершенствование в алгоритм, позволившее освободиться от требования неделимости чисел q - 1 на квадраты простых чисел. В результате, например, выбрав число Т = 24 • З2 5 • 7 = 5040 и взяв S равным произведению простых чисел q с условием, что Г делится на q - 1, получим S > 1.5 1052. что позволяет доказывать простоту чисел N. записываемых сотней десятичных знаков. При этом вычисления будут проводиться в полях, порождённых корнями из 1 степеней 16. 9. 5 и 7. Мой персональный компьютер с процессором Pentium-150. пользуясь реализацией этого алгоритма на языке UBASIC. доказал простоту записываемого 65 десятичными знаками, большего из простых чисел в примере Ривеста. Шамира и Адлемана (см. пункт 1) за 8 секунд. Сравнение этих 8 секунд и 17 лет. потребовавшихся для разложения на множители предложенного в примере числа, конечно, впечатляет. Отметим, что опенка сложности этого алгоритма представляет собой трудную задачу аналитической теории чисел. Как уже указывалось, количество операций оценивается величиной (In дг)с1п1п1пЛГ. Однако соответствующие числа S и Т. возникающие в процессе доказательства, не e2W3 и £ - некоторый корень кубический из 1. могут быть явно указаны в зависимости от n. Доказано лишь существование чисел 5 и Т. для которых достигается оценка. Впрочем, есть вероятностный вариант алгоритма, доказывающий простоту простого числа n с вероятностью большей 1 - 2~к за 0(/г(1п А)с1п1п1пЛГ) арифметических операций. А в предположении расширенной гипотезы Римана эта опенка сложности может быть получена при эффективно указанных S и Т. 6. Как раскладывают составные числа на множители Мы лишь кратко коснемся этой темы, отсылая читателей к книгам [7. 18. 19]. Среди многих алгоритмов разложения мы выберем ту линию развития, которая привела к разложению числа, предложенного RSA. Поиском эффективных способов разложения целых чисел на множители занимаются уже очень давно. Эта задача интересовала выдающихся учёных в области теории чисел. Вероятно Ферма был первый, кто предложил представить разлагаемое число n в виде разности квадратов n = х2 - у2, а затем, вычисляя (n.x - у), попытаться найти нетривиальный делитель n. Он же предложил и способ, позволяющий найти требуемое представление. Если разлагаемое число имеет два не очень отличающиеся по величине множителя, этот способ позволяет определить их быстрее, чем простой перебор делителей. Лежандр обратил внимание на то. что при таком подходе достаточно получить сравнение х2 = у2 (mod n).(17) Конечно, не каждая пара чисел, удовлетворяющих ему. позволяет разложить n на множители. Эйлер и Гаусс предложили некоторые способы нахождения чисел, связанных соотношением (17). Лежандр использовал для этой пели непрерывные дроби. Напомним, что каждому иррациональному числу £ может быть поставлена в соответствие бесконечная последовательность целых чисел [bo; Ь\, &2; • • •]; называемая его непрерывной дробью. Это сопоставление строится следующим образом хо = к = [xi]. xt+i = l h г = 0, 1, 2,.... Х{ Oi Лежандр доказал, что непрерывная дробь квадратичной иррациональности периодична. Если раскладывать в непрерывную дробь число £ = \/n, Vn + p- то возникающие в процессе разложения числа жг- имеют вид ж,- = --- с целыми Pi,Qi, причем всегда 0 Р,- < \/n. 0 < Qi < 2\/n. С каждой непрерывной дробью можно связать последовательность рациональных чисел, так называемых подходящих дробей. -. г 0. вычисляемых по правилам Ai+i = bi+iAi + Аг- 1,= bi+iBi +г 0. А0 = Ь0, В0 = A i = 1. B i = 0 и стремящихся к разлагаемому числу. Если в непрерывную дробь разлагается число £ = \/N~. то справедливо соотношение 42-i--i = (-i)U-(18) из которого следует = (-l)Q,- (mod TV).(19) Заметим, что длина периода разложения в непрерывную дробь числа £ = y/N может быть большой и достигать величин порядка \/N. В 1971 г. Шенкс предложил использовать сравнения (19) для конструирования чисел, удовлетворяющих (17). Если вычисления проводить до тех пор. пока при чётном г не получится Qi = R2 при некотором целом R. то пара чисел (A,- i.i?) будет удовлетворять (17) и с её помощью можно надеяться получить разложение N на простые множители. В 1975 г. Моррисон и Бриллхарт стали перемножать сравнения (19) при различных г с тем. чтобы таким способом получить квадрат целого числа в правой части. Этот метод, метод непрерывных дробей, позволил впервые разложить на множители седьмое число Ферма = 2128 + 1. Для реализации алгоритма выбирается так называемая база множителей {pi-P2.....Ps}- В неё входят ограниченные по величине некоторым пара- метром простые числа такие, что - =1. Последнее условие связано с тем. что. согласно (18). в разложение на простые множители чисел Qi могут входить лишь те простые, для которых N является квадратичным вычетом. На первом этапе алгоритма каждое очередное число Qi делится на все числа Р\.р2; - -.Ps и. если оно не разлагается полностью в произведение степеней этих простых, то отбрасывается. Иначе получается разложение (-1)д,- = (-1)аоПр?-(2°) Этому номеру г сопоставляется вектор (ао, а\..... as) (вектор показателей). Затем вычисляется следующее значение Qi+i-, и с ним проделывается в точности такая же процедура. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||