Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[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-, и с ним проделывается в точности такая же процедура.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9]