Математические основы защиты информации. Ишмухаметов Ш.Т - 95 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 3. Эллиптические кривые 96
Анализ метода Ленстры
Проведем теперь анализ метода Ленстры и оценим условия, при которых он
будет успешно завершен. До сих пор все вычисления проводились по модулю
числа n, однако, если координаты полученных точек вычислять по модулю p,
являющегося делителем n, тогда условием успешного завершения алгоритма
будет, очевидно, условие
kP = ∞, где k =
∏
p
a
i
i
≤B
1
p
a
i
i
, (5.57)
и эллиптическая кривая y
2
= x
3
+ ax + b рассматривается в конечном поле
F
p
.
Пусть l = #E(F
p
) число точек этой кривой. По неравенству Хассe
l ∈ [p + 1 − 2
√
(p), p + 1 + 2
√
(p)]. Для любой точки Q(x, y) выполняется
условие lQ = ∞, поэтому, для того, что алгоритм Ленстры успешно
завершился, необходимо, чтобы множитель k в уравнении (5.57) делился на
порядок кривой l . Последнее условие будет выполнено, если все делители l
не превышают границы B
1
.
Дадим здесь определение гладкости целого числа (smoothness),
которое будет широко использоваться в последующих разделах. Пусть B
– некоторое положительное целое число. Произвольное целое число x
называется B – гладким, если все делители x по модулю не превышают
B . Например, x = 2
5
· 5 · 13
2
является B -гладким для любого B ≥ 13.
Это условие гладкости является более слабым, чем требуется в
алгоритме Ленстры. Для успешного завершения этого алгоритма необходимо,
чтобы все делители числа l вида p
r
, кроме последнего, были меньше границы
B
1
, а наибольший делитель p
r
имел степень r = 1 и был меньше границы
B
2
. Например, для #EC(F
p
) = 2
5
· 5 · 13
2
· 233 границы B
1
, B
2
должны
удовлетворять условиям B
1
≥ 13
2
= 169, B
2
≥ 233.
Число l, любой делитель которого вида p
r
, где p–простое число,
меньше границы B , называется B –гладкостепенным. .
Отметим, что необходимая граница для степеней делителей l
существенно зависит от значения #EC(F
p
), которое, в свою очередь,
Глава 3. Эллиптические кривые                                           96

          Анализ метода Ленстры

Проведем теперь анализ метода Ленстры и оценим условия, при которых он
будет успешно завершен. До сих пор все вычисления проводились по модулю
числа n, однако, если координаты полученных точек вычислять по модулю p,
являющегося делителем n, тогда условием успешного завершения алгоритма
будет, очевидно, условие
                                    ∏
                 kP = ∞, где k =              pai i ,               (5.57)
                                    a
                                   pi i ≤B1


и эллиптическая кривая y 2 = x3 + ax + b рассматривается в конечном поле
Fp .
       Пусть l = #E(Fp ) число точек этой кривой. По неравенству Хассe
              √              √
l ∈ [p + 1 − 2 (p), p + 1 + 2 (p)]. Для любой точки Q(x, y) выполняется
условие lQ = ∞, поэтому, для того, что алгоритм Ленстры успешно
завершился, необходимо, чтобы множитель k в уравнении (5.57) делился на
порядок кривой l . Последнее условие будет выполнено, если все делители l
не превышают границы B1 .
       Дадим здесь определение гладкости целого числа (smoothness),
которое будет широко использоваться в последующих разделах. Пусть B
– некоторое положительное целое число. Произвольное целое число x
называется B – гладким, если все делители x по модулю не превышают
B . Например, x = 25 · 5 · 132 является B -гладким для любого B ≥ 13.
       Это условие гладкости является более слабым, чем требуется в
алгоритме Ленстры. Для успешного завершения этого алгоритма необходимо,
чтобы все делители числа l вида pr , кроме последнего, были меньше границы
B1 , а наибольший делитель pr имел степень r = 1 и был меньше границы
B2 . Например, для #EC(Fp ) = 25 · 5 · 132 · 233 границы B1 , B2 должны
удовлетворять условиям B1 ≥ 132 = 169, B2 ≥ 233.
       Число l , любой делитель которого вида pr , где p–простое число,
меньше границы B , называется B –гладкостепенным. .
       Отметим, что необходимая граница для степеней делителей l
существенно зависит от значения #EC(Fp ), которое, в свою очередь,

Страницы