Me voy a centrar en ‘ ¿Hay mejores alternativas? ‘parte de la pregunta, y use Java para explicar cómo se puede lograr esto. Estoy seguro de que otros lenguajes que se mencionaron contienen tales características también, pero será Java todo el camino aquí.
____________________________________________________________
Antes de profundizar en los detalles, piense en los tipos primitivos y las estructuras de datos a su cargo, que probablemente pueda usar para almacenar enteros tan grandes. Tiene int , long (con signed , unsigned : en C y sus derivados directos), y eso es probablemente todo. La mayoría de los lenguajes fuertemente tipados le brindan los tipos de datos mencionados anteriormente, que parecen funcionar para un puñado de propósitos prácticos, pero debemos encontrar enfoques más intuitivos si queremos almacenar, administrar y manipular números de tal magnitud.
Una forma que viene a la mente es usar una estructura de datos de matriz para almacenar estos números. ¿Cómo preguntas? Bueno, piénselo de esta manera: intente almacenar los dígitos del número en consideración dentro de la matriz, es decir, almacenar [matemática] 144 [/ matemática] en una matriz de tamaño [matemática] 3 [/ matemática] como:
array[0] = 4; array[1] = 4; array[2] = 1;
O
array[0] = 1; array[1] = 4; array[4] = 4;
Entiendes la esencia, ¿verdad? Si almacena números de esta manera, el único límite superior de su metodología será el número máximo de elementos que contiene una matriz. Y eso es MUCHOS dígitos.
Ahora, la clase BigInteger de Java y sus métodos asociados son más que capaces de manejar números muy grandes. Veamos los requisitos de la pregunta uno por uno:
____________________________________________________________
¿Cómo debo primero almacenar tales valores?
El siguiente código calcula [math] 100! [/ Math] y lo almacena en un objeto BI large_factorial , que contiene [math] 150 + [/ math] dígitos:
import java.math.BigInteger;
clase pública FactorialBigIntegerApproach {
public static void main (String [] args) {
BigInteger large_factorial = factorial (BigInteger.valueOf (100L));
System.out.println (large_factorial);
}
factorial BigInteger estático privado (número BigInteger)
{
if (número.equals (BigInteger.ONE))
volver BigInteger.ONE;
return number.multiply (factorial (number.subtract (BigInteger.ONE)));
}
}
Salida:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Detrás de escena, este gran número se almacena dentro de una matriz de matriz de enteros (como se discutió anteriormente; manteniendo la documentación intacta):
/ **
* La magnitud de este BigInteger, en orden big-endian : el
* El elemento zeroth de esta matriz es el int más significativo de
* magnitud. La magnitud debe ser “mínima” en que el más significativo
* int ({@code mag [0]}) no debe ser cero. Esto es necesario para
* asegúrese de que haya exactamente una representación para cada BigInteger
* valor. Tenga en cuenta que esto implica que el BigInteger cero tiene un
* matriz magnética de longitud cero.
* /
final int [] mag;
Entonces, el almacenamiento está a cargo. Vamonos:
____________________________________________________________
¿Cómo verifico su primalidad?
El siguiente código verifica si un número de 160 dígitos es primo o no. La explicación sigue:
import java.math.BigInteger;
clase pública BigIntegerPrimalityCheck {
public static void main (String [] args) {
String string =
“5166566839092074458466334866”
+ “571597694114460570387986357538”
+ “048450432901440804868689337999”
+ “823161841839689242893622491638”
+ “917313351308387294478994745350”
+ “551549126803”;
BigInteger bigInteger = nuevo BigInteger (cadena);
System.out.println (bigInteger.isProbablePrime (10));
}
}
Salida:
cierto
Explicación:
El argumento del método isProbablePrime ([math] 10 [/ math] here) se llama parámetro de certainty , que básicamente le pregunta al usuario cuánta incertidumbre está dispuesto a tolerar . Por lo tanto, cuando especificamos [matemática] 10 [/ matemática], eso significa que estamos de acuerdo con acomodar una incertidumbre de [matemática] 1 – (1/2 exp (10)) [/ matemática], o ~ [matemática] 99.902 [/ math]%, lo cual es genial. Ipso facto , el tiempo de ejecución de este método es directamente proporcional a este valor.
Por lo tanto, si está de humor para verificar si un número grande es primo o no con un alto grado de certeza (por ejemplo, [matemática] 100 [/ matemática] o [matemática] 1000 [/ matemática]), es mejor que tome un taza de café también.
Los algoritmos utilizados por BI para la verificación de primalidad son la prueba de primalidad de Miller-Rabin y la prueba de primalidad de Lucas-Lehmer.
____________________________________________________________
¿Cómo calculo el producto de estos dos valores?
Tratemos de multiplicar los dos números que acabamos de observar: [matemática] 100! [/ Matemática] y un primo aleatorio [matemática] 160 [/ matemática]. Aquí hay más código:
import java.math.BigInteger;
clase pública BigIntegerMultiplication {
public static void main (String [] args) {
Cadena uno =
“9332621544394415268169923885”
+ “6266700490715968264381621468”
+ “5929638952175999932299156089”
+ “4146397615651828625369792082”
+ “7223758251185210916864000000”
+ “000000000000000000”;
Cadena dos = “5166566839092074458466334866”
+ “571597694114460570387986357538”
+ “048450432901440804868689337999”
+ “823161841839689242893622491638”
+ “917313351308387294478994745350”
+ “551549126803”;
BigInteger bigInteger_1 = nuevo BigInteger (uno);
BigInteger bigInteger_2 = nuevo BigInteger (dos);
Producto BigInteger = bigInteger_1.multiply (bigInteger_2);
System.out.println (one.length () + “,” + two.length ());
System.out.println (producto);
System.out.println (product.toString (). Length ());
}
}
Salida:
158, 160
482176129930644483360933865113448402532473036347509752252989813068609925107973799686381369488640867483509145219090982364287740744814189928631787042247710544703225173685856499574106417511215995125790606610173396711837190400168583226414432980006584225915912256093361256119448870003423722227105792000000000000000000000000
318
Lo que acabamos de ver fue la multiplicación de un número de dígitos [matemáticos] 158 [/ matemáticos] y un número de dígitos [matemáticos] 160 [/ matemáticos], dando como resultado un producto enorme [31] [/ matemáticos] dígitos. BI utiliza el algoritmo Karatsuba y los enfoques de multiplicación Toom-Cook para calcular productos tan grandes.
____________________________________________________________
¿Cómo se hace para el cifrado RSA?
Ahora, generar primos de calidad criptográfica es un requisito previo necesario para lograr esto. Este hilo SOF trata este problema de forma muy compleja y efectiva.
____________________________________________________________
Y ahora, después de escribir, codificar y encontrar citas relevantes durante la última hora, me detendré. Espero que esto haya ayudado. Por favor, hágamelo saber en caso de que presente algún hecho incorrecto / incorrecto. Estaré más que feliz de actualizar la respuesta.
