символом Лежандра, легко вказати формулу для числа точок на кривій Y 2 = f (X) над полем GF (p) , p> 2 (поля великих характеристик). Дійсно, порівняння Y 2 = f (X) (mod p) щодо Y при фіксованому X має (при p> 2 ) 1 + рішень (це вірно і при f (x) = 0 ). Враховуючи нескінченно віддалену точку, отримуємо формулу для порядку кривої над полем GF (p) , p > 2 у вигляді
В
При малих простих p , користуючись цією формулою і теорією квадратичних лишків порядок кривої над полем GF (p) знаходиться досить легко. Але обчислення порядку еліптичної кривої не завжди просто і навіть можливо. Загальна формула для обчислення порядку довільній кривій невідома. Невідомо навіть, чи можна за поліноміальний час знайти криву даного порядку. Проте, відомі способи вибору еліптичних кривих над кінцевими полями, що допускають просте визначення порядку. Ці способи важливі, тому що в криптографическом відношенні корисними є еліптичні криві, порядок яких містить великі прості множники. Для кривих, у яких порядок є гладким числом (тобто розкладається тільки на малі прості) проблема дискретного логарифмування може бути вирішена порівняно швидко алгоритмом поліг-Хеллмана-Зильбера.
Алгоритми на еліптичних кривих
У цьому розділі представлені алгоритми, необхідні для реалізації криптографічних додатків на еліптичних кривих.
Діаграма, наведена нижче, показує, які модулі необхідно створити при реалізації алгоритму цифрового підпису на еліптичних кривих (ECDSA). У додатку даної роботи генерація випадкових чисел, модульні арифметика і операції над великими числами здійснюються стандартними засобами мови Java. Арифметика еліптичних кривих заснована на алгоритмах, наведених у цій главі. br/>В
Додавання точок еліптичної кривої
Відповідно до визначення операції додавання в групі точок еліптичної кривої загальна схема алгоритму складання точок P 1 = (x 1
