Encuentra los divisores $n_i$ de $a_i$ , mutuamente coprima, con $\prod n_i=\operatorname{lcm}(a_i)$

Question

Se nos da $k$ números enteros positivos $a_i$ y quiere tantos enteros positivos $n_i$ cada uno dividiendo el respectivo $a_i$ con el $n_i$ mutuamente coprima, y el producto de las $n_i$ igual al mínimo común múltiplo del $a_i$ .
_{Nota: <span class="math-container">$1$</span> es coprima con todo número entero positivo, por lo que <span class="math-container">$n_i=1$</span> a veces está bien.}

Hay un método sencillo cuando podemos poner el $a_i$ como $\prod p_j^{m_{j,i}}$ para los primos $p_j$ . Inicialmente fijamos todos los $n_i$ a $a_i$ entonces para cada primo $p_j$ que aparecen en las factorizaciones del $a_i$ elegimos uno de los posibles $i$ con multiplicidad máxima $m_{j,i}$ y para cada otros $i$ dividir $n_i$ por $p_j^{m_{j,i}}$ .

¿Podemos proceder sin factorización o, si es imposible, con el menor trabajo de factorización posible (quizás utilizando una primitiva de Máximo Común Divisor y/o otros métodos computacionalmente eficientes)?

---

Dado $a_0=554400=2^5\cdot 3^2\cdot 5^2\cdot 7\cdot 11$ , $a_1=4422600=2^3\cdot 3^5\cdot 5^2\cdot 7\cdot 13$
$k=2$ las únicas 4 soluciones son:

• $n_0=2^5\cdot 5^2\cdot 7\cdot 11=61600$ , $n_1=3^5\cdot 13=3159$
• $n_0=2^5\cdot 5^2\cdot 11=8800$ , $n_1=3^5\cdot 7\cdot 13=22113$
• $n_0=2^5\cdot 7\cdot 11=2464$ , $n_1=3^5\cdot 5^2\cdot 13=78975$
• $n_0=2^5\cdot 11=352$ , $n_1=3^5\cdot 5^2\cdot 7\cdot 13=552825$

---

Resolver el problema para $k=2$ conduce a una solución para las grandes $k$ sustituyendo iterativamente $a_i$ y $a_{i'}$ con el $n_i$ y $n_{i'}$ obtenido para el $k(k-1)/2$ pares de $i,i'$ con $i<i'$ . Sin embargo, eso parece menos que óptimo.

---

El problema es de interés general en los grandes problemas de la TRC. El contexto motivador inicial fue la aplicación de la Teorema chino del resto en el último paso del Pohlig-Hellman algoritmo con módulos compuestos, allí .

Answer 1

Actualmente no se conoce ningún algoritmo de tiempo polinómico para encontrar factorizaciones primos de números enteros, así que aquí tenemos un algoritmo que, aunque está lejos de ser perfecto, se ejecuta en tiempo polinómico.

Dejemos que $A=\{a_1,\ldots,a_k\}$ , dejemos que $M$ sea el elemento máximo de $A$ y que $n=\log_2{M}$ . Determinaremos la complejidad computacional en términos de $n$ y $k$ .

Todas las primas $p$ tiene una mayor potencia $m_p$ entre los elementos de $A$ Es decir $m_p$ es el poder de $p$ en $\text{lcm}\hspace{1pt}A$ . Nuestro primer objetivo será encontrar valores $b_i$ que será un múltiplo de sólo aquellos primos $p$ para lo cual el poder de $p$ en $a_i$ es $m_p$ . A continuación, los utilizaremos para encontrar los valores $c_i$ que será el producto de los valores $p^{m_p}$ tal que $p^{m_p}$ divide $a_i$ . Por último, las compararemos entre sí para determinar $n_i$ . Esto se completará en $\mathcal{O}(k\cdot n^5+k^2\cdot n)$ tiempo, que es efectivamente un polinomio.

Para cada $a_i$ definimos

$$b_i=\frac{a_i^{n+1}}{\gcd(a_i^{n+1},\text{lcm}\hspace{1pt}\{a_j^n\text{ s.t. }j\neq i\}\})}$$

Averigüemos qué está pasando aquí. Lo que hace el denominador es encontrar la máxima potencia de cada primo que divide un elemento de $A\backslash\{a_i\}$ y multiplica ese máximo por $n$ . A continuación, toma estos poderes y los compara con los que se encuentran en $a_i^{n+1}$ y toma el más pequeño. Si la potencia de $p$ encontrado en $a_i$ es $p^{m_p}$ , donde $m_p$ debe ser como máximo $n$ entonces $p^{m_p}\cdot(n+1)>p^{m_p}\cdot n$ Así que $p$ dividirá $b_i$ y en caso contrario, ya que $(p^{m_p}-1)\cdot(n+1)<p^{m_p}\cdot n$ , $p$ no dividirá $b_i$ . Así, $p$ divide $b_i$ si y sólo si $p^{m_p}$ divide $a_i$ . Este proceso llevará $\mathcal{O}(k\cdot n^4)$ tiempo, resultante de tomar $k$ $\gcd$ sobre valores con un máximo de $n^2$ bits.

Ahora queremos encontrar $c_i$ para lo cual el poder de $p$ es $m_p$ si $p^{m_p}$ divide $a_i$ y 0 en caso contrario. Para ello, haremos lo siguiente (nótese que los subíndices se han eliminado aquí para mayor claridad):

x = gcd(a,b)
while (x != 1)
    c *= x
    a /= x
    x = gcd(a,b)

En cada iteración, esto multiplicará el poder de $p$ en $c_i$ por al menos 1 siempre que no sea todavía $p^{m_p}$ . Por lo tanto, se necesitará como máximo $m_p\leq n$ iteraciones, cada una de las cuales toma $\mathcal{O}(n^5)$ tiempo debido a la multiplicación, por lo que el proceso de búsqueda de valores de $c_i$ requiere como máximo $\mathcal{O}(k\cdot n^5)$ tiempo.

Por último, tenemos que encontrar nuestros valores de $n_i$ . Las encontramos en orden. Simplemente dejamos que $n_1=c_1$ , entonces toma el $\gcd$ de esto con los otros valores de $c_i$ y dividir estos valores antiguos de $c_i$ por eso $\gcd$ para obtener nuevos valores. A continuación, hacemos lo mismo con todos los demás valores desde 2 hasta $k$ , tomando $\mathcal{O}(k^2\cdot n+n^2)$ tiempo, dándonos valores de trabajo de $n_i$ en tiempo polinómico.