ВУЗ:
Составители:
182
элемент кривой Е (mod p)? Этот вопрос близок к следующему вопросу о
мультипликативных группах конечны: полей: пусть целое b фиксированно, а
простое р случайно; какова вероятность того, что b — образующий в
∗
p
F ? Вопрос
изучался как для конечных полей, так и для эллиптических кривых. Более
подробное изложение можно найти в работе Гулты (Gupta) и Мурти (Murty),
приведенной в списке литературы.
Описанные криптосистемы могут быть надежными, даже если точка В не
является порождающим элементом Фактически нужно, чтобы в циклической
группе, порождаемой В: задача дискретного логарифмирования не
была
эффективно разрешима. Это будет так (т.е. все известные методы решения
задачи дискретного логарифмирования в произвольной абелевой группе
оказываются слишком медленными), если порядок В делится на очень большое
простое число, скажем, имеющее порядок величины, близкий к N.
Один из способов гарантировать что наш выбор В является надлежащим (а
фактически, что
В порождает эллиптическую кривую) — это взять такую
эллиптическую кривую и такое конечное поле, чтобы число точек N было
простым чистом. Тогда всякая точка В
≠
О будет порождающим элементом.
Если использовать первый из описанных выше методов, то при фиксированном
p
F можно продолжать выбор пар (Е, В), пока не найдется такая, для которой
число точек на Е есть простое число (что можно определить одним из тестов на
простоту, обсуждавшихся в § V.1). Если применять второй метод, то для
фиксированной глобальной эллиптической кривой Е над Q можно продолжать
выбирать простые р, иона не найдем
кривую Е(mod p), число точек на которой
— простое. Как долго нам придется ждать? Этот вопрос аналогичен
следующему вопросу о группах
∗
p
F : является ли (р-1)/2 простым числом, т.е.
верно ли, что любой элемент, отличный от ±1, — либо порождающий, либо
квадрат порождающего элемента (см. упражнение 13 к §II.1)? Ни для
эллиптических кривых, ни для конечных полей вопрос дока не получил явного
ответа, однако в обоих случаях предполагается, что вероятность выбора р с
требующимся свойством есть O(1/
plog )
3аиечание. Для того чтобы Е(mod p) имела простой порядок N при
большом р, надо выбирать Е так, чтобы она имела тривиальное кручение, т.е.
чтобы на ней не было точек конечного порядка. кроме О. В противном случае N
будет делиться на порядок периодической подгруппы.
2.8.3. Примеры эллиптических кривых и
их применение
Пример. пусть р = 23. Рассмотрим эллиптическую кривую
1xxy
22
++= . В
Страницы
- « первая
- ‹ предыдущая
- …
- 180
- 181
- 182
- 183
- 184
- …
- следующая ›
- последняя »
