El estándar de criptografía de respuesta para este tipo de problema es el uso de algún tipo de homomórfica de cifrado. Homomórfica de cifrado permite cifrar de entrada de tal manera que un tercero puede realizar cálculos sobre él (pero no es capaz de leer los resultados de estos cálculos sin romper el cifrado).
Un ejemplo tonto de esto es que si usted desea conseguir un tercero para realizar algunas operaciones de multiplicación para usted (es decir multiplicar $a$$b$), puede cifrar sus valores a través de RSA, enviarle $a^{e}$$b^{e}$, se multiplica los valores de cifrado para obtener $(ab)^{e}$ y lo envía de vuelta, en la que puede recuperarse $(ab)$ mediante el cálculo de $(ab)^{de}$ (todas las operaciones que se realicen modulo algunos semiprime $n$). Por supuesto, la realización de cualquiera de estos cifrado/descifrado de pasos que se requieren varias operaciones de multiplicación, pero usted se pueda imaginar, este posiblemente sea útil si usted quería saber el producto de un millón de números. De equipo de científicos ahora saben cómo realizar plenamente homomórfica de cifrado en el polinomio de tiempo, lo que significa que hay métodos para cifrar las cosas que permiten que la tercera parte no sólo de multiplicarse, sino también añadir, comparar, y en general realizar arbitraria de la computación. Usted podría utilizar este método para este problema.
Yo creo que estos métodos no son lo suficientemente rápido como para ser utilizado en la práctica, sin embargo. Usted podría esperar de un simple tipo de construcción como en su construcción para encontrar un ciclo Hamiltoniano. No estoy seguro de si alguien ha pensado en esto antes, pero aquí es un método que puede funcionar.
Uno de los métodos más rápidos para la factorización de números enteros es a través del General de Campo de Número de Tamiz. Este algoritmo es un poco complicado, pero se puede resumir de la siguiente manera (ver el artículo de la Wikipedia para una descripción más exacta):
- Generar dos (grado $d$) polinomios $f(x)$ $g(x)$ tal que $f$ $g$ son irreducibles sobre los racionales, pero tienen una raíz común, $m$ modulo $n$.
- Repetidamente elegir enteros $a$ $b$ y calcular el $r = b^d f(a/b)$$s = b^d g(a/b)$. Si $r$ $s$ ambos $B$-suave (es decir, todos sus factores primos son en la mayoría de las $B$), a continuación, almacenar este par (junto con los asociados $a$$b$) para más tarde ($B$ es un parámetro que depende de la $n$ en algunos de manera simple).
- El uso de eliminación Gaussiana (o algunos lineales dispersos solver) para encontrar un subconjunto de pares $(r_1, s_1), \dots (r_k, s_k)$ tal que $r_1r_2\dots r_k$ $s_1s_2\dots s_k$ son ambos cuadrados (técnicamente, usted necesita un poco más fuerte que el de la condición, pero esto es una simplificación razonable).
- Resulta que $r_i$ es la norma de la $a_i + \alpha b_i$ $\mathbb{Z}[\alpha]$ donde $\alpha$ es una raíz de $f$$\mathbb{C}$. Del mismo modo, $s_i$ es la norma de la $a_i + \beta b_i$ $\mathbb{Z}[\beta]$ donde $\beta$ es una raíz de $g$. Si $r_1r_2\dots r_k$ es un cuadrado (más que otros más fuertes de la enfermedad), entonces esto implica que hay un elemento $x \in \mathbb{Z}[\alpha]$$x^2 = r_1r_2\dots r_k$, y un elemento $y \in \mathbb{Z}[\beta]$$y^2 = s_1s_2\dots s_k$. No se conocen métodos para calcular estos $x$$y$.
- Desde $f$ $g$ ambos tienen una raíz $m$ modulo $n$, existen dos homomorphisms $u: \mathbb{Z}[\alpha] \rightarrow \mathbb{Z}/n\mathbb{Z}$ $v: \mathbb{Z}[\beta] \rightarrow \mathbb{Z}/n\mathbb{Z}$ que acaba de enviar a$\alpha$$\beta$, respectivamente, a $m$. Entonces, si dejamos $C = \prod (a_i + mb_i) \bmod n$,$u(x)^2 = C \bmod n$$v(y)^2 = C \bmod n$. Si $u(x)$ $v(y)$ son iguales (o negativos de cada uno de los otros), esto no nos dice nada, pero de lo contrario, esto nos permite factorizar $n$. En promedio, esto ocurrirá con una probabilidad de alrededor de $1/2$.
Para tu pregunta, la cosa importante de comida para llevar de esto es que la única pasos de este procedimiento en el que es realmente importante saber $n$ son los pasos a$1$$5$, y estos pasos son relativamente cómputo de la luz. Realizar los pasos $2$, $3$, y $4$ sólo requieren un conocimiento de $f$ $g$ (y tal vez el tamaño aproximado de $n$, para establecer parámetros como la $B$).
Entonces la pregunta es, si estos esbirros saber $f$$g$, pueden averiguar $n$? No estoy seguro de la respuesta a este. Si conocen a $m$, entonces se puede calcular el $f(m)$$g(m)$, tanto de los que son divisibles por $n$ (por lo que probablemente su mcd será, básicamente, dar $n$). Sin embargo, parece que se puede construir a $f$ $g$ de tal manera que es difícil encontrar a $m$ (por decir, elegir al azar grado $d$ polinomios y ajuste de la constante de plazo para que las $m$ es una raíz modulo $n$). No sé si hay algún estándar de la dureza de la suposición de que da esto.
Por último, hay implícito un segundo componente a su pregunta, que es que tiene un ejército de esbirros en lugar de sólo uno. Esto sugiere también puede ser que desee un problema que paraleliza bien. Por suerte, el paso 2 anterior (probablemente el más pesado computacionalmente paso) es altamente parallelizable, así que usted puede dividir el trabajo entre muchos esbirros fácilmente. Si usted piensa que sus súbditos no concuerdan, entonces hay algunos enfoques adicionales para ganar algo de privacidad a través de dividir el problema entre ellos, de manera que ningún individuo subordinado puede aprender mucho sobre el problema (por ejemplo, algo así como dar sólo $f$ a la mitad de los esbirros y sólo $g$ a la mitad de los secuaces); esto es probablemente vale la pena pensar.
