Держите подменю активным после наведения мыши

Теорема Габриэля Ламе ограничивает число шагов по log (1 / sqrt (5) * (a + 1/2)) - 2, где база журнала равна (1 + sqrt (5)) / 2. Это для наихудшего сценария для алгоритма, и это происходит, когда входы являются последовательными числами Фибанокси.

Немного более либеральная граница: log a, где база журнала (sqrt (2) )) подразумевается Коблицем.

Для криптографических целей мы обычно рассматриваем поразрядную сложность алгоритмов, принимая во внимание, что размер бита задан приблизительно на k = loga.

Здесь представляет собой подробный анализ поразрядной сложности алгоритма Евклида:

. Хотя в большинстве ссылок побитовая сложность алгоритма Евклида дается выражением O (loga) ^ 3, существует более жесткая оценка, которая является O (loga) ^ 2.

Рассмотрим; r0 = a, r1 = b, r0 = q1.r1 + r2. , , , ri-1 = qi.ri + ri + 1,. , , , rm-2 = qm-1.rm-1 + rm rm-1 = qm.rm

, заметим, что: a = r0> = b = r1> r2> r3 ...> rm-1 > rm> 0 .......... (1)

и rm - наибольший общий делитель a и b.

По заявлению в книге Коблица ( Курс в теории чисел и криптографии) можно доказать, что: ri + 1 & lt; (ri-1) / 2 ................. (2)

Опять же в Коблице число бит-операций, необходимых для деления k-битового положительного целого на 1-битовое положительное целое число (при условии k> = l), задается как: (k-l + 1) .l .... ............... (3)

В силу (1) и (2) количество дивизий равно O (loga), и поэтому (3) общая сумма сложность O (loga) ^ 3.

Теперь это может быть сведено к O (loga) ^ 2 замечанием в Koblitz.

рассмотрим ki = logri +1

в силу (1) и (2) имеем: ki + 1 & lt; = ki для i = 0,1, ..., m-2, m-1 и ki + 2 & lt; = (ki) -1 для i = 0,1, ..., m-2

и (3) общая стоимость m-дивизионов ограничена: SUM [(ki-1) - ((ki) - 1))] ki для i = 0,1,2, ..., m

, переставляя это: SUM [(ki-1) - ((ki) -1))] * ki = 4 * k0 ^ 2

Таким образом, побитовая сложность алгоритма Евклида равна O (loga) ^ 2.