Tema destacado: Entra al canal IRC oficial de #elhacker.net
 Autor
|
Tema: Algoritmo más rápido actualmente para factorizar un número (Leído 13,382 veces)
|
nhaalclkiemr
 Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
Pues eso, cual es el algoritmo más rápido actualmente para factorizar un número?? Segun tengo entendido es el NFS (Criba Numerica Especial)...mi idea es crear el código más rápido que exista para factorizar un número...el code habría que traducirlo despues a ASM pero weno de momento eso...cual es el método más rápido para factorizar un número actualmente? Saludos 
|
|
|
|
|
En línea
|
| StasFodidoCrypter 1.0 - 100% (old) | | StasFodidoCrypter 2.0 - 85% (deserted) | | Fire AV/FW-Killer - 97% (deserted) | | R-WlanXDecrypter 0.9- 100% |
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
Ya lo encontré, era el Generic number field sieve (GNFS) http://en.wikipedia.org/wiki/General_number_field_sievegeneral number field sieve (GNFS) is the most efficient algorithm known for factoring integers larger than 100 digits. Heuristically, its complexity for factoring an integer n is of the form Al parecer la formula es esta:  Como no entiendo nada de la formula a ver si consigo algun codigo en ASM o C que la utilice...si teneis algun tipo de informacion os ayudaría... Saludos
|
|
|
|
|
En línea
|
| StasFodidoCrypter 1.0 - 100% (old) | | StasFodidoCrypter 2.0 - 85% (deserted) | | Fire AV/FW-Killer - 97% (deserted) | | R-WlanXDecrypter 0.9- 100% |
|
|
|
|
|
|
ghastlyX
|
Sobre como programarlo no te puedo ayudar, mis conocimientos matemáticos por el momento no son suficientes, pero estoy realizando un trabajo sobre criptografía y en efecto el algoritmo no cuántico más rápido de factorización es ese, pero eso que pones no es la fórmula, sino su complejidad, expresada en forma O y en L. Pero te advierto que para números grandes no te servirá, puesto que su complejidad es exponencial. Un saludo de ghastlyX |
|
|
|
|
En línea
|
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
Entonces reformulo mi pregunta...cual sería el algoritmo mas rápido para calcular numeros primos grandes ?? Basicamente lo k quiero es calcular numeros primos RSA... Con lo de la formula me deví ekivocar, se algo de matemáticas pero poco...lo k se da asta 2º de bach  Saludos |
|
|
|
|
En línea
|
| StasFodidoCrypter 1.0 - 100% (old) | | StasFodidoCrypter 2.0 - 85% (deserted) | | Fire AV/FW-Killer - 97% (deserted) | | R-WlanXDecrypter 0.9- 100% |
|
|
|
|
ghastlyX
|
No me has comprendido, no es que en función de si el número sea más grande o más pequeño el algoritmo sea mejor o peor. Ese algoritmo es el más rápido para factorizar CUALQUIER número (sea grande o pequeño), lo que te quería decir es que tanto este algoritmo como el resto de algoritmos clásicos tienen complejidades exponenciales (si te fijas son todos O(exp())) y por lo tanto, a medida que el número va aumentando, la complejidad es mucho mayor, puesto que las exponenciales crecen muy rápido. Si buscas usarlo para RSA, no te va a servir porque hablamos de números enormes. RSA sólo tiene dos focos de peligro que yo conozca: la computación cuántica con el algoritmo de Shor (complejidad logarítmica) y la demostración de la hipótesis de Riemann. Estas dos vías permitirían factorizar RSA en tiempos polinómicos, pero los ordenadores cuánticos aún no existen útilmente (vale que han hecho ordenadores cuánticos de hasta más de 10 qubits que utilizaron para comprobar que el algoritmo de Shor era correcto, pero lo comprobaron con el número 15... aún están lejos de poder atacar un RSA) y la hipótesis de Riemann no está demostrada (lleva unos cuantos añitos así xDD). Yo también hago 2º BACH, por eso decía que no te podía ayudar con el algoritmo, no tengo aún conocimientos suficientes  Un saludo de ghastlyX |
|
|
|
|
En línea
|
|
|
|
sirdarckcat
Troll Buena Onda y
CoAdmin
Desconectado
Mensajes: 6.947
Lavando Platos
|
aver, si quieres encontrar numeros primos, el proceso es diferente a factorizar. Puedes factorizar usando curvas elípticas, hasta cierto punto es mas rápida que muchos otros algoritmos.. pero no es muy optimo para numeros demasiado grandes. Pero si quieres encontrar numeros primos muy muy grandes, puedes hacer una combinacion de la criba de atkin con el teorema de los primos de fibonacci, que f(x) donde x es primo de fibonacci, da como resultado otro primo. en fin, la criba de atkin es muy usada para calcular primos grandes implementada en C esta aqui: http://cr.yp.to/primegen.htmlpuedes hacer un cpu-memory xchnge, y empezar desde cierto numero a calcular primos, y solo le dejas limites.. en fin.. Saludos!! |
|
|
|
|
En línea
|
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
Gracias, yo lo k quiero noes encontrar numeros primos, sino factorizar numeros primos muy grandes...lo k quiero basicamente es factorizar un numero RSA...y por eso necesito el algoritmo mas rapido para factorizar un numero RSA... Gracias de todas maneras, miraré lo k tu dices...pero dejo aclarado k lo k quiero es el mejor algoritmo para factorizar un numero grande (RSA) Preferiblemente uno en el kpudiera hacer un calculo usando varias computadoras, es decir, usando por ejemplo 10 oredenadores k dispongo poder usarlos todos en conjunto Saludos |
|
|
|
|
En línea
|
| StasFodidoCrypter 1.0 - 100% (old) | | StasFodidoCrypter 2.0 - 85% (deserted) | | Fire AV/FW-Killer - 97% (deserted) | | R-WlanXDecrypter 0.9- 100% |
|
|
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
Gracias por el code, pero es el algoritmo k decia yo no? el GNFS no? sirve entonces o no? es k GhastlyX decí k ese algoritmo no sirve para calcular numeros primos grandes (RSA) pork su complejidad es exponencial...entonces sirve o no? Gracias y saludos |
|
|
|
|
En línea
|
| StasFodidoCrypter 1.0 - 100% (old) | | StasFodidoCrypter 2.0 - 85% (deserted) | | Fire AV/FW-Killer - 97% (deserted) | | R-WlanXDecrypter 0.9- 100% |
|
|
|
sirdarckcat
Troll Buena Onda y
CoAdmin
Desconectado
Mensajes: 6.947
Lavando Platos
|
Pues si sirve.. pero te vas a tardar años jajaja
ningun algoritmo va a tardar menos de lo que tardas en hacer el recorrido a X numero, en eso se basa la seguridad de RSA, en que no puedas factorizar el numero.. si fuera facil, pues no sería tanto problema.
Si traduces el codigo a COBOL, podría poner una mainframe Z9 (t-rex) a tratar de factorizarlo por 1 smana pero dudo que lo logre..
Saludos!!
|
|
|
|
|
En línea
|
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
Si traduces el codigo a COBOL, podría poner una mainframe Z9 (t-rex) a tratar de factorizarlo por 1 smana pero dudo que lo logre.. No se ese lenguaj, y no tengo ni la mas minima idea de que es eso de Z9...pero la verdad me sorprende k (sea lo k sea eso) puedas factorizarlo en 1 semana  lo de que tardaría años ya lo sé...en eso se basa la seguridad RSA como tu dices...y una cosa, no habría manera de hacer una factorizacion de un numero RSA de manera distribuida, de manera k si yo dispongo de 100 ordenadores en vez de tardar años tardase años/100 ???   Supongo que me entenderías, sería hacer un calculo de factorizacioin de un numero RSA usando varios ordenadores, sería posible?? y como se implementaría eso? Weno gracias y saludos
|
|
|
|
|
En línea
|
| StasFodidoCrypter 1.0 - 100% (old) | | StasFodidoCrypter 2.0 - 85% (deserted) | | Fire AV/FW-Killer - 97% (deserted) | | R-WlanXDecrypter 0.9- 100% |
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
he incluido los include pero me da un error al compilar, soy muy novato en C...me pone k eh.h es solo para C++...pero si el code viene para C...a ver si alguien me puede ayudar Saludos P.D.: Uso Visual C, voy a provar co nDev-C |
|
|
|
|
En línea
|
| StasFodidoCrypter 1.0 - 100% (old) | | StasFodidoCrypter 2.0 - 85% (deserted) | | Fire AV/FW-Killer - 97% (deserted) | | R-WlanXDecrypter 0.9- 100% |
|
|
|
sirdarckcat
Troll Buena Onda y
CoAdmin
Desconectado
Mensajes: 6.947
Lavando Platos
|
eah yo no dije que terminaria en 1 semana, dije que lo podia meter 1 semana a ver hasta donde llega jaja.. si se puede hacer que el algoritmo quede para computo distribuido, montando un servidor que vaya guardando las tablas.. pero seria complicado la verdad.. porcierto, Z9 = http://www-03.ibm.com/systems/z/z9bc/ |
|
|
|
« Última modificación: 29 Octubre 2007, 01:04 por sirdarckcat »
|
En línea
|
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
Gracias por las aclaraciones... si se puede hacer que el algoritmo quede para computo distribuido, montando un servidor que vaya guardando las tablas.. pero seria complicado la verdad.. Pues me interesa  ...que tipos de tablas se tienen que hacer? Es que para computo distribuido por ejemplo para un hash con fuerza bruta es muy facil pork puedes decirle a cada ordenador desde que sitio asta donde...pero como se podría hacer como tu dices con tablas?? Tu idea sería por ejemplo una tabla con distintos valores (no tengo ni idea de como) e ir cada ordenador cojiendo una? o algo parecido? Weno si puedes por favor ayudame con eso del cmpto distribuido k esto me interesa y tu pareces saber como hacerlo, gracias y saludos P.D.: Ya se que no viene a cuento pero me acabo de acordar...al final conseguiste hacer el elevador de privilegios ese que me dijiste? |
|
|
|
« Última modificación: 29 Octubre 2007, 15:20 por nhaalclkiemr »
|
En línea
|
| StasFodidoCrypter 1.0 - 100% (old) | | StasFodidoCrypter 2.0 - 85% (deserted) | | Fire AV/FW-Killer - 97% (deserted) | | R-WlanXDecrypter 0.9- 100% |
|
|
|
|
 |
