En el sentido de muchos desafíos, pensé que este podría ser interesante.

En este desafío, utilizaremos el Sistema de número de residuos (RNS) para realizar sumas, restas y multiplicaciones en enteros grandes.

¿Qué es el RNS?

El RNS es una de las muchas formas en que las personas se han desarrollado para identificar enteros. En este sistema, los números están representados por una secuencia de residuos (que son los resultados después de una operación de módulo (es decir, el resto después de la división de enteros)). En este sistema, cada entero tiene muchas representaciones. Para mantener las cosas simples, vamos a limitar las cosas para que cada número entero esté representado de forma única. Creo que es más fácil describir lo que está sucediendo con un ejemplo concreto.

Veamos los primeros tres números primos: 2, 3, 5. En el sistema RNS, podemos usar estos tres números para representar de manera única cualquier número que sea menor que 2 * 3 * 5 = 30 usando residuos. Toma 21:

21 es menor que 30, por lo que podemos representarlo usando los resultados después de modificar por 2, 3 y 5. (es decir, el resto después de un entero dividiendo entre 2, 3 y 5)

Identificaríamos 21 con la siguiente secuencia de enteros:

21 ~ {21 mod 2, 21 mod 3, 21 mod 5} = {1, 0, 1}

Y así, en nuestro sistema RNS, en lugar de "21", usaríamos {1,0,1}.

En general, dado un número entero n , representamos n como { n mod 2, ..., n mod p_k } donde p_k es el primo más pequeño, de modo que n es menor que el producto de todos los primos menores o iguales que p_k .

Otro ejemplo, digamos que tenemos 3412. Necesitamos usar 2,3,5,7,11,13 aquí porque 2*3*5*7*11*13=30030, mientras 2*3*5*7*11=2310que , que es demasiado pequeño.

3412 ~ {3412 mod 2, 3412 mod 3, 3412, mod 5, ..., 3412 mod 13} = {0, 1, 2, 3, 2, 6}

Usted nota que usando este sistema podemos representar números muy grandes relativamente sin dolor. Usando {1, 2, 3, 4, 5, 6, 7, 8, ...} residuos, podemos representar números hasta {2, 6, 30, 210, 2310, 30030, 510510, 9699690 ...} respectivamente. ( Aquí está la serie )

Nuestra tarea

Utilizaremos estos residuos para realizar +, - y * en grandes cantidades. Describiré estos procesos a continuación. Por ahora, aquí están las especificaciones de entrada y salida.

Entrada

Se le darán dos números (potencialmente muy grandes) a través de un stdin o argumento de función. Se darán como cadenas de 10 dígitos de base.

Con el fin de delinear aún más el problema, llamamos a la primera entrada ny a la segunda m. Suponga que n> m> = 0 .

También se le dará +o -o *para indicar la operación a realizar.

Salida

Deje x ser un número entero. Usaremos [ x ] para referirnos a la representación RNS descrita anteriormente de x .

Debes dar salida [n] <operator> [m] = [result]

Cómo realizar las operaciones en RNS

Estas operaciones son relativamente simples. Dados dos números en notación RNS, para sumarlos, restarlos o multiplicarlos, simplemente realice las operaciones dadas por componentes y luego tome el módulo.

es decir

{1, 2, 3} + {1, 1, 4} = {(1 + 1) mod 2, (2 + 1) mod 3, (3 + 4) mod 5} = {0, 0, 2}

Tenga en cuenta que si el número de residuos utilizado para representar dos números diferentes no es el mismo, al realizar operaciones, deberá extender el número "más corto" para que tenga el mismo número de residuos. Esto sigue el mismo proceso. Vea los casos de prueba para un ejemplo.

Lo mismo ocurre si el resultado requiere más residuos que cualquier entrada. Entonces ambas entradas necesitan ser "extendidas".

Detalles importantes

• Aquí trataremos con grandes números, pero no arbitrariamente grandes. Seremos responsables de los números hasta el producto de los primeros 100 primos (ver más abajo). Para este fin, se le otorgan los primeros 100 primos gratis (sin costo de byte) . Puede pegarlos en una matriz llamada po algo idiomático en su idioma y luego restar el número de bytes utilizados para iniciar esta matriz de su total final. Esto, por supuesto, significa que pueden estar codificados o puede usar uno incorporado para generarlos.

