Esta respuesta se describe el algoritmo para encontrar $\phi(m)$ a partir de un par $(e,d)$, al igual que su $(e,d) = (13631, 142703)$
La copia, el uso de $N$ en lugar de su $m$ como notación para el módulo:
Calcular $k = ed-1$
Determinar el exponente de $2$, $t$, en la factorización de $k$,
es decir, el factor de $k$ en la forma $k = 2^t r$ $t > 0$ $r$ impar.
Escoge un random $x\,|\,2 \leq x < N$
Calcular la secuencia de
$s = x^{\frac k 2}, x^{\frac k 4}, \dots, x^{\frac k {2^t}} \pmod{N}$
-
Determinar el primer índice $i$ tal que $s_i \neq \pm 1$ y
$s_{i-1} = 1$
Si no existe un índice, seleccione un nuevo $x$ e inténtelo de nuevo.
De lo contrario, deje $p = \gcd(s_i - 1, N)$$q = \frac N p$.
Hecho.
Esto es posible por la mano de la calculadora para estos tamaños (puede que tenga que probar un par de $x$). Pero dado el contexto, probablemente no es lo que el profesor pretende.
Una alternativa, directamente después de la sugerencia:
Por definición de RSA: $ed = 1 \pmod{\phi(m)}$. Por lo $ed-1 $ es un múltiplo de a $\phi(m)$. Ahora para el par $(e,d)$:
$ed -1 =1945184592$ , que podemos dividir por un factor de 2,
dejando $121574037$, el cual es divisible por 3, usando el estándar de la prueba
y nos deja con $13508226$, esto resulta ser divisble por $13$ (después de intentar $7$$11$), dejando $3117283$ también divisible por $13$, y nos quedamos con $239791$. Entonces (por ejemplo, la comprobación de todos los números primos $< 100$) nos encontramos con un factor de $61$, lo que deja a $3931$ (que es primo, la comprobación de todos los números primos $\sqrt{3931}$ como divisores). Así
$$ed-1 = 2^4 \cdot 3 \cdot 13^2 \cdot 61 \cdot 3931$$ and we now we can find $\phi(m)$ because $ed-1$ happens to have a lot of small factors, and we don't have to find $\phi(m)$ by guessing it or something like that. $\phi(m)= (p-1)(q-1)$ should be divisible by $2^2$ at least (as $p,q$ are odd) and we note that $t= \frac{ed-1}{3931} = 494832$ seems a strong candidate for being $\phi(m)$ as it is $< m$ and has the same length and the same starting digits (which we expect, as $p, q$ are around size $\sqrt{m}$ so $m - \phi(m)$ is about 1400 to 1500. So we expect the first two digits to coincide, which rules out the candidates $39131 \cdot 61$ or $2 \cdot 3931 \cdot 61 = 479582$.
El algoritmo que me dio la primera siempre va a funcionar (con una probabilidad cercana a $1$), independientemente de ser capaz de factor de $ed-1$ an esto podría ser tan duro como el factoring $m$ sí. Así que este ejercicio es un poco engañoso, ya que aquí tenemos "la suerte" con nuestra $ed-1$ tener un relativamente pequeño factor de 61.
Para (b) tomar nota de que $m - \phi(m) =pq -(p-1)(q-1)$ = $p+q-1$,y el lado izquierdo es conocido como$m$$\phi(m)$. Así conocemos $p+q$ $pq$ a partir de la cual se resuelve $p$ $q$ en una forma estándar (ecuación cuadrática).
