Обратное умножение, выполнившее переполнение

Что вам нужно, так это модульное деление, которое можно вычислить с помощью версии алгоритма Евклида. В этом случае результат равен 768.

Это очень быстро -- время (log n)² даже для наивной реализации. (Если вам нужно работать с большими числами, я мог бы дать ссылки на лучшие алгоритмы.)

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

Если вы возьмете 0x100000000 и разделите его на 0x123456D, вы получите 224,9999 (десятичное число). Это говорит вам о том, что примерно через каждые 225 номеров вы будете набирать остаток. Конечно, поскольку это не совсем 225, вы не получите остаток с целыми числами. Как указал @Jacob, в 32-битном мире вы нажмете только одно значение (768 или 0x300). Таким образом, для этого конкретного теста ответ будет 2^32 * X + 768 для всех целых чисел X >= 0.

Что ж, вы можете построить длинные значения с меньшей половиной, равной вашему результату, и высокой половиной = 1,2,3,4,5..., разделить на ваш фиксированный множитель и посмотреть, получите ли вы результат без остатка. Возможно, это можно немного ускорить, поняв закономерности в числах, чтобы вы могли выбрасывать четные значения или что-то в этом роде.

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

Хорошо ...

Верни все обратно

import java.io.*;
public class multiply {
    public static void main(String[] argv) {
        long multiplier = 0x123456DL;
        // long result = 0x69D04700L;
        long result = (multiplier * 300L) & 0xFFFFFFFFL;
        System.out.println("New result = " + Long.toHexString(result));
        long offset = (multiplier * 300L) >> 32;
        System.out.println("New offset = " + offset);
        for (int i = 0; i < 30; i++) {
            long test = result + (((i * multiplier) + offset) << 32);
            long quotient = test / multiplier;
            long remainder = test % multiplier;
            System.out.println("Test: " + Long.toHexString(test) + " quotient: " + Long.toHexString(quotient) + " remainder: " + Long.toHexString(remainder));
        }
    }
}

Результаты (исправлено):

C:\JavaTools>java multiply
New result = 55555bbc
New offset = 1
Test: 155555bbc quotient: 12c remainder: 0
Test: 123456e55555bbc quotient: 10000012c remainder: 0
Test: 2468adb55555bbc quotient: 20000012c remainder: 0
Test: 369d04855555bbc quotient: 30000012c remainder: 0
Test: 48d15b555555bbc quotient: 40000012c remainder: 0
Test: 5b05b2255555bbc quotient: 50000012c remainder: 0
Test: 6d3a08f55555bbc quotient: 60000012c remainder: 0
Test: 7f6e5fc55555bbc quotient: 70000012c remainder: 0
Test: 91a2b6955555bbc quotient: 80000012c remainder: 0
Test: a3d70d655555bbc quotient: 90000012c remainder: 0
Test: b60b64355555bbc quotient: a0000012c remainder: 0
Test: c83fbb055555bbc quotient: b0000012c remainder: 0
Test: da7411d55555bbc quotient: c0000012c remainder: 0
Test: eca868a55555bbc quotient: d0000012c remainder: 0
Test: fedcbf755555bbc quotient: e0000012c remainder: 0
Test: 1111116455555bbc quotient: f0000012c remainder: 0
Test: 123456d155555bbc quotient: 100000012c remainder: 0
Test: 13579c3e55555bbc quotient: 110000012c remainder: 0
Test: 147ae1ab55555bbc quotient: 120000012c remainder: 0
Test: 159e271855555bbc quotient: 130000012c remainder: 0
Test: 16c16c8555555bbc quotient: 140000012c remainder: 0
Test: 17e4b1f255555bbc quotient: 150000012c remainder: 0
Test: 1907f75f55555bbc quotient: 160000012c remainder: 0
Test: 1a2b3ccc55555bbc quotient: 170000012c remainder: 0
Test: 1b4e823955555bbc quotient: 180000012c remainder: 0
Test: 1c71c7a655555bbc quotient: 190000012c remainder: 0
Test: 1d950d1355555bbc quotient: 1a0000012c remainder: 0
Test: 1eb8528055555bbc quotient: 1b0000012c remainder: 0
Test: 1fdb97ed55555bbc quotient: 1c0000012c remainder: 0
Test: 20fedd5a55555bbc quotient: 1d0000012c remainder: 0

Хорошо, я вижу, что частные (кроме первого) > 32 бита.

Да, это возможно.

Используйте китайскую теорему об остатках.

Ты знаешь что

n = 0 (mod 0x123456D)

а также

n = 0x69D04700 (mod 0x100000000)

Они относительно простые, так как 0x123456D нечетно, а «0x100000000» является степенью двойки. Таким образом, применяется китайская теорема об остатках, и она дает вам

n = 0x369D04700 (mod 0x123456D00000000)

Это говорит вам, что результаты без усечения равны 0x369D04700 + k * 0x123456D00000000. Разделив это на 0x123456D, вы получите 0x300 + k * 0x100000000.

Ваша функция:

uint Function(uint value)
{
  return value * 0x123456D;
}

умножается в uint (что работает точно так же, как целые числа по модулю 2**64 в так называемом unchecked контексте) на нечетное число. Такое нечетное число имеет уникальное обратное значение по модулю 2**64. В данном случае это 0xE2D68C65u, потому что, как вы можете проверить (синтаксис C#):

unchecked(0x123456Du * 0xE2D68C65u) == 1u

Это умножение ассоциативно и коммутативно. Итак, ваш «обратный» метод:

uint UndoFunction(uint value)
{
  return value * 0xE2D68C65u;
}

(подразумевается unckecked контекст).

Для любого ввода x и UndoFunction(Function(x)), и Function(UndoFunction(x)) возвращают исходное x.

ПС! Чтобы найти модульную инверсию 0xE2D68C65u, я использовал не .NET, а что-то другое. На самом деле GP/PARI нравится ответ Чарльза. В GP вы можете сделать 1/Mod(19088749, 2^32) или Mod(19088749, 2^32)^-1. По умолчанию используется десятичная запись.

Не с указанным вами типом возврата. Если вы хотите иметь возможность обрабатывать 64 бита, вы должны указать тип возвращаемого значения как ulong (или UInt64). C# использует строгую статическую типизацию в таких случаях и не будет автоматически "преобразовывать" значения, если результат не может быть сохранен в определенном типе. Даже если бы он преобразовывался с повышением, ему пришлось бы выполнить обратное приведение, чтобы обеспечить допустимый тип возвращаемого значения, потому что в иерархии наследования .NET UInt64 не является производным от UInt32.