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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 98
N digits B
1
N curves
15 2000 25
20 11000 90
25 50000 300
30 250000 700
35 10
6
1800
40 3 · 10
6
5100
45 11 · 10
6
10 600
50 4, 3 · 10
7
19 300
55 1, 1 · 10
8
49 000
60 2, 6 · 10
8
124 000
65 8, 5 · 10
8
210 000
70 2, 9 · 10
9
340 000
Оценка эффективности метода эллиптических кривых Ленстры
Пусть наименьший множитель числа n равен p. Тогда, время работы
алгоритма Ленстры можно оценить величиной
exp
(
√
2 + o(1)
√
ln p ln ln p)
)
, (5.58)
которая выполняется в случае, если граница B
1
выбрана близко к величине
exp
(
√
2/2 + o(1)
√
ln p ln ln p)
)
.
Поскольку значение множителя p неизвестно, то выбор значения B
1
выполняется эмпирически, что несколько ухудшает практическую оценку
сходимости метода Ленстры. Отметим, что добавление в алгоритм Ленстры
второй стадии вычислений сохраняет общую асимптотическую оценку,
хотя обеспечивает большой практический прирост скорости сходимости
алгоритма.
5.6. Рекордные разложения метода ECFM
Если сравнивать метод эллиптических кривых с другими методами
факторизации, то ECFM относится к классу субэкспоненциальных методов
Глава 3. Эллиптические кривые                                       98

       N digits      B1        N curves
         15         2000         25
         20        11000         90
         25        50000         300
         30       250000         700
         35          106        1800
         40        3 · 106      5100
         45       11 · 106      10 600
         50       4, 3 · 107    19 300
         55       1, 1 · 108    49 000
         60       2, 6 · 108   124 000
         65       8, 5 · 108   210 000
         70       2, 9 · 109   340 000

Оценка эффективности метода эллиптических кривых Ленстры

     Пусть наименьший множитель числа n равен p. Тогда, время работы
алгоритма Ленстры можно оценить величиной
                        (√         √             )
                    exp    2 + o(1) ln p ln ln p) ,              (5.58)

которая выполняется в случае, если граница B1 выбрана близко к величине
                        (√           √             )
                    exp    2/2 + o(1) ln p ln ln p) .

Поскольку значение множителя p неизвестно, то выбор значения B1
выполняется эмпирически, что несколько ухудшает практическую оценку
сходимости метода Ленстры. Отметим, что добавление в алгоритм Ленстры
второй стадии вычислений сохраняет общую асимптотическую оценку,
хотя обеспечивает большой практический прирост скорости сходимости
алгоритма.


5.6. Рекордные разложения метода ECFM
Если сравнивать метод эллиптических кривых с другими методами
факторизации, то ECFM относится к классу субэкспоненциальных методов

Страницы