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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

Глава 3. Эллиптические кривые 97
определяется коэффициентами a и b кривой. К сожалению, нет никакого
регулярного способа выбрать кривую с наименьшим значением максимальной
степени делителя #EC(F
p
).
Пример 2. Рассмотрим простое число p = 1007 и вычислим
наименьшие значения границ B
1
, B
2
для каждого целого числа k из
интервала [1001, 1013], окружающего p. Получим:
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
почти всегда очень большая.
Поэтому процедуру факторизации на ЭК следует всегда
выполнять одновременно с несколькими различными кривыми. На
сайте http://alpertron.com.ar/ECM.HTM приведены оценки для значения
параметра B
1
и рекомендуемое число кривых в зависимости от размерности
наименьшего делителя факторизуемого числа n:
Глава 3. Эллиптические кривые                                                                     97

определяется коэффициентами a и b кривой. К сожалению, нет никакого
регулярного способа выбрать кривую с наименьшим значением максимальной
степени делителя #EC(Fp ).

       Пример 2. Рассмотрим простое число p = 1007 и вычислим
наименьшие значения границ B1 , B2 для каждого целого числа k из
интервала [1001, 1013], окружающего p. Получим:
 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
почти всегда очень большая.
       Поэтому       процедуру          факторизации          на       ЭК       следует        всегда
выполнять      одновременно        с     несколькими     различными              кривыми.         На
сайте http://alpertron.com.ar/ECM.HTM приведены оценки для значения
параметра B1 и рекомендуемое число кривых в зависимости от размерности
наименьшего делителя факторизуемого числа n:

Страницы