• Si por alguna razón esta es la representación entera por defecto utilizada en su idioma. Eso está bien.

• No puede usar ningún tipo de Entero de precisión arbitraria a menos que sea el idioma predeterminado. Si es el valor predeterminado, no puede usarlo para almacenar enteros que normalmente no caben en 64 bits.

• Para ser claros, cada número entero siempre estará representado con la menor cantidad de residuos posible. Esto se aplica tanto a la entrada como a la salida.

• Creo que las otras especificaciones deberían evitar esto, pero ser redundantes: es posible que no realice la operación dada en las entradas y luego cambie todo a RNS y luego a la salida. Debe cambiar las entradas a RNS y luego realizar las operaciones para producir la salida.

Casos de prueba

1. Entrada:

n = 10
m = 4
+

Salida:

{ 0, 1, 0 } + { 0, 1 } = { 0, 2, 4 }

Explicación:

Primero, cambie cada número a su representación RNS como se describe arriba:

10 ~ {0,1,0}y 4 ~ {0,1}. Tenga en cuenta que cuando queremos hacer una suma de componentes, 10tiene más componentes que 4. Por lo tanto, debemos "extender" el número más corto. Entonces escribiremos brevemente 4 ~ {0,1} --> {0,1, 4 mod 5} = {0,1,4}. Ahora procedemos con la suma y luego tomamos el módulo.

2. Entrada

n=28
m=18
+

Salida:

 [ 0, 1, 3 ] + [0, 0, 3 ] = [ 0, 1, 1, 4 ]

3. Entrada (me aplasta la cara en el teclado)

n=1231725471982371298419823012819231982571923
m=1288488183
*

Salida (dividida en líneas separadas para facilitar la lectura):

[1, 2, 3, 6, 2, 10, 2, 1, 12, 16, 7, 15, 34, 29, 31, 5, 55, 32, 66, 61, 3, 76, 52, 14, 65, 44, 99, 57 ] 
* 
[1, 0, 3, 3, 4, 8, 9, 10, 8, 0 ] 
= 
[1, 0, 4, 4, 8, 2, 1, 10, 4, 0, 17, 7, 27, 21, 44, 51, 56, 9, 6, 9, 12, 0, 52, 36, 43, 68, 99, 24, 96, 39, 96, 66, 125] 

nrequiere 28 primos. mrequiere 10. n*mrequiere 33.

4. Entrada

n=8709668761379269784034173446876636639594408083936553641753483991897255703964943107588335040121154680170867105541177741204814011615930342030904704147856733048115934632145172739949220591246493529224396454328521288726490
m=1699412683745170450115957274739962577420086093042490863793456500767137147999161679589295549397604032154933975242548831536518655879433595016
-

Salida:

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 509]
-
[0, 2, 1, 6, 1, 12, 11, 18, 14, 28, 21, 36, 37, 42, 16, 52, 41, 60, 16, 70, 49, 78, 80, 88, 49, 100, 13, 106, 4, 112, 68, 130, 36, 138, 37, 150, 0, 162, 8, 172, 163, 180, 18, 192, 129, 198, 135, 222, 78, 228, 90, 238, 57, 250, 36, 262, 87, 270, 206, 280, 193, 292, 253, 310, 224, 316, 57, 336, 48, 348]
=
[0, 1, 4, 1, 10, 1, 6, 1, 9, 1, 10, 1, 4, 1, 31, 1, 18, 1, 51, 1, 24, 1, 3, 1, 48, 1, 90, 1, 105, 1, 59, 1, 101, 1, 112, 1, 0, 1, 159, 1, 16, 1, 173, 1, 68, 1, 76, 1, 149, 1, 143, 1, 184, 1, 221, 1, 182, 1, 71, 1, 90, 1, 54, 1, 89, 1, 274, 1, 299, 1, 266, 1, 228, 1, 340, 1, 170, 1, 107, 1, 340, 1, 88, 1, 157, 1, 143, 1, 22, 1, 22, 1, 58, 1, 296, 1, 371, 1, 140]

