Dos números que comparten un factor primo desconocido. Encuentra un método para factorizar rápidamente ambos números.

X y y son dos números que comparten un factor primo. No sabes cuál es el factor primo. Explique cómo se puede factorizar X y y rápidamente. Demuestra que funciona usando X = 41685823 y y = 39034579 .

Realmente no sé cómo abordar esta pregunta porque compartir un factor primo, ¿significa que también pueden compartir otros factores? ¡Cualquier ayuda sería espléndida! Salud.

Editar: Aparentemente, un compañero de clase dijo que los dos primos son primos consecutivos. Tal vez esto aclare la pregunta. ¡Gracias!

pista: cálculo mcd
Si X y y comparten un divisor común, X − y y X + y también comparten ese divisor común y pueden ser más fáciles de factorizar, al menos para eliminar algunos de los divisores más pequeños.
LOL, soy estudiante en UofWaterloo y tengo una clase de Math135. Creo que probablemente seas uno de mis compañeros de clase. De todos modos, no entendí la forma correcta de resolver la pregunta. Pero estoy seguro de que no es tan simple como usar el algoritmo de Euclid, ya que la pregunta requería usar RSA y requería que encontráramos una manera de resolverlo rápidamente. Mientras tanto, la pregunta da la condición de que tanto N1 como N2 tienen y solo tienen dos factores primos.

Respuestas (1)

Puedes usar el algoritmo de Euclides para encontrar el máximo común divisor, que dividirá el número primo. Si te dan eso X y y son semiprimos, que cada uno tiene solo dos factores primos, puedes dividirlos por el MCD y tener la factorización. Los números de ejemplo que tiene cumplen con este criterio, pero no lo veo en la declaración del problema. Si X y y cada uno tenía cuatro factores primos grandes y compartía dos de ellos, el MCD sería el producto de los dos factores compartidos y el resto sería el producto de los otros dos. Esa es una factorización, pero no completa.

No estoy muy seguro de seguir. Tiene razón en que mis dos números dados en la pregunta no los especifican como semiprimos, por lo que estoy confundido sobre cuál es la mejor manera de hacer esta pregunta. ¿Debo tratar la pregunta como semi números primos o puedo simplemente elegir qué número primo quiero?
Todavía factorizando X GRAMO C D , y GRAMO C D y GRAMO C D es la mayoría de las veces mucho más fácil que factorizar X , y ...
Le pregunté a uno de mis compañeros de clase y la pregunta cambió a que tienen números primos consecutivos que los tienen en cuenta. ¿Eso cambia la pregunta para que sea más clara y resoluble? Gracias1
@Michael: no importa si los primos son consecutivos, solo cuántos hay. Si son aproximadamente del mismo tamaño, en lugar de factorizar X estás factorizando algo sobre X , por lo que si está haciendo una división de prueba, ahora debe subir a X 1 4 en lugar de X 1 2 . Este es el punto del comentario de NS.
@Michael, siga los consejos que le han dado y aplique el algoritmo euclidiano a los dos números. Son solo un puñado (OK, que sean dos) de divisiones euclidianas.
Dos números que comparten un factor primo desconocido. Encuentra un método para factorizar rápidamente ambos números.
RespuestasAquíPolítica de privacidad1y, 0v