Оператор по модулю (%) дает разные результаты для разных версий .NET в C #

Я шифрую вводимые пользователем данные для генерации строки для пароля. Но строка кода дает разные результаты в разных версиях фреймворка. Частичный код со значением нажатой пользователем клавиши:

Нажатая клавиша: 1. Переменная ascii равна 49. Значения 'e' и 'n' после некоторого вычисления:

e = 103, 
n = 143,

Math.Pow(ascii, e) % n

Результат приведенного выше кода:

  • В .NET 3.5 (C #)

    Math.Pow(ascii, e) % n
    

    дает 9.0.

  • В .NET 4 (C #)

    Math.Pow(ascii, e) % n
    

    дает 77.0.

Math.Pow() дает правильный (одинаковый) результат в обеих версиях.

В чем причина и есть ли решение?

90 голосов | спросил 12 revs, 10 users 40%
Rajiv
1 Jam1000000amThu, 01 Jan 1970 03:00:00 +030070 1970, 03:00:00

5 ответов


0

Math.Pow работает с числами с плавающей запятой двойной точности; таким образом, вы не должны ожидать большего, чем первые 15–17 цифр результата будут точными:

  

Все числа с плавающей запятой также имеют ограниченное количество значащих цифр, что также определяет, насколько точно значение с плавающей запятой приближается к действительному числу. Значение Double может содержать до 15 десятичных знаков точности, хотя внутренне поддерживается максимум 17 цифр.

Однако по модулю арифметики все цифры должны быть точными. В вашем случае вы вычисляете 49 103 , чей результат состоит из 175 цифр, делая операцию по модулю бессмысленной в обоих ваших ответах.

Чтобы определить правильное значение, вы должны использовать арифметику произвольной точности, как указано в BigInteger (введено в .NET 4.0).

удар>

int val = (int)(BigInteger.Pow(49, 103) % 143);   // gives 114

Изменить . Как отметил Марк Питерс в комментариях ниже, вам следует использовать BigInteger.ModPow , который предназначен специально для этого вида операций:

int val = (int)BigInteger.ModPow(49, 103, 143);   // gives 114
ответил Douglas 31 Jpm1000000pmFri, 31 Jan 2014 18:03:35 +040014 2014, 18:03:35
0

Помимо того, что ваша хеширующая функция не очень хорошая * , самая большая проблема в вашем коде не в том, что он возвращает другое число в зависимости от версии .NET, а в том, что в обоих случаях он возвращает совершенно бессмысленное число: правильный ответ на проблему -

49 103 , mod 143 = равно 114. ( ссылка на Wolfram Alpha )

Вы можете использовать этот код для вычисления этого ответа:

private static int PowMod(int a, int b, int mod) {
    if (b == 0) {
        return 1;
    }
    var tmp = PowMod(a, b/2, mod);
    tmp *= tmp;
    if (b%2 != 0) {
        tmp *= a;
    }
    return tmp%mod;
}

Причина, по которой ваши вычисления дают другой результат, заключается в том, что для получения ответа вы используете промежуточное значение, которое сбрасывает большинство значащих цифр 49 103 числа: только первые 16 из его 175 цифр верны!

1230824813134842807283798520430636310264067713738977819859474030746648511411697029659004340261471771152928833391663821316264359104254030819694748088798262075483562075061997649

Все остальные 159 цифр неверны. Операция мода, однако, ищет результат, который требует, чтобы каждая отдельная цифра была правильной, включая самые последние. Таким образом, даже самое незначительное улучшение точности Math.Pow, которое могло быть реализовано в .NET 4, привело бы к резкому отличию вашего расчет, который по сути дает произвольный результат.

* Поскольку в этом вопросе говорится о повышении целых чисел до высоких степеней в контексте хеширования пароля, может быть очень хорошей идеей прочитать этот ответ link перед тем, как принять решение о том, следует ли изменить ваш текущий подход на потенциально лучший.

ответил dasblinkenlight 31 Jpm1000000pmFri, 31 Jan 2014 18:08:55 +040014 2014, 18:08:55
0

То, что вы видите - ошибка округления в два раза. Math.Pow работает с двойным, и разница как показано ниже:

.NET 2.0 и 3.5 => var powerResult = Math.Pow(ascii, e); возвращает:

1.2308248131348429E+174

.NET 4.0 и 4.5 => var powerResult = Math.Pow(ascii, e); возвращает:

1.2308248131348427E+174

Обратите внимание на последнюю цифру перед E, и это вызывает разницу в результате. Это не оператор модуля (%).

ответил Habib 31 Jpm1000000pmFri, 31 Jan 2014 18:04:09 +040014 2014, 18:04:09
0

Есть много ответов о том, как плохой код. Однако, почему результат отличается ...

Intel FPU использует формат 80-битный внутренне, чтобы получить больше точности для промежуточных результатов. Поэтому, если значение находится в регистре процессора, оно получает 80 битов, но когда оно записывается в стек, оно сохраняется в 64 битах .

Я ожидаю, что более новая версия .NET имеет лучший оптимизатор в своей компиляции Just in Time (JIT), поэтому она сохраняет значение в регистре, а не записывает его в стек, а затем читает его обратно из стека. .

Может случиться так, что JIT теперь может возвращать значение в регистре, а не в стеке. Или передайте значение в функцию MOD в регистре.

См. также вопрос переполнения стека Каковы применения /преимущества 80-разрядного типа данных с расширенной точностью?

Другие процессоры, например ARM даст разные результаты для этого кода.

ответил Joe 31 Jpm1000000pmFri, 31 Jan 2014 18:00:13 +040014 2014, 18:00:13
0

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

int n = 143;
int e = 103;
int result = 1;
int ascii = (int) 'a';

for (i = 0; i < e; ++i) 
    result = result * ascii % n;

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

ответил Ronald 31 Jpm1000000pmFri, 31 Jan 2014 18:08:36 +040014 2014, 18:08:36

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132