Estoy implementando una prueba de primalidad de Miller Rabin usando JavaScript BigInts.
El algoritmo básico no es un problema: lo tengo hecho, pero requiere un número aleatorio en el rango de 0 a (número que se está probando-3). No puedo usar Math.random() y escalar ya que estoy usando BigInt.
Esto no necesita ser criptográficamente seguro, solo lo suficientemente aleatorio, por lo que opté por generar una cadena de dígitos hexadecimales seleccionados al azar y convertirlos en BigInt.
Aquí está el código:
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; }El problema aquí es que el número generado podría estar fuera de rango. Esta función maneja eso (mal) iterando hasta que obtiene un número dentro del rango. Obviamente, eso podría llevar mucho tiempo. En la práctica, nunca ha iterado más de un par de docenas de veces antes de dar un número, pero la naturaleza de la aleatoriedad significa que el problema está 'ahí fuera' esperando morderme.
Podría escalar o truncar el resultado para ponerlo dentro del rango, en lugar de iterarlo, pero me preocupa que esto afecte la aleatoriedad. Ya tengo alguna evidencia de que esto no es tan aleatorio como podría ser, pero eso podría no importar en esta aplicación.
Entonces, dos preguntas:
Este es un proyecto solo de JavaScript; no hay bibliotecas, por favor.
La prueba de Miller Rabin es una prueba probabilística 1 . Es decir, es determinista para establecer que un número no es primo, pero una indicación prima es solo eso: una indicación de que un número puede ser primo.
La razón es que ciertas bases utilizadas en la prueba pueden dar como resultado una indicación prima, incluso cuando el número objetivo no es primo. El uso de un número aleatorio como base en la prueba permite ejecutar la prueba repetidamente con una base diferente cada vez, aumentando así la probabilidad de que el resultado indique correctamente primo o no primo 2 .
Por lo tanto, los números aleatorios seleccionados deben ser menores que el número que se está probando. No es necesario que se seleccionen de la gama completa.
Con esto en mente ahora tengo esto:
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 ) debe proporcionar un rango de números lo suficientemente grande para este propósito. Funciona con mi implementación de Miller-Rabin en la medida en que lo he probado hasta ahora.
1 Probar números hasta 3,317,044,064,679,887,385,961,981 contra una breve lista específica de bases arrojará un resultado primo/no primo definitivo.
2 Para resultados primos no deterministas, aún es necesario realizar una prueba determinista (como una división de prueba) para confirmar.
Una forma de obtener un número aleatorio en un rango es
lower + rand() % (upper - lower)rand() es cualquier función que devuelve un número aleatorio mayor que (superior - inferior). Los cálculos se pueden hacer con Integer o 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() ); }