Foros de matemática
18/11/2017, 01:39:02 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: 1 [2]   Ir Abajo
  Imprimir  
Autor Tema: ¿Puede existir un algoritmo de factorización determinista?  (Leído 5574 veces)
0 Usuarios y 1 Visitante están viendo este tema.
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.646



Ver Perfil
« Respuesta #20 : 27/06/2016, 10:47:38 am »



Ya he probado la fórmula para números grandes y tarda; no sé cuánto, porque no tengo paciencia, pero imagino que demasiado para los RSA.

Sin embargo, la fórmula que decía funciona, es la ecuación de esta hipérbola:

[texx](\dfrac{x+\sqrt{x^{2}+4k}}{2}-x)\cdot(\dfrac{x+\sqrt{x^{2}+4k}}{2})=xy
 [/texx]

donde el número a factorizar es [texx]k=xy
 [/texx].

Las soluciones enteras vienen dadas por los divisores del número en positivo y negativo; así que para un primo, por ejemplo, tendrá soluciones [texx]1,-1,p,-p
 [/texx] (asociadas a cada una de las variables).

Aunque no sea muy práctico, al menos consiste en una fórmula cerrada; si bien el requisito que pides de las “pocas operaciones”... creo que no queda satisfecho, ya que, al ordenador le cuesta resolver la ecuación con valores un poco grandes.

Saludos.
En línea

Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 40.263


Ver Perfil
« Respuesta #21 : 28/06/2016, 05:57:14 am »

Hola


Ya he probado la fórmula para números grandes y tarda; no sé cuánto, porque no tengo paciencia, pero imagino que demasiado para los RSA.

Sin embargo, la fórmula que decía funciona, es la ecuación de esta hipérbola:

[texx](\dfrac{x+\sqrt{x^{2}+4k}}{2}-x)\cdot(\dfrac{x+\sqrt{x^{2}+4k}}{2})=xy
 [/texx]

donde el número a factorizar es [texx]k=xy
 [/texx].

Si [texx]xy=k[/texx] lo anterior es una identidad; es decir, se cumple para cualquier par de valores [texx]x,y[/texx] cuyo producto sea [texx]k.[/texx]

Si lo que quieres decir es que la factorización se encuentra a través de las soluciones enteras de esa ecuación, es cierto. Pero no hace falta complicarlo tanto: la factorización se encuentra a través de las soluciones enteras de la ecuación [texx]xy=k[/texx].

Por otra parte dar una ecuación implícita, no es dar una fórmula. Una fórmula tiene que ser una expresión del tipo [texx]x=f(k)[/texx], donde [texx]k[/texx] es el número a factorizar y [texx]x[/texx] uno de sus factores.

La mayor parte de los métodos para resolver ecuaciones implícitas son iterativos (más aun si son diofánticas), entonces en principio el dar une ecuación cuya solución es la factorización no nos deja en absoluto más cerca de tener esa factorización.

Entonces lo que deberías de hacer es especificar que método o fórmula propones para resolver esa ecuación y ahí podemos entrar a analizar.

Saludos.

P.D. Como indiqué en mi anterior intervención una fórmula directa cuando los factores de [texx]n[/texx] están suficientemente próximos a su raíz cuadrada es aplicar un sólo paso del método de Fermat es decir:

[texx]x=\lceil \sqrt{n}\rceil -\sqrt{\lceil \sqrt{n}\rceil^2-n}[/texx]
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.646



Ver Perfil
« Respuesta #22 : 28/06/2016, 06:50:39 am »


Entonces lo que deberías de hacer es especificar que método o fórmula propones para resolver esa ecuación y ahí podemos entrar a analizar.


Ahí está la cuestión; no lo sé. Yo vi que Wolfram lo resolvía pero no sé qué usa. Me di cuenta de que era una identidad despejando, claro, así que cuando la fórmula se iguala al valor del número, k el Wolfram simplemente dice “True”. Por eso lo igualé a “xy” a ver si me daba las soluciones y me las dio.

 Como en principio es una ecuación en los reales que tiene soluciones enteras cuando “k” es natural, pensé que el Wolfram podría utilizar un método que no fuera haciendo “probaturas”, lo que respondería en parte a la pregunta que hace JOSEFERM (que además se tarde poco y sean pocas operaciones ya me parece pedir gollerías). Desde luego que no es nada eficiente, tarda mucho más que poniendo divisors (k) o factorize (k); sin embargo si el programa lo hiciera sin ir probando candidatos a divisores tendría su interés, pero a tenor de lo que me dices me temo que no debe de ser así, ¿no?

Saludos.
En línea

Luis Fuentes
el_manco
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 40.263


Ver Perfil
« Respuesta #23 : 28/06/2016, 08:31:27 am »

