ормальному базісі як найбільш складаний операцій. Це пріблізно на порядок збільшує ШВИДКІСТЬ Виконання операцій ділення на два в порівнянні з операцією подвоєння точки.
Розглянемо Можливі підході до розв'язання задач дискретного логарифма. Найбільш проста Ситуація вінікає для крівої
,
,
з коефіцієнтом, порядок Якої
максимально простим порядок досягається при. Покладемо, что, а генератор має порядок. У ціклічній групі ВСІ точки є точками подільності на два, відповідно до (4) їх-координати мают слід ї, отже, непарна Вагу при поданні в НБ. При діленні на два отрімуємо Дві точки, одна з якіх захи групі ї має порядок, а Інша Максимальний порядок
Смороду мают відповідно непарного ї Парний Вагу-координат и легко розрізнюються без множення на Вибір однієї Із точок (5) порядку здійснюється й достатньо просто. Оскількі в групі віпліває, что
В
то после множення візначається вага елемента або его слід. p> При (парна вага елемента) корістуються інша формула (5), у протилежних випадка - дерло формулою (5). Таким чином, ділення на два з Вибори точки порядком практично зводіться до двох множення у полі.
Відзначімо, что при послідовному діленні на два для половини всех кривих (з коефіцієнтом и порядком достатнім віявляється ЛИШЕ ОДНЕ множення в полі.
Для цього при шкірному діленні обчіслюється позбав розв'язання квадратного рівняння (4) i координата точки ділення. Нехай, и при послідовному діленні на два з Вибори точки Із групи одержуємо
.
Згідно з (5) (перша формула),. . . ,, Того підсумовуючі рівності
В
отрімуємо з урахуванням Першого ділення
(6)
де Кожне з РІШЕНЬ вібірається так, щоб віконувалася Умова тоб в НБ Вагу вектора булу непарний. p> Як видно, рекурентне обчислення за формулою (6) не вімагає обчислення координат та на шкірному кроці ділення, вместо неї слід позбав запам'ятати параметри й. За необхідності - координата обчіслюється як
Таким чином, відповідно до (6) алгоритм послідовного ділення на Дві точки Із групи вімагає позбав одного множення ЕЛЕМЕНТІВ у полі. Це чудова властівість Операції ділення на два можна вікорістаті з метою Збільшення продуктівності обчислень як при кріптоаналізі, так и при ШВИДКО експоненціюванні будь-якої точки Із групи. p> Если пріпустіті, что для будь-якої точки ми нашли способ визначення парності (непарності), то послідовна процедура віднімання ї ділення на два з Вибори точки Із групи за поліноміальній годину приведе нас до відомої точки. p> Значення у двійковому поданні візначається самою процедурою віднімання-ділення. Зрозуміло, что така функція Вже НЕ однобічна. Це питання поки залішається відкрітім и доводитися вірішуваті відомімі методами з експонентною складністю.
Для крівої з коефіцієнтом оптимальний порядок. При діленні на Дві точки Із групи, як й у попередня випадка, отрімуємо Дві точки порядком ї, однак обідві точки ділення парні й мают слід - координат (і, відповідно, парна вага в нормальному базісі). p> Візначіті, яка з них має порядок, можна Шляхом множення кожної з них на, но це вімагає більшіх обчислювальних витрат. Більш раціональне дворазове ділення на два, Яку в одній з Галузії дасть Дві точки порядком, смороду НЕ діляться на два ї мают координат та непарної ваги. Ця галузь відбраковується ї залішається точка Із групи
Приклад 1 . Розглянемо криве Коблиці над полем, яка має порядок. Всі точки з генератором наведено в табліці 1
Таблиця 1 - Координати точок крівої над полем
В В
5
29
13
16
20
30
10
4
9
23
0
В
9
7
22
7
5
19
30
29
10
28
_
В
12 P
13 P
14 P
15 P
16 P
17 p
18 P
19 P
20 P
21 P
22 P
В
8
Схожі реферати:
Реферат на тему: Визначення точки рівноваги прибутку і точки беззбитковості експлуатації вер ...Реферат на тему: Виконання операцій множення і ділення в ЕОМ Реферат на тему: Формування обчислювальних навичок табличного множення і діленняРеферат на тему: Особливості вивчення табличних випадків множення і ділення у початковій шко ...Реферат на тему: Моделювання в пакеті Model Vision Studium коливань матеріальної точки в пол ...
|
 Український реферат переглянуто разів: |  Коментарів до українського реферату: 0 |
|
|