nutiliza 100 primos musa 70 primos. n-musa 99 primos.

Lo verifiqué usando la ChineseRemimplementación incorporada del teorema del resto chino en GAP (que básicamente toma números RNS y los cambia a enteros de base 10). Creo que son correctos. Si algo parece sospechoso, hágamelo saber.

Para aquellos que se preocupan, el producto de los primeros 100 primos es:

471193079990618495316248783476026042202057477340967552018863483961641533584503
422120528925670554468197243910409777715799180438028421831503871944494399049257
9030720635990538452312528339864352999310398481791730017201031090

Este número es 1 mayor que el número máximo que podemos representar usando el sistema dado (y la limitación principal de 100).

Algo relacionado

BRECHA

Algunos antecedentes: Admitiré que cuando creé esta pregunta, hace muchos meses, no tenía un método para resolver la parte difícil de esta pregunta: determinar el número correcto de primos para usar. Tenemos muchas personas muy inteligentes en este sitio, y realmente esperaba que alguien encontrara una manera de hacerlo con bastante rapidez. Sin embargo, como esto no sucedió, ni siquiera estaba seguro de que fuera realmente posible resolver este problema. Entonces, tuve que tomarme el tiempo para idear un método. Creo que lo que he hecho no rompe ninguna de las reglas en este desafío, por supuesto, me encantaría que esto se verifique.

También me arrepiento un poco de la elección del código de golf porque las soluciones son un poco más profundas de lo que normalmente se ajustan al formato de etiqueta. Dicho esto, para seguir las reglas del sitio, hay una versión "golfizada" de mi solución al final de esta publicación.

Código

### The first 100 primes;
primes := Primes{[1..100]};

### In many of the functions below, the 'string' variable is a string of digits
###


### Returns the 'index' digit of 'string' as an integer
GetValueAsInt := function(string, index) 
    return IntChar(string[index]) - 48;
end;

### Used in the 'modulus' function. See that comment for more information. 
### Calculates the contribution to the modulus of a digit 'digit' in the 10^power place.
### 'integer' is the modulus
digit_contribution := function(digit, integer, power)
    local result, i;
    result := 1;
    for i in [0..power-1] do
        result := ( result * (10 mod integer) ) mod integer;
    od;
    result := (result * (digit mod integer) ) mod integer;
    return result;
end;

### This modulus function is used to calculate the modulus of large numbers without storing them
##### as large numbers.
### It does so by breaking them into digits, and calculating the contribution of each digit.
### e.g. 1234 mod 5 = (1000 mod 5)(1 mod 5) + (200 mod 5)(2 mod 5) + (10 mod 5)(3 mod 5) + (4 mod 5)
### It actually mods after every calculation to ensure that we never get a number larger
##### than the modulus ('integer') squared, which will never be even close to 10^64-1
modulus := function(string, integer)
    local i, result, digit, len;
    len := Length(string);
    result := 0;
    for i in [1..len] do
        digit :=  IntChar(string[i]) -48;
        result := ( result + digit_contribution(digit, integer, len-i) )  mod integer;
    od;
    return result;
end;

### This returns the product of the first i-1 primes (mod j). It must not (and does not)
##### ever store an integer larger than 2^64-1
phi_i := function(i,j)
    local index, result;
    result := 1;
    for index in [1..i-1] do
        result := ( result * primes[index] ) mod primes[j];
    od;
    return result;
end;

### Calculates the first residues of 'string' mod the first 100 primes
get_residues := function(string) 
    local p, result;
    result := [];
    for p in primes do
        Add( result, modulus(string, p) );  
    od; 
    return result;
end;

### Gets the ith element in the partial_chinese array, given the previous elements
### See the explanation section and partial_chinese function for more info
get_partial_i := function( i, residues, previous_array )
    local index, result;
    result := residues[i];
    for index in [1..Length(previous_array)] do
        result := ( result - previous_array[index]*phi_i(index,i) ) mod primes[i]; 
    od;     
    result := ( result / phi_i(i,i) ) mod primes[i];
    return result;
end;