Hola


Entonces lo que deberías de hacer es especificar que método o fórmula propones para resolver esa ecuación y ahí podemos entrar a analizar.


Ahí está la cuestión; no lo sé. Yo vi que Wolfram lo resolvía pero no sé qué usa. Me di cuenta de que era una identidad despejando, claro, así que cuando la fórmula se iguala al valor del número, k el Wolfram simplemente dice “True”. Por eso lo igualé a “xy” a ver si me daba las soluciones y me las dio.

 Como en principio es una ecuación en los reales que tiene soluciones enteras cuando “k” es natural, pensé que el Wolfram podría utilizar un método que no fuera haciendo “probaturas”, lo que respondería en parte a la pregunta que hace JOSEFERM (que además se tarde poco y sean pocas operaciones ya me parece pedir gollerías). Desde luego que no es nada eficiente, tarda mucho más que poniendo divisors (k) o factorize (k); sin embargo si el programa lo hiciera sin ir probando candidatos a divisores tendría su interés, pero a tenor de lo que me dices me temo que no debe de ser así, ¿no?

No, no debe de ser así.

En vez de semejante complicación de ecuación prueba a meterle a Wolfram simplemente la ecuación [texx]xy=k[/texx].

Saludos.
En línea
feriva
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 6.646



Ver Perfil
« Respuesta #24 : 28/06/2016, 10:32:13 am »



En vez de semejante complicación de ecuación prueba a meterle a Wolfram simplemente la ecuación [texx]xy=k[/texx].


Visto, gracias.

Saludos.
En línea

sqrmatrix
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 125


Ver Perfil
« Respuesta #25 : 29/06/2016, 07:12:33 am »

Hablando de la búsqueda de fórmulas que proporcionan la factorización de un entero [texx]\displaystyle m[/texx], hace años se me ocurrió esta fórmula:

[texx]\displaystyle \left(\sen{\left(\pi\cdot\frac{m}{x}\right)}\right)^2=0[/texx]

La idea era que, puesto que [texx]\displaystyle \sen{(x)}=0[/texx] cuando [texx]\displaystyle x[/texx] es un múltiplo entero de [texx]\displaystyle \pi[/texx], se conseguiría que [texx]\displaystyle \sen{\left(\pi\cdot\frac{m}{x}\right)}[/texx] valiera [texx]\displaystyle 0[/texx] cuando el cociente [texx]\displaystyle \frac{m}{x}[/texx] fuese entero, y esto ocurre cuando [texx]\displaystyle x[/texx] divide a [texx]\displaystyle m[/texx].

Como [texx]\displaystyle \sen{(x)}[/texx] puede tomar valores positivos y negativos, independientemente de que [texx]\displaystyle x[/texx] sea múltiplo entero de [texx]\displaystyle \pi[/texx] o no, esto supondría que obtendríamos valores [texx]\displaystyle 0[/texx] aunque [texx]\displaystyle x[/texx] no dividiera a [texx]\displaystyle m[/texx]. Elevando al cuadrado, hacemos que [texx]\displaystyle \left(\sen{\left(\pi\cdot\frac{m}{x}\right)}\right)^2[/texx] siempre tome valor positivo.

Pensaba que había encontrado una fórmula cuyas únicas soluciones eran los divisores de [texx]\displaystyle m[/texx], y pensaba que podría aplicar el método de Newton para encontrarlas. Pronto me dí cuenta de que lamentablemente ocurre que también hay soluciones para valores de [texx]\displaystyle x[/texx] que no son divisores de [texx]\displaystyle m[/texx]. En particular, cualquier valor de [texx]\displaystyle x[/texx] de la forma [texx]\displaystyle \frac{m}{k}[/texx], con [texx]\displaystyle k[/texx] entero, también es solución de la ecuación, pues [texx]\displaystyle \frac{m}{m/k}=k[/texx], siendo [texx]\displaystyle k[/texx] entero. Únicamente estaba pensando en valores enteros para [texx]\displaystyle x[/texx], y no me dí cuenta de que también existían valores no enteros de [texx]\displaystyle x[/texx] en los que la ecuación dada también tenía soluciones. Además, el método de Newton sería inaplicable para encontrar soluciones enteras, ya que lo más probable es que no encontrase ninguna solución por no converger, o que encontrase una solución no entera.

Una pena que no funcionara :sonrisa: . En todo caso, si trabajamos con valores enteros de [texx]\displaystyle x[/texx], y si no me equivoco, la ecuación sólo tiene solución cuando [texx]\displaystyle x[/texx] divide a [texx]\displaystyle m[/texx], aunque esto no aporta gran cosa a la factorización.
En línea
Páginas: 1 [2]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.1 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!