Dado un número entero $N$ con factores primos desconocidos $f_1$ , $f_2$ ... $f_n$ y dados unos enteros únicos $k_1$ , $k_2$ ... $k_n$ con $\sqrt{N} \geq k_i>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.