### returns an array such that the sum of prod_primes(i)*array[i] is equal to the integer value
##### that is represented by the residues. (It basically just does the CRT without
##### actually summing everything.) prod_primes(i) is the product of the first i-1 primes 
### See the explanation for a bit more info
### This is what allows us to determine the minimal number of primes to represent a RNS number
partial_chinese := function( string )
    local array, i, residues;
    residues := get_residues(string);
    array := [];        
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;   
end;

### Same as partial_chinese but takes input in a different form.
partial_chinese_from_residues := function(residues)
    local array, i;
    array := [];        
    for i in [1 .. Length(primes)] do
        Add( array, get_partial_i( i, residues, array ) );
    od;
    return array;
end;

### gives you the number of primes needed to represent an integer. Basically asks how 
##### many trailing zeros there are in the chinese array.
get_size := function(string)
    local array, i, len, result;
    array := partial_chinese(string);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi; 
    od; 
    Print("ERROR: get_size().\n");
    return 0;
end;

### Same as above but with different input format
get_size_from_residues := function(residues)
    local array, i, len, result;
    array := partial_chinese_from_residues(residues);
    len := Length(array);
    for i in [0..len-1] do
        if  not (array[len-i] = 0) then
            return len -i;
        fi; 
    od; 
    Print("ERROR: get_size().\n");
    return 0;
end;

### the actual function. inputs are all strings
f := function(in1, in2, opperation)
    local residues_1, residues_2, residues_result, i;
    residues_1 := get_residues(in1);
    residues_2 := get_residues(in2);
    residues_result := [];
    if opperation = "+" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] + residues_2[i] ) mod primes[i]);
        od;     
    elif opperation = "*" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] * residues_2[i] ) mod primes[i]);
        od;     
    elif opperation = "-" then
        for i in [1..Length(primes)] do
            Add( residues_result, ( residues_1[i] - residues_2[i] ) mod primes[i]);
        od;     
    fi;
    Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );
end;

Explicación:

Para comenzar, calculamos los 100 residuos de ambas entradas. Hacemos esto con la modulusfunción en el código. Traté de tener cuidado para que usemos la modfunción incorporada después de cada paso. Esto garantiza que nunca tengamos un número mayor que 540^2, que es 1 menor que el centésimo primo al cuadrado.

Después de tener todos los residuos, podemos realizar la operación dada y modcada entrada nuevamente. Ahora tenemos un designador único para el resultado, pero necesitamos determinar el número mínimo de entradas que tenemos que usar para representar el resultado y cada una de las entradas.

Averiguar cuántos residuos realmente necesitamos es, con mucho, la parte más difícil de este problema. Para determinar esto, realizamos la mayoría de los pasos del Teorema del resto chino (CRT). Sin embargo, obviamente tenemos que hacer modificaciones para no terminar con números que sean demasiado grandes.

Dejado prod(i)ser la suma de los primeros i-1números primos. Por ejemplo,

prod(1) = 1
prod(2) = 2
prod(3) = 6
prod(4) = 30
etc

Dejar Xser un número entero. Dejar {r_i}ser los residuos de X, es decir

r_i = X mod p_i

¿Dónde p_iestá el ith prime? Esto es para 1<i<=100en nuestro caso.

Ahora vamos a usar el CRT para encontrar una secuencia {u_i}tal que la suma ide prod(i) * u_isea ​​igual a X. Tenga en cuenta que cada uno u_itambién es técnicamente un residuo, como u_i < p_i. Además, si X < prod(i)entonces u_i = 0. Esto es de importancia crítica. Significa que al examinar los ceros finales, podemos determinar cuántos de los residuos r_irealmente necesitamos representar Xen el RNS.

Si desea examinar algunas secuencias de u_i, la partial_chinesefunción devuelve la u_isecuencia.

Al jugar con el CRT, pude encontrar una fórmula recursiva para los u_ivalores, resolviendo el problema de determinar cuántos residuos necesitamos.

La formula es:

u_i = [ r_i - SUM ] / prod(i)       (mod p_i)

¿Dónde SUMestá la suma j in [1,i)de u_j * prod(i).

Por supuesto, en prod(i)realidad no se puede calcular en algunos casos porque es demasiado grande. Para este propósito, utilicé la phi_ifunción. Esta función vuelve prod(j) (mod p_i). Está moden cada paso, por lo que nunca calculamos nada que sea demasiado grande.

