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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 94
k 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013
B
1
7 3 1 4 5 2 1 16 1 5 1 11 1
B
2
143 167 1003 251 67 503 1007 16 1009 101 1011 23 1013
Этот пример показывает, что факторизацию числа n, имеющего в
разложении множитель p = 1007, может выполнить при B
1
= B
2
= 16, а
может потребовать границы B
2
, сравнимой с числом 1007, в зависимости от
выбранной кривой. Отметим также, что границу B
1
в большинстве случаев
можно взять очень небольшой (наибольшее значение = 16), а граница B
2
почти всегда очень большая.
Поэтому процедуру факторизации на ЭК следует всегда выполнять
одновременно с несколькими различными кривыми.
Классический алгоритм Ленстры 1987 г. завершается в своей
первой стадии. Последующие улучшения этого алгоритма, выполненные
Монтгомери, Брентом и др., позволили решать задачу факторизации n даже
в случае, если порядок l содержит более одного множителя, превышающего
B
1
. Описание алгоритма Монтгомери для вычисления кратного точки ЭК
можно найти в книге Болотова и др. [61], а улучшения Монгомери к методу
Ленстры в статьях [36] и [37].
Оценка эффективности метода эллиптических кривых Ленстры
Пусть наименьший множитель числа n равен p. Тогда, время работы
алгоритма Ленстры можно оценить величиной
exp
√
2 + o(1)
p
ln p ln ln p)
, (3.67)
которая выполняется в случае, если граница B
1
выбрана близко к величине
exp
√
2/2 + o(1)
p
ln p ln ln p)
.
Поскольку значение множителя p неизвестно, то выбор значения B
1
выполняется эмпирически, что несколько ухудшает практическую оценку
сходимости метода Ленстры. Отметим, что добавление в алгоритм Ленстры
второй стадии вычислений сохраняет общую асимптотическую оценку,
Глава 3. Эллиптические кривые                                                     94

 k    1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013
 B1    7    3      1     4     5    2      1     16    1     5      1     11      1
 B2   143   167   1003   251   67   503   1007   16   1009   101   1011   23    1013


       Этот пример показывает, что факторизацию числа n, имеющего в
разложении множитель p = 1007, может выполнить при B1 = B2 = 16, а
может потребовать границы B2 , сравнимой с числом 1007, в зависимости от
выбранной кривой. Отметим также, что границу B1 в большинстве случаев
можно взять очень небольшой (наибольшее значение = 16), а граница B2
почти всегда очень большая.
       Поэтому процедуру факторизации на ЭК следует всегда выполнять
одновременно с несколькими различными кривыми.
       Классический алгоритм Ленстры 1987 г. завершается в своей
первой стадии. Последующие улучшения этого алгоритма, выполненные
Монтгомери, Брентом и др., позволили решать задачу факторизации n даже
в случае, если порядок l содержит более одного множителя, превышающего
B1 . Описание алгоритма Монтгомери для вычисления кратного точки ЭК
можно найти в книге Болотова и др. [61], а улучшения Монгомери к методу
Ленстры в статьях [36] и [37].

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

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

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

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

Страницы