В эллиптической криптографии необходимо находить «обратные числа по модулю» с помощью расширенного алгоритма евклида, а так же находить много остатков от деления. При этом, алгоритм евклида даёт в результате как отрицательные, так и положительные числа. Например, 3 mod 11. Обратным числом будет являться 4, так как 3 * 4 mod 11 = 1.
Но -1 — тоже правильный ответ, поскольку, 3 * (-1) = -3. А -3 mod 11 = 1. И такие вычисления там повсеместно.
Даже в сильно оптимизированном виде с минимизацией деления и прямого нахождения остатков — деление всё равно местами присутствует. Я лично наступал на грабли, связанные с вот этой разницей между остатком и модулем, когда разрабатывал быстрый алгоритм подписи 3410.
Но -1 — тоже правильный ответ, поскольку, 3 * (-1) = -3. А -3 mod 11 = 1. И такие вычисления там повсеместно.
Даже в сильно оптимизированном виде с минимизацией деления и прямого нахождения остатков — деление всё равно местами присутствует. Я лично наступал на грабли, связанные с вот этой разницей между остатком и модулем, когда разрабатывал быстрый алгоритм подписи 3410.