Метод спуску Вейля

6. Метод спуску Вейля

Заснована на методі спуску Вейля атака називається - атакою.

Нехай несуперсингулярна крива  визначена над композиційним полем  з непростим розширенням. Позначимо ,,  ( мале поле, - розширення поля ). Тоді

Припустимо, що виконується хоча б одна з умов:

1. - непарне число;

2. ;

3.  Тут  - ²магічне число², певне в працях А Менезиса, М.Ку, Гаудрі, Хасе й Смарта. Воно визначає рід  якоїсь гіпереліптичної кривої  -атака пропонує використати метод спуску Вейля для зведення на кривій  до  якобіану  гіпереліптичної кривої  роду  над полем

Порядок підгрупи якобіану  може виявитися більше порядку  поля  кривої  але для групи  існують субекспоненціальні алгоритми розв’язання

За допомогою алгоритму Кантора  у підгрупі  може бути вирішена за  групових операцій. При практичній реалізації для  часто залучаються такі три методи:

1. - метод Полларда зі складністю  бітових операцій.

2. Метод Енге-Гаудрі, що має субекспоненційну обчислювальну складність

3. Алгоритм Гаудри, який оцінюється складністю

 бітових операцій.

Алгоритм Гаудрі швидше, ніж алгоритм Полларда, якщо  У зв'язку зі швидким зростанням співмножника  цей алгоритм стає непрактичним при . У цьому випадку доцільно використати метод Енге-Гаудрі. Він вважається прийнятним при .

 атака вважається успішною, якщо рід  гіпереліптичної  кривої  малий настільки, що алгоритми 2 і 3 більш ефективні, ніж метод Полларда. Нехай, наприклад, крива  визначена над полем  й , , тоді . У випадку максимального значення  величина , тому очікується, що при  -атака для майже всіх кривих над полем  буде успішною. При  приходимо до якобіану  ізоморфної кривої  з експонентною складністю розв’язання .

Щоб уникнути атаки методом спуску Вейля, розширення  поля слід вибирати простим. При цьому  й , а рід  гіпереліптичної кривої  набагато перевищує граничне значення 1024. Практично у всіх сучасних стандартах  у цьому зв'язку рекомендується степінь поля  вибирати як просте число.