Материал: Лекция 2 Генерирование простых чисел [восстановлен]
Пример2 для 1-го случая. =3mod23, 23=4*5+3
Находим 324/4 = 36 mod 23 =16
r=+16, r=-16.2
Проверка =256mod23=3
Во втором случае задача усложняется.
Известен алгоритм решения задачи 
a mod p , если найдено некоторое другое число b GF(p), которое дает
|
b |
|
|
, т. е. b – невычет. |
|
|
|
= −1 |
|||
|
|||||
|
|
|
|
|
|
|
p |
|
|
||
Хотя сейчас не известен полиномиальный алгоритм, решающий задачу нахождения невычета, однако с вероятностью 50% при случайном выборе элемента b GF(p) будем попадать на невычет. Следовательно, несколько попыток случайного выбора b с высокой вероятностью даст невычет.
Имея в своем распоряжении метод генерирования невычетов b,
можно использовать следующую конструкцию для нахождения 
a mod p
[2, 3]: |
|
|
|
|
|
|
1) генерировать случайные числа |
b Z p , Z p ={0,1, 2, 3, , p −1} |
|||||
, до тех пор, пока b2 – 4a не окажется квадратичным невычетом по |
||||||
mod p, т.е. |
|
2 |
−4a |
|
|
|
|
b |
|
|
= −1 |
|
|
|
|
|
p |
|
|
|
|
|
|
|
|
||
|
2) |
найти |
r = x(p+1)2 |
mod(x2 |
−bx + a) , |
|
|
|
||
|
где (x2 |
−bx + a) |
- полином над полем |
GF(p) |
||||||
|
3) |
выдать ответ: r, -r – как решение задачи |
|
mod p . |
||||||
a |
||||||||||
|
|
|
|
|
mod p |
|
||||
|
|
Сложность нахождения |
|
a |
составляет |
|||||
|
|
битовых операций O((log p)3 ) |
|
|
|
|||||
|
Когда n составное число n = p q , нахождение |
a |
mod n |
является весьма |
|
трудной задачей, и до сих пор не известно ни одного полиномиально |
|||
|
сложного алгоритма ее решения, если p и q неизвестно. |
|
||
• |
Если p и q известны, то общий порядок такой. |
|
||
• |
1. сначала нужно найти решения уравнения по простым модулямp и q |
|||
|
(сомножителям n) |
|
||
2. затем, используя китайскую терему о остатках, получить решение систем урвынений .
(Нужно решить 4 системы из двух уравнений) и путем подстановки в исходное уравнение найти правильное решение.
Доказано, что по сложности эта задача нахождения вычета эквивалентна задаче факторизации чисел. Если p и q известны, то задача извлечения решается довольно просто по алгоритму, рассмотренному выше. Данный факт эффективно используется в криптосистемах с открытым ключом.
2. Генерирование простых чисел
В криптографии с открытым ключем необходимо уметь находить простые числа. Обычно эта задача решается в два этапа:
1) генерирование случайного или псевдослучайного (если число не является секретным ключом) числа, которое по размерности удовлетворяет предъявленным требованиям;
2) проверка, является ли выбранное нечетное число простым. Если является, то оно принимается. Если же это число не является простым, тогда нужно повторять эти этапы до появления успешного результата.
Возникает вопрос: сколько потребуется сделать попыток (в среднем) для генерирования простого числа заданной размерности?