@Proshka17

Количество закрытых ключей (криптография)?

Добрый день!
Есть задачка на программирование:
Зыкрытый ключ задается как (p,q)
Необходимо определить количество подходящих открытых ключей.
Никак не могу придумать алгоритм перебора
  • Вопрос задан
  • 227 просмотров
Решения вопроса 1
@Mercury13
Программист на «си с крестами» и не только
Разложим НОД и НОК на простые множители.
Для каждого простого определим степень в НОД и НОК.

Если хоть для одного простого a p[НОД,a] > p[НОК,a], STOP: 0.
[ПРИМЕР: НОД=2, НОК=5 — ну не бывает такого, правда? А не бывает из-за того, что в НОД 2¹, а в НОК 20.]

Теперь возьмём другой пример: в НОД 2¹, в НОК 2³. Это значит, в одном числе будет 2¹, в другом 2³ — два варианта.

Итого ответ: 0, если хотя бы для одного простого a будет p[НОК,а] < p[НОД,a]
Иначе 2^{КОЛИЧЕСТВО{простых a} ( p[НОК,а] > p[НОД,a] )}

ПРИМЕР: НОД = 2¹·30·5² = 50, НОК = 2³·3¹·5² = 600
1-2. 1-0-2 = 50, 3-1-2 = 600 и 600-50
3-4. 1-1-2 = 150, 3-0-2 = 200 и 200-150
Правильно, четыре штуки?

UPD. Для большей скорости можно разобрать на простые множители НОК, а в НОД просто проверить то, что получилось: нет ли степени выше, нет ли посторонних простых.
Ну и, конечно, очень крайние случаи: НОД=НОК → 1 штука, НОД>НОК → 0 штук
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы