Переверните эту математическую функцию

Question

Мне нужно повернуть функцию с трудными математическими операциями, я прошу здесь проверить, возможно ли это, в конце концов, за помощью.

    public static UInt32 Func_4(UInt32 P, UInt32 X, UInt32 G)
    {
        UInt64 result = 1;
        UInt64 mult = G;
        if (X == 0)
            return 1;
        while (X != 0)
        {
            if ((X & 1) != 0)
                result = (mult * result) % P;
            X = X >> 1;
            mult = (mult * mult) % P;
        }
        return (UInt32)result;
    }

Под «реверсом» я имею в виду следующее: я знаю G, я знаю P, я знаю результат. Мне нужно X.

Я пытался перевести это снова этим утром, пока мой разум был чист, но я потерпел неудачу. Это вообще возможно?

Заранее спасибо.

Answer 1

Похоже, ваша функция Func_4() вычисляет G ^X mod P . То, что вы просите, - это решение проблемы дискретный логарифм , но эффективный алгоритм не известен.

Answer 2

хорошо

работает через это вручную для:

P = 5, X = 0b0000 1110, G = 7

P = 5, X = 0b0001 1110, G = 7

P = 5, X = 0b0011 1110, G = 7

P = 5, X = 0b0111 1110, G = 7

и т. Д., Я думаю, вы видите шаблон

у всех одинаковое возвращаемое значение для результата (4) ...

поэтому любая попытка изменить это, чтобы получить значение для X, будет иметь несколько возможных значений для X ..

в зависимости от того, что вам на самом деле нужно из этого, это может не иметь большого значения ...

каков контекст этой вещи?

Answer 3

Так как оператор по модулю находится в игре, вы можете сразу сказать, что функция не является биективной: для фиксированных P и G разные x могут возвращать один и тот же результат.

Но функция является биективной для ограниченной области x. Так же, как atan, asin, sqrt, .... выдают полный набор значений, когда вы ограничиваете домен, вы можете выбрать правильное.

На первый взгляд, функция, для очень большого P, это:

Произведение G ^{(2i * x [i])} , где x [i] - это i-й бит x (начиная с бита 0 как наименее значимого).

Это означает, что при большом значении P (больше, чем Prod (G ²ⁱ ), для x = 0x1111 ... 111), вы можете повернуть функцию вспять. Также кажется, что функция была разработана , чтобы не быть обратимой для меньших P.

Answer 4

Похоже, я = (г ** х) мод р. Это означает, что может быть более одного х

Answer 5

алгоритм псевдо

R = Pow (G, X) мод P

т.е.) существует один Q, который является R + P * Q = pow (G, X)

В обратном порядке, проверьте Y для всех Q от 0 до UINT32 ((MAXUINT32-R) / P),

Y = log (R + P * Q) / log (G)

и если значение Y не имеет дробей, то они являются множеством ответов "X" для вашей задачи.

Предположим, что X1 является первым значением X, которое не имеет дробей, а X2 является вторым значением X, которое не имеет дробей. Тогда множество всех X может быть задано в уравнении X (S) = X1 + (X2-X1) * S, где S = 0 до UINT32 ((MAXUINT32-X1) / (X2-X1)).

Это связано с тем, что если 1 = Pow (G, T) mod P, а затем Pow (G, X + T) mod P = Pow (G, X) mod P * Pow (G, T) mod P, который является также Pow (G, X) mod P. Следовательно, X, X + T, X + 2T, X + 3T ... все будут иметь одинаковые значения ..

Answer 6

Я серьезно думаю, что вы злоупотребляете этим алгоритмом. Из вашего описания и анализа алгоритма становится ясно, что он предназначен только для продвижения вперед. Думайте об этом как о вычислении контрольной суммы X с использованием ключей P и G.