Блог

Я реализую тест на простоту Миллера Рабина, используя JavaScript BigInts.

С базовым алгоритмом проблем нет — я уже это сделал, но для него требуется случайное число в диапазоне от 0 до (проверяемое число — 3). Я не могу использовать Math.random() и масштабировать, так как я использую BigInt.

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

Вот код:

 function getRandomBigint(lower, upper) {

    // Convert to hex strings so that we know how many digits to generate
    let hexDigits = new Array(upper.toString(16).length).fill('');
    let rand;
    let newDigits;
    do {
        // Fill the array with random hex digits and convert to a BigInt
        newDigits = hexDigits.map(()=>Math.floor(Math.random()*16).toString(16));
        rand = BigInt('0x' newDigits.join(''));
    } while (rand < lower || rand > upper);
    return rand;
}
 

Проблема здесь в том, что сгенерированное число может находиться вне диапазона. Эта функция обрабатывает это (плохо), повторяя до тех пор, пока не получит число в диапазоне. Очевидно, что это потенциально может занять очень много времени. На практике он никогда не повторялся более пары десятков раз, прежде чем выдать число, но природа случайности означает, что проблема «где-то там» ждет, чтобы укусить меня!

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

Итак, два вопроса:

• достаточно ли это случайности для Миллера Рабина?
• как работать с результатами вне диапазона?

Это проект только для JavaScript — никаких библиотек, пожалуйста.

Тест Миллера-Рабина — это вероятностный тест ¹. То есть это детерминировано для установления того, что число не является простым, но простым признаком является только это — указание на то, что число может быть простым.

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

Таким образом, выбранные случайные числа должны быть просто меньше тестируемого числа. Нет необходимости выбирать их из полного диапазона.

Имея это в виду, теперь у меня есть это:

 function getRandomBigInt(upper) {
    let maxInt = BigInt(Number.MAX_SAFE_INTEGER);
    if (upper <= maxInt) {
        return BigInt((Math.floor(Math.random()*Number(upper))));
    } else {
        return BigInt((Math.floor(Math.random()*Number.MAX_SAFE_INTEGER)));
    }

}
 

9007199254740991 ( Number.MAX_SAFE_INTEGER ) должен предоставлять достаточно большой диапазон чисел для этой цели. Он работает с моей реализацией Miller-Rabin, насколько я ее тестировал до сих пор.

¹ Тестирование чисел до 3,317,044,064,679,887,385,961,981 по короткому конкретному списку баз даст окончательный простой / не простой результат.

² Для недетерминированных простых результатов все равно необходимо выполнить детерминированный тест (например, разделение проб) для подтверждения.

Способ получить случайное число в диапазоне

   lower   rand() % (upper - lower)
 

rand() — это любая функция, которая возвращает случайное число, большее, чем (верхнее — нижнее). Математика может быть выполнена с помощью Integer или Bigint .

 function rand16() {
    // 0 .. 2^16-1
    return BigInt(Math.floor(Math.random()*65536));
}
function rand() {
   // -2^63 .. 2^63-1
   return BigInt( (((rand16() * 65536)   rand16())* 65536   rand16()) * 65536   rand16() );
}