Tema destacado: Deseas probar algunas mejoras a la interfaz del foro? Prueba cake! acerca de
 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
|
Weno y aveo k este tema es complicado... SDC, no doy compilado tu code!! un monton de errores, conseguí las librerias pero me da errores igual... buské mas codes pero no encontré nada conciso... weno pues a ver si alguien me puede ayudar... Después otra cuestión sería como hacer para realizar la factorizacion de manera d¡ distribuida...alguien sabe como? o se necesita saber el algoritmo para saber como hacer esto? Weno saludos y a ver si alguien me puede ayudar... 
|
|
|
|
|
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
|
Weno pues al final conseguí un programa y su codigo fuente, el msieve 1.30 y si mal no pienso esa es su última versión... Al ejecutar msieve.exe -h me sale esto: Msieve v. 1.30
usage: msieve [options] [one_number]
numbers starting with '0' are treated as octal,
numbers starting with '0x' are treated as hexadecimal
options:
-s <name> save intermediate results to <name>
instead of the default msieve.dat
-l <name> append log information to <name>
instead of the default msieve.log
-i <name> read one or more integers to factor from
<name> (default worktodo.ini) instead of
from the command line
-m manual mode: enter numbers via standard input
-q quiet: do not generate any log information,
only print any factors found
-d <min> deadline: if still sieving after <min>
minutes, shut down gracefully (default off)
-r <num> stop after finding <num> relations
-v verbose: write log information to screen
as well as to logfile
-t <num> use at most <num> threads
quadratic sieve options:
-c client: only perform sieving
number field sieve options:
-n use the number field sieve (97+ digits only;
performs all NFS tasks in order)
-nf <name> read from / write to NFS factor base file
<name> instead of the default msieve.fb
-np [X,Y] perform only NFS polynomial selection; if
specified, cover the range from X to Y
percent of the total polynomial search
space, inclusive (1<=X<Y<=100)
-ns [X,Y] perform only NFS sieving; if specified,
handle sieve lines X to Y inclusive
-nc perform only NFS combining (all phases)
-nc1 [X,Y] perform only NFS filtering. Filtering will
only track ideals >= X (determined automa-
tically if 0) and will only use the first Y
Y relations (or all relations if 0)
-nc2 perform only NFS linear algebra
-ncr perform only NFS linear algebra, restarting
from a previous checkpoint
-nc3 [X,Y] perform only NFS square root (compute
dependency numbers X through Y, 1<=X,Y<=64)Weno yo de momento uso msieve.exe -m <numero> -nMe gustaría saber como uso las opciones (no entiendo bien el ingles) para hacer un calculo distribuido de un numero RSA grande...uso -n porque pone use the number field sieve (97+ digits only; performs all NFS tasks in order) y supongo k kiere decir que así usa el General Number Fiel Sieve...aunke el -c tambien pone algo de eso, a ver si alguien me lo aclara...después las opciones -nc1, -nc 2 y eso no las se utilizar y no se para k sirven, ¿para k sirven? ¿Y como puedo hacer un calculo distribuido?, esa es la cuestion principal... También me interesaría saber como poder reanudar el calculo despues de apagarse el ordenador por ejemplo... Saludos
|
|
|
|
« Última modificación: 18 Noviembre 2007, 00:39 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% |
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
http://sage.math.washington.edu/home/yqiang/Software/msieve-1.21/Readme.qsEn esa pagina se dice como hacer el calculo distribuido pero la verdad esta en inglés y yo de eso nada...entendí algunas cosas con un traductor automático pero no me enteré de casi nada... A ver si alguien leyendo eso me puede ayudar. 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
|
weno solo decir que prové con el msieve a factorizar un nñumero RSA-100 que en teoría con un Opteron 2.2GHz en algo mas de 15 horas se saca...yo prové con mi AMD XP 1.76GHz y me tardó unas 130 horas mas o menos... Dejo aki el log: Mon Nov 19 00:03:31 2007
Mon Nov 19 00:03:31 2007
Mon Nov 19 00:03:31 2007 Msieve v. 1.30
Mon Nov 19 00:03:31 2007 random seeds: d1db0230 31340bab
Mon Nov 19 00:03:31 2007 factoring 1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139 (100 digits)
Mon Nov 19 00:03:32 2007 commencing number field sieve (99-digit input)
Mon Nov 19 00:03:32 2007 commencing number field sieve polynomial selection
Mon Nov 19 00:03:32 2007 time limit set to 0.34 hours
Mon Nov 19 00:23:54 2007 polynomial selection complete
Mon Nov 19 00:23:54 2007 R0: -90090659319219610
Mon Nov 19 00:23:54 2007 R1: 1
Mon Nov 19 00:23:54 2007 A0: -236693752426701
Mon Nov 19 00:23:54 2007 A1: 1218856810757904
Mon Nov 19 00:23:54 2007 A2: -498495660635766
Mon Nov 19 00:23:54 2007 A3: -1007162657451726
Mon Nov 19 00:23:54 2007 A4: 1181612609417695
Mon Nov 19 00:23:54 2007 A5: 256559696537760
Mon Nov 19 00:23:54 2007 size score = 1.747374e-010, Murphy alpha = -3.961502, combined = 6.544435e-010
Mon Nov 19 00:23:54 2007 generating factor base
Mon Nov 19 00:23:57 2007 factor base complete:
Mon Nov 19 00:23:57 2007 150825 rational roots (max prime = 2027269)
Mon Nov 19 00:23:57 2007 150678 algebraic roots (max prime = 2027269)
Mon Nov 19 00:23:57 2007 a range: [-5818182, 5818182]
Mon Nov 19 00:23:57 2007 b range: [1, 4294967295]
Mon Nov 19 00:23:57 2007 number of hash buckets: 31
Mon Nov 19 00:23:57 2007 sieve block size: 65536
Mon Nov 19 00:23:57 2007
Mon Nov 19 00:23:57 2007 maximum RFB prime: 2027269
Mon Nov 19 00:23:57 2007 RFB entries: 150825
Mon Nov 19 00:23:57 2007 medium RFB entries: 6542
Mon Nov 19 00:23:57 2007 resieved RFB entries: 6374
Mon Nov 19 00:23:57 2007 small RFB prime powers: 28
Mon Nov 19 00:23:57 2007 projective RFB roots: 0
Mon Nov 19 00:23:57 2007 RFB trial factoring cutoff: 54 bits
Mon Nov 19 00:23:57 2007 single large prime RFB range: 21 - 26 bits
Mon Nov 19 00:23:57 2007 double large prime RFB range: 42 - 49 bits
Mon Nov 19 00:23:57 2007
Mon Nov 19 00:23:57 2007 maximum AFB prime: 2027269
Mon Nov 19 00:23:57 2007 AFB entries: 150678
Mon Nov 19 00:23:57 2007 medium AFB entries: 6448
Mon Nov 19 00:23:57 2007 resieved AFB entries: 6243
Mon Nov 19 00:23:57 2007 small AFB prime powers: 56
Mon Nov 19 00:23:57 2007 projective AFB roots: 7
Mon Nov 19 00:23:57 2007 AFB trial factoring cutoff: 54 bits
Mon Nov 19 00:23:57 2007 single large prime AFB range: 21 - 26 bits
Mon Nov 19 00:23:57 2007 double large prime AFB range: 42 - 49 bits
Mon Nov 19 00:23:57 2007
Sat Nov 24 09:02:40 2007 completed b = 368013, found 3723754 relations
Sat Nov 24 09:02:41 2007 factor base loaded:
Sat Nov 24 09:02:41 2007 150825 rational ideals (max prime = 2027269)
Sat Nov 24 09:02:41 2007 150678 algebraic ideals (max prime = 2027269)
Sat Nov 24 09:02:41 2007 added 1249 free relations
Sat Nov 24 09:02:42 2007
Sat Nov 24 09:02:42 2007 commencing relation filtering
Sat Nov 24 09:02:42 2007 commencing duplicate removal, pass 1
Sat Nov 24 09:04:10 2007 found 26113 hash collisions in 3725003 relations
Sat Nov 24 09:04:10 2007 commencing duplicate removal, pass 2
Sat Nov 24 09:05:20 2007 found 0 duplicates and 3725003 unique relations
Sat Nov 24 09:05:20 2007 memory use: 36.9 MB
Sat Nov 24 09:05:22 2007 ignoring smallest 168314 rational and 168184 algebraic ideals
Sat Nov 24 09:05:22 2007 filtering ideals above 2282312
Sat Nov 24 09:05:22 2007 need 572046 more relations than ideals
Sat Nov 24 09:05:22 2007 commencing singleton removal, pass 1
Sat Nov 24 09:07:14 2007 relations with 0 large ideals: 76255
Sat Nov 24 09:07:14 2007 relations with 1 large ideals: 581215
Sat Nov 24 09:07:14 2007 relations with 2 large ideals: 1423171
Sat Nov 24 09:07:14 2007 relations with 3 large ideals: 1306179
Sat Nov 24 09:07:14 2007 relations with 4 large ideals: 338183
Sat Nov 24 09:07:14 2007 relations with 5 large ideals: 0
Sat Nov 24 09:07:14 2007 relations with 6 large ideals: 0
Sat Nov 24 09:07:14 2007 relations with 7+ large ideals: 0
Sat Nov 24 09:07:14 2007 3725003 relations and about 3712493 large ideals
Sat Nov 24 09:07:14 2007 commencing singleton removal, pass 2
Sat Nov 24 09:09:44 2007 found 1846983 singletons
Sat Nov 24 09:09:44 2007 current dataset: 1878020 relations and about 1509395 large ideals
Sat Nov 24 09:09:44 2007 commencing singleton removal, pass 3
Sat Nov 24 09:11:59 2007 found 358081 singletons
Sat Nov 24 09:12:00 2007 current dataset: 1519939 relations and about 1124297 large ideals
Sat Nov 24 09:12:00 2007 commencing singleton removal, final pass
Sat Nov 24 09:13:42 2007 memory use: 51.4 MB
Sat Nov 24 09:13:42 2007 commencing in-memory singleton removal
Sat Nov 24 09:13:43 2007 begin with 1519939 relations and 1153504 unique ideals
Sat Nov 24 09:13:46 2007 reduce to 1287371 relations and 914681 ideals in 15 passes
Sat Nov 24 09:13:46 2007 max relations containing the same ideal: 16
Sat Nov 24 09:13:46 2007 dataset has 10.8% excess relations
Sat Nov 24 09:13:48 2007 ignoring smallest 152663 rational and 152437 algebraic ideals
Sat Nov 24 09:13:48 2007 filtering ideals above 2054080
Sat Nov 24 09:13:48 2007 need 363417 more relations than ideals
Sat Nov 24 09:13:48 2007 commencing singleton removal, final pass
Sat Nov 24 09:15:30 2007 memory use: 51.4 MB
Sat Nov 24 09:15:30 2007 commencing in-memory singleton removal
Sat Nov 24 09:15:30 2007 begin with 1519939 relations and 1184451 unique ideals
Sat Nov 24 09:15:34 2007 reduce to 1281191 relations and 939189 ideals in 15 passes
Sat Nov 24 09:15:34 2007 max relations containing the same ideal: 16
Sat Nov 24 09:15:34 2007 dataset has 1.6% excess relations
Sat Nov 24 09:15:34 2007 relations with 0 large ideals: 62457
Sat Nov 24 09:15:34 2007 relations with 1 large ideals: 287841
Sat Nov 24 09:15:34 2007 relations with 2 large ideals: 511207
Sat Nov 24 09:15:34 2007 relations with 3 large ideals: 345302
Sat Nov 24 09:15:34 2007 relations with 4 large ideals: 74384
Sat Nov 24 09:15:34 2007 relations with 5 large ideals: 0
Sat Nov 24 09:15:34 2007 relations with 6 large ideals: 0
Sat Nov 24 09:15:34 2007 relations with 7+ large ideals: 0
Sat Nov 24 09:15:34 2007 commencing 2-way merge
Sat Nov 24 09:15:36 2007 reduce to 742971 relation sets and 400999 unique ideals
Sat Nov 24 09:15:36 2007 ignored 30 oversize relation sets
Sat Nov 24 09:15:36 2007 commencing full merge
Sat Nov 24 09:15:46 2007 found 351227 cycles, need 324800
Sat Nov 24 09:15:46 2007 weight of 324800 cycles is about 19847633 (61.11/cycle)
Sat Nov 24 09:15:46 2007 distribution of cycle lengths:
Sat Nov 24 09:15:46 2007 1 relations: 62795
Sat Nov 24 09:15:46 2007 2 relations: 38628
Sat Nov 24 09:15:46 2007 3 relations: 33745
Sat Nov 24 09:15:46 2007 4 relations: 28203
Sat Nov 24 09:15:46 2007 5 relations: 25142
Sat Nov 24 09:15:46 2007 6 relations: 21709
Sat Nov 24 09:15:46 2007 7 relations: 18947
Sat Nov 24 09:15:46 2007 8 relations: 16502
Sat Nov 24 09:15:46 2007 9 relations: 14565
Sat Nov 24 09:15:46 2007 10+ relations: 64564
Sat Nov 24 09:15:46 2007 heaviest cycle: 20 relations
Sat Nov 24 09:15:46 2007 commencing cycle optimization
Sat Nov 24 09:15:47 2007 start with 1833422 relations
Sat Nov 24 09:15:55 2007 pruned 40259 relations
Sat Nov 24 09:15:55 2007 distribution of cycle lengths:
Sat Nov 24 09:15:55 2007 1 relations: 62795
Sat Nov 24 09:15:55 2007 2 relations: 39076
Sat Nov 24 09:15:55 2007 3 relations: 34544
Sat Nov 24 09:15:55 2007 4 relations: 28640
Sat Nov 24 09:15:55 2007 5 relations: 25687
Sat Nov 24 09:15:55 2007 6 relations: 22099
Sat Nov 24 09:15:55 2007 7 relations: 19414
Sat Nov 24 09:15:55 2007 8 relations: 16787
Sat Nov 24 09:15:55 2007 9 relations: 14738
Sat Nov 24 09:15:55 2007 10+ relations: 61020
Sat Nov 24 09:15:55 2007 heaviest cycle: 20 relations
Sat Nov 24 09:15:57 2007
Sat Nov 24 09:15:57 2007 commencing linear algebra
Sat Nov 24 09:15:57 2007 read 324800 cycles
Sat Nov 24 09:15:59 2007 cycles contain 1016949 unique relations
Sat Nov 24 09:17:35 2007 read 1016949 relations
Sat Nov 24 09:17:48 2007 using 32 quadratic characters above 67102460
Sat Nov 24 09:19:02 2007 read 324800 cycles
Sat Nov 24 09:19:23 2007 matrix is 322903 x 324800 with weight 28970681 (avg 89.20/col)
Sat Nov 24 09:19:46 2007 filtering completed in 3 passes
Sat Nov 24 09:19:47 2007 matrix is 311163 x 311361 with weight 27801593 (avg 89.29/col)
Sat Nov 24 09:20:07 2007 read 311361 cycles
Sat Nov 24 09:20:42 2007 matrix is 311163 x 311361 with weight 27801593 (avg 89.29/col)
Sat Nov 24 09:20:42 2007 saving the first 48 matrix rows for later
Sat Nov 24 09:20:43 2007 matrix is 311115 x 311361 with weight 20883557 (avg 67.07/col)
Sat Nov 24 09:20:43 2007 matrix includes 64 packed rows
Sat Nov 24 09:20:43 2007 using block size 10922 for processor cache size 256 kB
Sat Nov 24 09:20:47 2007 commencing Lanczos iteration
Sat Nov 24 10:02:18 2007 lanczos halted after 4921 iterations (dim = 311104)
Sat Nov 24 10:02:34 2007 recovered 39 nontrivial dependencies
Sat Nov 24 10:02:51 2007
Sat Nov 24 10:02:51 2007 commencing square root phase
Sat Nov 24 10:02:52 2007 reading relations for dependency 1
Sat Nov 24 10:03:35 2007 read 155474 cycles
Sat Nov 24 10:03:35 2007 cycles contain 602458 unique relations
Sat Nov 24 10:05:20 2007 read 602458 relations
Sat Nov 24 10:05:27 2007 multiplying 862978 relations
Sat Nov 24 10:16:13 2007 multiply complete, coefficients have about 58.08 million bits
Sat Nov 24 10:17:05 2007 initial square root is modulo 218255617
Sat Nov 24 10:42:31 2007 prp50 factor: 37975227936943673922808872755445627854565536638199
Sat Nov 24 10:42:31 2007 prp50 factor: 40094690950920881030683735292761468389214899724061
Sat Nov 24 10:42:31 2007 elapsed time 130:39:00
Weno solo eso, yo sigo mirando, y si alguien kiere ayudar ya sabe... 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% |
|
|
|
darkraider
Desconectado
Mensajes: 229
|
Hola buenas. En cuanto al mejor algrotimo, no puedo aportar nada. Pero de computación distribuída, creo que si.
Me acorde de que habia leido uno de los articulos de la revista Arroba (esos en los que el personaje suele ser INGENIERO), sobre el tema. Estuve revisando la pila de arrobas y la encontré. Es el numero 115 de la revista. Si lo tenes o lo podes conseguir leetelo porque creo que ahi decía algo sobre como montar una red de computacion distribuída con una plataforma java, o algo por el estilo.
La verdad es que me lo voy a volver a leer mañana (proque tengo examen y hoy tengo que estudiar) y si no encontraste nada de utilidad, te lo cuento o te escaneo el articulo y te lo mando.
Salu2
|
|
|
|
|
En línea
|
Curioso de mi...
|
|
|
nhaalclkiemr
Desconectado
Mensajes: 1.666
Máximo exponente 9DB9F1AEED2FADBDE 997BBE20FEDA92
|
Weno pues buské pero no encuentro nada... Sobre el algorítmo ya verifiqué que si que es ese, el GNFS...solo el SNFS es mas rapido para un numero de numeros especiales pero para los RSA el mejor es el método general que es el GNFS... Pues si pudieras pasarme esa información te lo agradecería mucho... 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% |
|
|
|
darkraider
Desconectado
Mensajes: 229
|
Muy buenas a todos. Lo prometido y es deuda, y por si a alguien le intriga mi examen, me fue bien  Al tajo: resulta que para la computación distribuida se han creado unos proyectos de comunidad, en los que los integrantes de la comunidad "ceden" sus tiempos muertos de CPU para la misma. Trabaja como un P2P; de todos para todos. En cambio, la comunidad ofrece potencia para realizar calculos. Al parecer este tipo de redes estan administradas por unos servidores dedicados a administrar las tareas a ejecutar y asignarlas a clientes espcíficos y segun el articulo llegan a los 15 TetraFLOPS (se habran pasado). Este tipo de computación distribuida es útil en calculos en los que el volumen de datos no sea grande, ya que la informacion va por internet. Ahora a la referencia: www.globalgridexchange.com/index.jsp . Desde esta pagina se puede encontrar una comunidad del estilo. Solo hace falta instalarse el demonio, y si se quieren programar tareas, se hace en java. Al parecer viene con ejemplos, y bien documentado. Como te dije antes, lo vi en Arroba, si te interesa el articulo entero lo escaneo. Pero por tanto no lo he probado, pero de los articulos de INGENIERO, me fio (sera un quinto sentido  ). Bueno, espero que te sirva. Salu2 Edito: mas referencias: www.globus.orgwww.parabon.comwww.distributed.netwww.eu-datagrid.org |
|
|
|
« Última modificación: 27 Noviembre 2007, 10:50 por darkraider »
|
En línea
|
Curioso de mi...
|
|
|
|
|
|
 |
