Обратная операция умножения, переполненная

Question

Учитывая код:

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

Ввод значения 0x300 приводит к результату 0x69D04700.Это только младшие 32 бита результата.Учитывая результат 0x69D04700 и коэффициент 0x123456D, возможно ли получить все числа так, чтобы (значение * 0x123456D) & 0xFFFFFFFF = 0x69D04700 быстро?

Редактировать: код, который я показываю, является псевдокодом - я могутип возврата расширяется.

Answer 1

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

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

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

Answer 2

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

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.

---

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

Answer 3

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

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

Вы знаете, что

n = 0 (mod 0x123456D)

и

n = 0x69D04700 (mod 0x100000000)

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

n = 0x369D04700 (mod 0x123456D00000000)

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

Answer 4

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

Answer 5

Ну, вы можете построить длинные значения с нижней половиной, равной вашему результату, а верхней половиной = 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 бита.

Answer 6

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