Si tiene curiosidad de dónde proviene esta fórmula, recomendaría trabajar con un par de ejemplos de CRT, que se pueden encontrar en la página de Wikipedia .

Finalmente, para cada entrada y nuestra salida, calculamos la u_isecuencia y luego determinamos los ceros finales. Luego tiramos tantos r_idesde el final de las secuencias de residuos.

Código "Golfed", 2621 bytes

primes:=Primes{[1..100]};GetValueAsInt:=function(string,index)return IntChar(string[index])-48;end;digit_contribution := function(digit, integer, power)local result, i;result:=1;for i in [0..power-1] do result := ( result * (10 mod integer) ) mod integer;od;result:=(result*(digit mod integer) ) mod integer;return result;end;modulus:=function(string, integer)local i,result,digit,len;len:=Length(string);result:=0;for i in [1..len] do digit:= IntChar(string[i])-48;result:=(result+digit_contribution(digit,integer,len-i)) mod integer;od;return result;end;phi_i:=function(i,j)local index,result;result:=1;for index in [1..i-1] do result:=(result*primes[index] ) mod primes[j];od;return result;end;get_residues:=function(string) local p,result;result:=[];for p in primes do Add(result,modulus(string,p));od;return result;end;get_partial_i:=function(i,residues,previous_array)local index,result;result:=residues[i];for index in [1..Length(previous_array)] do result:=(result-previous_array[index]*phi_i(index,i) ) mod primes[i];od;result:=(result/phi_i(i,i)) mod primes[i];return result;end;partial_chinese:=function(string)local array,i,residues;residues:=get_residues(string);array:=[];for i in [1 .. Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;partial_chinese_from_residues:=function(residues)local array,i;array:=[];for i in [1..Length(primes)] do Add(array,get_partial_i(i,residues,array));od;return array;end;get_size:=function(string)local array,i,len,result;array:=partial_chinese(string);len:=Length(array);for i in [0..len-1] do if not (array[len-i] = 0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;get_size_from_residues:=function(residues)local array,i,len,result;array:=partial_chinese_from_residues(residues);len:=Length(array);for i in [0..len-1] do if not (array[len-i]=0) then return len-i;fi;od;Print("ERROR: get_size().\n");return 0;end;f:=function(in1,in2,opperation)local residues_1,residues_2,residues_result,i;residues_1:=get_residues(in1);residues_2:=get_residues(in2);residues_result:=[];if opperation = "+" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]+residues_2[i] ) mod primes[i]);od;elif opperation = "*" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]*residues_2[i])mod primes[i]);od;elif opperation = "-" then for i in [1..Length(primes)] do Add(residues_result,(residues_1[i]-residues_2[i]) mod primes[i]);od;fi;Print(residues_1{[1..get_size(in1)]}, " ", opperation, " ", residues_2{[1..get_size(in2)]}, " = ", residues_result{[1..get_size_from_residues(residues_result)]} );end;

Mathematica, no golf

