Методи вирішення проблем дискретного логарифмування

height="26" align="BOTTOM" border="0" />

Таким чином, відповідно до (6) алгоритм послідовного ділення на дві точки із групи вимагає лише одного множення елементів у поле . Це чудова властивість операції ділення на два можна використати з метою збільшення продуктивності обчислень як при криптоаналізі, так і при швидкому експоненціюванні будь-якої точки із групи .

Якщо припустити, що для будь-якої точки ми знайшли спосіб визначення парності (непарності) , то послідовна процедура віднімання й ділення на два з вибором точки із групи за поліноміальний час приведе нас до відомої точки .

Значення у двійковому поданні визначається самою процедурою віднімання-ділення. Зрозуміло, що така функція вже не однобічна. Це питання поки залишається відкритим і доводиться вирішувати відомими методами з експонентною складністю.

Для кривої з коефіцієнтом оптимальний порядок . При діленні на дві точки із групи , як й у попередньому випадку, отримуємо дві точки порядку й , однак обидві точки ділення парні й мають слід - координат (і, відповідно, парна вага в нормальному базисі).

Визначити, яка з них має порядок , можна шляхом множення кожної з них на , але це вимагає більших обчислювальних витрат. Більш раціональне дворазове ділення на два, яке в одній з галузей дасть дві точки порядку , вони не діляться на два й мають координати непарної ваги. Ця галузь відбраковується й залишається точка із групи

Приклад 1. Розглянемо криву Коблиця над полем , яка має порядок . Всі точки з генератором наведено в таблиці 1

Таблиця 1- Координати точок кривої над полем

	5	29	13	16	20	30	10	4	9	23	0
	9	7	22	7	5	19	30	29	10	28	_
	12P	13P	14P	15P	16P	17p	18P	19P	20P	21P	22P
	8	22	27	21	1	11	15	18	2	26	_
	19	30	28	26	14	15	25	23	28	27	0
	23P	24P	25P	26P	27P	28P	29P	30P	31P	32P	33P
	26	2	18	15	11	1	21	27	22	8	0
	13	30	20	19	21	15	23	14	11	27	0
	34P	35P	36P	37P	38P	39P	40P	41P	42P	43P	44P
	23	9	4	10	30	20	16	13	29	5	*
	25	27	25	18	7	29	23	29	14	15	*

Приймемо

.

При діленні точки на два отримаємо дві точки

й .

Розглянемо всі операції при діленні точки відповідно до (3), (5) (друга з формул) в ОНБ із ізоморфізмом, тобто

, .

У нормальному базисі маємо . Розв’язуємо рівняння (3)

.

Відповідно до таблиці 2 , тоді одне з розв’язань для легко отримати, задаючи перший біт, скажімо, рівним 0.

Таблиця 2 - Елементи поля як степені елемента в ОНБ

0	00000	1	11111	-	-
	10000		00011		01101
	01000		10001		10110
	00100		11000		01011
	00010		01100		10101
	00001		00110		11010
	10010		10111		10011
	01001		11011		11001
	10100		11101		11100
	01010		11110		01110
	00101		01111		00111

При цьому інші біти визначаються із суми

, тобто

.

Друге розв’язання, мабуть, дорівнює . Легко перевірити, що отримані розв’язання задовольняють рівняння

.

Згідно з (5) (перша з формул) і даних таблиці 2 маємо

Отримано дві точки:

і .

Для визначення кожної необхідно виконати по два множення елементів поля. Неважко перевірити виконання умови

дискретне логарифмування метод

, ,

зокрема,

.

Обидві точки мають сліди

,

і, отже, діляться на два, але мають різні порядки. Точка має порядок 22, а точка - порядок Для визначення порядку достатньо виконати ще одне ділення на два. Якщо поділити точку, то отримаємо дві точки порядку 44, що не діляться на два (з непарною вагою x координат). При діленні точки отримаємо дві точки з порядками 22 й 11 (з парною вагою x координат).

Размещено на /