Бэби-степ гигантский шаг

В теории групп , одном из разделов математики, гигантский шаг-шаг - это алгоритм встречи посередине для вычисления дискретного логарифма или порядка элемента в конечной абелевой группе, созданный Дэниелом Шэнксом . ^[1] Проблема дискретного журнала имеет фундаментальное значение для криптографии с открытым ключом .

Многие из наиболее часто используемых систем криптографии основаны на предположении, что дискретный журнал чрезвычайно сложно вычислить; чем сложнее, тем большую безопасность обеспечивает передача данных. Один из способов повысить сложность проблемы дискретного журнала - основать криптосистему на более крупной группе.

Теория [ править ]

Алгоритм основан на компромиссе между пространством и временем . Это довольно простая модификация пробного умножения, наивного метода нахождения дискретных логарифмов.

Для данной циклической группы порядка , генератора группы и элемента группы проблема состоит в том, чтобы найти такое целое число , что${\ displaystyle G}$${\ displaystyle n}$ ${\ displaystyle \ alpha}$${\ displaystyle \ beta}$${\ displaystyle x}$

${\ Displaystyle \ альфа ^ {х} = \ бета \ ,.}$

Алгоритм baby-step гигантский шаг основан на переписывании :${\ displaystyle x}$

${\ displaystyle x = im + j}$

${\ displaystyle m = \ left \ lceil {\ sqrt {n}} \ right \ rceil}$

${\ Displaystyle 0 \ Leq я <м}$

${\ Displaystyle 0 \ Leq J <м}$

Таким образом, мы имеем:

${\ Displaystyle \ альфа ^ {х} = \ бета \,}$

${\ Displaystyle \ альфа ^ {им + J} = \ бета \,}$

${\ Displaystyle \ альфа ^ {J} = \ бета \ влево (\ альфа ^ {- м} \ вправо) ^ {я} \,}$

Алгоритм предварительно вычисляет несколько значений . Затем он фиксирует и пробует значения в правой части приведенного выше сравнения способом пробного умножения. Он проверяет, выполняется ли сравнение для любого значения , используя предварительно вычисленные значения .${\ displaystyle \ alpha ^ {j}}$${\ displaystyle j}$${\ displaystyle m}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle \ alpha ^ {j}}$

Алгоритм [ править ]

Вход : Циклическая группа G порядка n , имеющая образующую α и элемент β .

Выход : удовлетворительное значение x .${\ Displaystyle \ альфа ^ {х} = \ бета}$

1. m ← Потолок ( √ n )
2. Для всех j, где 0 ≤ j < m :
   1. Вычислите α ^j и сохраните пару ( j , α ^j ) в таблице. (См. § Практика )
3. Вычислить α ^{- m} .
4. γ ← β . (положим γ = β )
5. Для всех i, где 0 ≤ i < m :
   1. Проверьте, является ли γ вторым компонентом ( α ^j ) любой пары в таблице.
   2. Если да, верните im + j .
   3. В противном случае γ ← γ • α ^{- m} .

Алгоритм C ++ (C ++ 17) [ править ]

#include  <cmath>#include  <cstdint>#include  <неупорядоченная_карта>std :: uint32_t  pow_m ( std :: uint32_t  base ,  std :: uint32_t  exp ,  std :: uint32_t  mod )  {  // модульное возведение в степень с использованием алгоритма умножения на квадрат }/// Вычисляет x так, чтобы g ^ x% mod == h std :: optional < std :: uint32_t >  babystep_giantstep ( std :: uint32_t  g ,  std :: uint32_t  h ,  std :: uint32_t  mod )  {  const  auto  m  =  static_cast < std :: uint32_t > ( std :: ceil ( std :: sqrt ( mod )));  автоматический  стол =  std :: unordered_map < std :: uint32_t ,  std :: uint32_t > {};  авто  е  =  std :: uint64_t { 1 };  // временные значения могут быть больше 32 бит  для  ( auto  i  =  std :: uint32_t { 0 };  i  <  m ;  ++ i )  {  table [ static_cast < std :: uint32_t >( е )]  =  я ;  е  =  ( e  *  g )  %  мод ;  }  const  auto  factor  =  pow_m ( g ,  mod - m -1 ,  mod );  е  =  ч ;  for  ( auto  i  =  std :: uint32_t {};  i  <  m ;  ++ i )  {  if  ( auto  it  = стол . найти ( static_cast < std :: uint32_t > ( e ));  это  ! =  таблица . end ())  {  return  { i * m  +  it -> second };  }  e  =  ( e  *  коэффициент )  %  mod ;  }  return  std :: nullopt ; }

На практике [ править ]

Лучший способ ускорить алгоритм гигантского шага младенца-шага - использовать эффективную схему поиска в таблице. Лучшее в этом случае - хеш-таблица . Хеширование выполняется на втором компоненте, и для выполнения проверки на шаге 1 основного цикла γ хешируется, а полученный адрес памяти проверяется. Поскольку хеш-таблицы могут извлекать и добавлять элементы во времени (постоянное время), это не замедляет общий алгоритм гигантских шагов маленького шага.${\ displaystyle O (1)}$

Время выполнения алгоритма и сложность пространства намного лучше, чем время выполнения наивного вычисления грубой силы.${\ displaystyle O ({\ sqrt {n}})}$${\ Displaystyle О (п)}$

Алгоритм гигантского шага Baby-step часто используется для поиска общего ключа при обмене ключами Диффи-Хеллмана , когда модуль представляет собой простое число. Если модуль не является простым, алгоритм Полига – Хеллмана имеет меньшую алгоритмическую сложность и решает ту же проблему.

Заметки [ править ]

• Алгоритм гигантских шагов baby-step - это общий алгоритм. Это работает для любой конечной циклической группы.
• Необязательно заранее знать порядок группы G. Алгоритм по-прежнему работает, если n - просто верхняя граница группового порядка.
• Обычно алгоритм гигантских шагов baby-step используется для групп с простым порядком. Если порядок группы составной, то алгоритм Полига – Хеллмана более эффективен.
• Алгоритм требует O ( m ) памяти. Можно использовать меньше памяти, выбрав меньшее m на первом шаге алгоритма. Это увеличивает время работы, которое затем составляет O ( n / m ). В качестве альтернативы можно использовать алгоритм ро Полларда для логарифмов , который имеет примерно такое же время работы, как и алгоритм гигантского шага маленького шага, но требует лишь небольшого объема памяти.
• В то время как этот алгоритм приписывается Дэниелу Шанксу, который опубликовал статью 1971 года, в которой он впервые появился, в статье Нечаева 1994 года ^[2] говорится, что он был известен Гельфонду в 1962 году.

Дальнейшее чтение [ править ]

• Х. Коэн , Курс вычислительной алгебраической теории чисел, Springer, 1996.
• Д. Шанкс , Число классов, теория факторизации и родов. В Proc. Symp. Чистая математика. 20, страницы 415—440. AMS, Провиденс, Род-Айленд, 1971.
• А. Штейн и Э. Теске, Оптимизированные методы шага младенца-гигантского шага, Журнал Математического общества Рамануджана 20 (2005), вып. 1, 1–32.
• А. В. Сазерленд , Вычисления порядка в общих группах , докторская диссертация, Массачусетский технологический институт, 2007.
• Д. С. Терр, Модификация алгоритма гигантских шагов Шанкса, «Математика вычислений» 69 (2000), 767–773. DOI : 10.1090 / S0025-5718-99-01141-2

Ссылки [ править ]

Внешние ссылки [ править ]

• Бэби-шаг-гигантский шаг - пример исходного кода на C