rns[d_,l_]:=Table[Reap[
    FoldPairList[Sow@QuotientRemainder[10#+#2,Prime@i]&,0,d]
  ][[2,1,-1,2]],{i,l}];
plus[a_,b_]:=Mod[a+b,Prime@Range@Length@a];
subtract[a_,b_]:=Mod[a-b,Prime@Range@Length@a];
times[a_,b_]:=Mod[a b,Prime@Range@Length@a];
mag[f_]:=LengthWhile[FoldList[#/#2&,f,Prime@Range@100],#>1.1&];
ext[m_,n_,i_]:=Fold[Mod[1##,Prime@i]&,m,Prime@Range@n];
multi[e_,p_,t_]:=Tr@Position[Mod[e Range@p,p],p-t];
appx[d_] := N@FromDigits[{d~Take~UpTo[6], Length@d}]

• La función rns[d_,l_]convierte un entero de base 10 den un entero RNS de longitud l.

• Función plus/times / subtractagregar / multiplicar / restar un entero RNS a / de otro, los cuales son de la misma longitud.

• La función mag[f_]estima la magnitud aproximada del número de coma flotantef en términos del límite inferior de la longitud de su representación RNS.

• La función ext[m_,n_,i_]descubre el resto de la división del producto de myPrime[Range@n] por Prime[i].

• Función multi[e_,p_,t_] proporciona el multiplicador más pequeño mque satisfaceDivisible[m*e+t,p]

• La función appx[d_]toma el primero6 dígitos de un entero decimal y da su valor aproximado de coma flotante.

Con la ayuda de las funciones anteriores, ahora podemos resolver un problema complicado: determinar la longitud del resultado .

Primero, tengo que aclarar que no es una tarea fácil determinar la longitud RNS de un entero. Para enteros pequeños, podemos compararlos directamente con el producto de primos. Pero para enteros muy grandes, ya que está prohibido calcular el producto de los números primos con una precisión infinita, esa comparación ya no funciona.

Por ejemplo, dado que el producto de prime 1to 30es 3.16*10^46, la longitud RNS de enteros alrededor 3.16*10^46puede ser 29o 30. La función magdará 29como referencia para estos enteros, mostrando que ambos 29y30 son posibles.

Una vez que conocemos la magnitud, simplemente representamos el entero de acuerdo con esa magnitud directamente, con la esperanza de calcular su longitud real. El truco aquí es agregar algunos números nuevos al número original y modificar su representación RNS, hasta que la representación sea completamente cero.

Por ejemplo, mag[211.]es 4, y su 4representación de longitud es {1, 1, 1, 1}.

step 1:   {1,1,1,1} -> {0,2,2,2}  by adding  (1) * 1 = 1
step 2:   {0,2,2,2} -> {0,0,1,6}  by adding  (2) * 2 = 4
step 3:   {0,0,1,6} -> {0,0,0,2}  by adding  (2*3) * 4 = 24
step 4:   {0,0,0,2} -> {0,0,0,0}  by adding  (2*3*5) * 6 = 180
step 5:   calculate 211 + (1 + 4 + 24 + 180) ~ 420

Al agregar algún número, aumentamos 211al número más pequeño que es divisible por 210( 2*3*5*7). Y ahora concluimos que el número original es mayor que 210, ya que 420es igual a "aproximadamente" dos veces de 210. No es difícil imaginar que si comenzamos desde 209, el número final es "aproximadamente"210 .

La función length[f_,n_]toma el valor de coma flotante fpara estimar la magnitud y corregirla en base a su representación RNS n.

length[f_,n_]:=With[{g=mag@f},
    g+If[#==0,1,Round[(#+f)/Times@@Prime@Range@g]-1]&[
      FoldList[Times,1.,Prime[Range[g-1]]].
      FoldPairList[
        Block[{i=#2,m},
          {m=multi[ext[1,i-1,i],Prime@i,Part@##],rnsPlus[#,ext[m,i-1,#]&/@Range[g]]}
        ]&,n,Range[g]]]]

La función rnsOperation[a_,b_,op_,rnsop_]proporciona rnsop[a,b]y opcorresponde a las operaciones normales utilizadas para obtener resultados aproximados basados ​​en valores de coma flotante.

rnsOperation[a_,b_,op_,rnsop_]:=Block[{c=op[appx@a,appx@b],m},
    m=mag[c];m=length[c,rnsop[rns[a,m],rns[b,m]]];rnsop[rns[a,m],rns[b,m]]]

Ejemplo

rnsOperation[
    IntegerDigits@1231725471982371298419823012819231982571923,
    IntegerDigits@1288488183,
    Times, times]
(* {1,0,4,4,8,2,1,10,4,0,17,7,27,21,44,51,56,9,6,9,12,0,52,36,43,68,99,24,96,39,96,66,125} *)

Python 3 , 435 bytes

Este desafío ha estado en mi lista de deseos por un tiempo, pero solo recientemente: a) Puse tiempo y atención en intentar realmente una respuesta; yb) en realidad probé mi idea para calcular el tamaño de los números (y, por lo tanto, el número de números primos comparándolo con el tamaño de los primarios) usando alguna combinación impía de logaritmos y el Teorema del resto chino. Desafortunadamente, trabajar con logaritmos al intentar determinar el número de primos que, por ejemplo,large_primorial + 3 requiere, significaba que tenía que encontrar formas de solucionar problemas de punto flotante.

Y entonces, este es un puerto de la respuesta de Liam .

Pruébalo en línea!

from functools import reduce as R
G=range
d=lambda s:[R(lambda z,c:(z*10+int(c))%q,s,0)for q in p]
h=lambda j,i:R(lambda z,q:z*q%p[i],p[:j],1)
def s(r):
 a=[];z=99
 for i in G(100):
  P=p[i];u=r[i]
  for j in G(len(a)):u=(u-a[j]*h(j,i))%P
  for k in G(1,P):
   if h(i,i)*k%P<2:break
  a+=u*k%P,
 while(a[z]<1)*z:z-=1
 return r[:z+1]
def f(a,b,n):u=d(a);v=d(b);print(s(u),n,s(v),'=',s([eval(str(u[i])+n+str(v[i]))%p[i]for i in G(100)]))

Explicación

Mientras intentaba transmitir la respuesta de Liam, personalmente encontré que algunas de las explicaciones dadas eran confusas, así que este es mi intento de explicar su algoritmo.

Primero, obtenemos los residuos de ny m.

res1 = get_residues(n)
res2 = get_residues(m)

Esto implica convertir todos los dígitos de las cadenas de entrada y convertirlos en módulos de números de cada uno de nuestros primos, por ejemplo, para 28, tendríamos [(20 + 8) mod 2, (20 + 8) mod 3, (20 + 8) mod 5, etc]

def get_residues(string):
    result = []
    for p in primes:
        result.append(reduce(lambda z, c:(z*10+int(c)) % p, string, 0))

Luego sumamos, multiplicamos o restamos los residuos por pares usando eval()

result = []
for i in range(len(primes)):
    result.append((eval(str(res1[i]) + op + str(res2[i])) % primes[i])

Luego obtenemos los tamaños de nuestros residuos, es decir, el número mínimo de primos que necesitamos.

size1 = get_size(res1)
size2 = get_size(res2)
size3 = get_size(result)

Obtener los tamaños es la parte más complicada y más intensiva en código. Usamos la partial_chinesefunción, que nos da nuestra secuencia de u_ipara determinar el tamaño con. Más u_ien un momento.

def get_size(residues):
    array = partial_chinese(residues)
    size = len(residues)-1
    while array[size] == 0 and size:
        size -= 1
    return size+1  # to prevent off-by-one errors from 0-indexing

La secuencia u_ise calcula tomando cada residuo r_i, restando la suma u_j * primorial(j) for j in [1, i)y luego dividingpor primorial(i)todo el módulo primes[i]. Es decir, u_i = (r_i - SUM) / primorial(i). Más información sobre nuestras funciones primarias y de división en un momento.

def partial_chinese(residues):
    array = []
    for i in range(len(primes)):
        array.append(get_partial_i(i, residues, array))
    return array

def get_partial_i(i, residues, previous_array):
    result = residues[i]
    for j in range(len(previous_array)):
        result = (result - previous_array[j] * phi_i(j, i)) % primes[i]
    result = result * inverse(phi_i(i, i), primes[i]) % primes[i]
    return result

phi_i(j, i)calcula primorial(j) mod primes[i]. El módulo de división cualquier primo pse implementa fácilmente mediante la comprobación manual de inversos multiplicativos, ya que podemos estar seguros de que cualquier posible u_ies 0 <= u_i < pcoprimo a p y por lo tanto se garantiza un inverso multiplicativo.

def phi_i(j, i):
    return reduce(lambda z, q: z * q % primes[i], primes[:j], 1)

def inverse(n, p):
    for i in range(1, p):
        if n * i % p == 1:
            return i

Con todo eso hecho, imprimimos nuestra cadena y terminamos.

print(res1[:size1], op, res2[:size2], "=", result[:size3])

Que sigue

Esto fue divertido de implementar. Todavía quiero ver si puedo usar logaritmos de alguna manera en otra respuesta. Y me gustaría implementar este código o algo así en un lenguaje de golf funcional, como APL o Jelly. ¡Todas y cada una de las sugerencias y correcciones de golf son bienvenidas!