Dado un número entero N con factores primos desconocidos f1 , f2 ... fn y dados unos enteros únicos k1 , k2 ... kn con √N≥ki>2 para todos i tal que f_1 \equiv 1\pmod {k_1} f_2 \equiv 1\pmod {k_2} f_n \equiv 1\pmod {k_n} ¿Saber k_1 , k_2 ... k_n de alguna manera ayudar a encontrar f_1 , f_2 ... f_n ?
Respuesta
¿Demasiados anuncios?
Roddy MacPhee
Puntos
72
Lulu hizo el punto de que, en cualquier momento k_i son todas constantes, no tienes mucha ayuda. Aquí hay algunas cosas que sí:
- Observando que k_i multiplicado por el negativo de su inverso multiplicativo mod cualquier primo que no sea f_i está fuera como un módulo equivalente más alto, porque sumaría a 0 mod el primo probado.
Esto significa lo siguiente:
- impar k_i no puede tener multiplicadores Impares.
- k_i\equiv 1\pmod 3 no puede tener un multiplicador r\equiv 2\pmod 3
- k_i\equiv 2\pmod 3 no puede tener un multiplicador r\equiv 1\pmod 3
- k_i\equiv 1\pmod 5 no puede tener un multiplicador r\equiv 4\pmod 5
Esto y la posibilidad de limitar su alcance, puede ayudar mucho.
0 votos
Creo que más contexto podría ayudar. Si, digamos, k_i=2 para todos i en realidad no nos dice mucho (sólo nos dice que N es impar que, presumiblemente, ya podríamos resolver). Si el k_i son grandes, entonces supongo que reduce considerablemente la búsqueda.
0 votos
@lulu, he proporcionado más contexto en la pregunta. Supongamos que k_i>2 para todos i .
0 votos
¿gcd desconocido? sólo pensando en posibilidades.
0 votos
El teorema de Dirichlet sobre las progresiones aritméticas nos dice que hay infinitos primos que son 1 mod. k_i para cada i por lo que no podemos decir lo que el f_i son.
1 votos
@boink están al menos limitados por N. y todos menos 1 menos que \sqrt{N}
0 votos
De hecho, puesto que todos ellos tienen garantizado ser impar, podemos duplicar cualquier impar k_i y sólo mirar allí. si sabemos n también podríamos argumentar a favor de la densidad.