Можно ли получить исходное значение числа после нескольких умножений **с переполнением**?

Не знаю о части переполнения, но есть способ вернуть исходное значение.

Китайская теорема об остатках очень помогает. Давайте позвоним h = abcd - cd. G — это значение, h, без переполнения, G = h + k*2^32, при условии, что переполнение просто выполняет %2^32. И таким образом ab = G / p^2.

G = h (mod 2^32)
G = 0 (mod p^2)

Если p^2 и 2^32 взаимно просты. Эта страница, посвященная китайской теореме об остатках, дает нам

G = h * b * p^2 (mod 2^32 * p^2)

Где b — модульный мультипликатив, обратный p^2 по модулю 2^32, b * p^2 = 1 (mod 2^32). После того, как вы вычислите G, просто разделите на p^2, чтобы найти ab.

Надеюсь, я не допустил ошибок...

Расширенный алгоритм Евклида является хорошим решением для этого, но он слишком сложен и трудно реализуем. Есть лучше.

И есть еще один способ сделать это (спасибо моему другу (:)

В википедии есть хорошая статья - модульное мультипликативное обратное с использованием теоремы Эйлера в случае, когда m и a взаимно просты:

где φ(m) — это функция totient Эйлера.

В моем случае m (по модулю) - это размер типа хэша - 2^32, 2^64 и т. д. (64 бит в моем случае).
Это означает, что нам нужно найти только значение φ(m). Но подумайте об этом - m == 2 ^ 64 таким образом, это дает нам гарантию, что m будет взаимно простым со всеми нечетными числами и НЕ будет взаимно простым с любым четным числом. Итак, что нам нужно сделать, это получить количество всех значений и разделить их на 2.

Кроме того, мы знаем, что m не будет подписано, иначе у нас возникнут проблемы. Чем это дает нам возможность сделать это:

hash_t x = -1;
x /= 2;
hash_t a_reverse = fast_pow( a, x );

Ну, о 64-битных числах, x действительно большое число (19 цифр: 9 223 372 036 854 775 807), но fast_pow очень быстрое, и мы могли бы кэшировать обратное число, если нам нужно более одного запроса.

fast_pow — известный алгоритм:

hash_t fast_pow( hash_t source, hash_t pow )
{
    if( 0 == pow )
    {
        return 1;
    }

    if( 0 != pow % 2 )
    {
        return source * fast_pow( source, pow - 1 );
    }
    else
    {
        return fast_pow( source * source, pow / 2  );    
    }

}

Дополнение: например:

    hash_t base = 2305843009213693951;  // 9th mersenne prime
    hash_t x = 1234567890987654321;

    x *= fast_pow( base, 123456789 );   // x * ( base ^ 123456789 )

    hash_t y = -1;
    y /= 2;
    hash_t base_reverse = fast_pow( base, y );

    x *= fast_pow( base_reverse, 123456789 );   // x * ( base_reverse ^ 123456789 )
    assert( x == 1234567890987654321 ) ;

работает идеально и очень быстро.

Вы должны использовать целые числа без знака, чтобы получить определенное поведение переполнения (по модулю 2 ^ N). Переполнение целого числа со знаком не определено.

Кроме того, вместо деления вы должны умножить на мультипликативную обратную величину p по модулю соответствующего значения. Например, если p=3 и ваши хеш-значения 8-битные, умножьте на 171, потому что 171*3=513=2*256+1. Мультипликативная обратная существует, если p и значение по модулю взаимно просты.

Просто частичный побочный ответ здесь: я считаю, что нет строго необходимо использовать целые числа без знака. Вы можете использовать дополнение.

Но обратите внимание, что это будет иметь отдельное представление для -0 и +0, и что вам, вероятно, придется вручную кодировать арифметические операции по пути.

Некоторые инструкции процессора не зависят от целочисленного представления, но не все.

У вас есть * b = c mod 2 ^ 32 (или что-то еще, в зависимости от того, как вы делаете свой хэш). Если бы вы могли найти d такое, что b * d = 1 mod 2 ^ 32 (или любой другой мод), вы могли бы вычислить a * b * d = a и получить a. Если gcd(b, mod 2^32) = 1, вы можете использовать http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm, чтобы найти x и y, такие что b * x + 2^32 * y = 1, или b * x = 1 - y * 2^32, или b * x = 1 mod 2^ 32, значит, х — это число, на которое нужно умножить.

Таким образом, переполнение на самом деле просто ваш компилятор хорошо к вам относится; стандарт C/++ фактически предполагает, что переполнение является неопределенным поведением. Итак, как только вы переполнились, вы фактически ничего не можете сделать, потому что ваша программа перестает быть детерминированной.

Возможно, вам придется переосмыслить алгоритм или добавить операции по модулю/вычитания, чтобы исправить ваш алгоритм.