OPERACIONES MODULARES Y FACTORIZACION

Actividades[pic 1]

Operaciones modulares y factorización

Descripción

• Software:

• Fortaleza de Cifrados: http://www.criptored.upm.es/software/sw_m001e.htm
• Msieve153:

• Cálculo de inversos. Con Fortaleza de Cifrados encuentra los siguientes inversos multiplicativos:

• inv (17, 27); b) inv (18, 231); c) inv (210, 2431) d) inv (65537, 876931508).

• Factorización de un número n = p*q. Con Msieve153, factoriza estos 6 números compuestos de 200, 220, 240, 260, 280 y 300 bits:

825978003848998898312024716822625570154718240569348268118339

998953628399715298831992911290285452859887456062283192823882161683

1608732996831216508159277659952021701799674006235398744155288667343172997

1354543287778399153166979461113793173551214783618259618960560750495486103455301

1473581925762428348880838685007956586120125158907213652820145423054427928545607960997

1641198470486892624720223721055575805086956302357294324019878360042573969740363472454309613

Metodología

Una vez realizados los pasos anteriores debes encontrar el tiempo que tarda el programa y hacer una gráfica de «tiempo versus bits».

Entrega

Para realizar la entrega, sube a la plataforma únicamente el documento Pdf con los resultados.

CÁLCULOS CON FORTALEZA DE CIFRADOS

• Cálculo de inversos. Con Fortaleza de Cifrados encuentra los siguientes inversos multiplicativos:

1. inv (17, 27);  

• R. (8)

1. inv (18, 231);

• R. (Los números no son primos relativos)

1. inv (210, 2431) ;

• R. (683)

1. inv (65537, 876931508);

• R. (661569001)

CÁLCULOS CON Msieve153

• Factorización de un número n = p*q. Con Msieve153, factoriza estos 6 números compuestos de 200, 220, 240, 260, 280 y 300 bits:

1. 825978003848998898312024716822625570154718240569348268118339

• Msieve v. 1.53 (SVN 1005)

random seeds: 1cd69b50 d380bdee

factoring 825978003848998898312024716822625570154718240569348268118339 (60 digits)

searching for 15-digit factors

commencing quadratic sieve (60-digit input)

using multiplier of 11

using generic 32kb sieve core

sieve interval: 4 blocks of size 32768

processing polynomials in batches of 51

using a sieve bound of 59729 (3000 primes)

using large prime bound of 2986450 (21 bits)

using trial factoring cutoff of 22 bits

polynomial 'A' values have 8 factors

restarting with 1420 full and 15604 partial relations

3320 relations (1420 full + 1900 combined from 15604 partial), need 3096

begin with 17024 relations

reduce to 4969 relations in 2 passes

attempting to read 4969 relations

recovered 4969 relations

recovered 4529 polynomials

attempting to build 3320 cycles

found 3320 cycles in 1 passes

distribution of cycle lengths:

   length 1 : 1420

   length 2 : 1900

largest cycle: 2 relations

matrix is 3000 x 3320 (0.4 MB) with weight 89533 (26.97/col)

sparse part has weight 89533 (26.97/col)

filtering completed in 3 passes

matrix is 2833 x 2897 (0.4 MB) with weight 75587 (26.09/col)

sparse part has weight 75587 (26.09/col)

commencing Lanczos iteration

memory use: 0.4 MB

lanczos halted after 46 iterations (dim = 2831)

recovered 64 nontrivial dependencies

p30 factor: 362369769670658684194773794821

p31 factor: 2279378891345413668492217185959

elapsed time 00:00:01

1. 998953628399715298831992911290285452859887456062283192823882161683

• Msieve v. 1.53 (SVN 1005)

random seeds: 73933634 81474cde

factoring 998953628399715298831992911290285452859887456062283192823882161683 (66 digits)

searching for 15-digit factors

commencing quadratic sieve (66-digit input)

using multiplier of 23

using generic 32kb sieve core

sieve interval: 12 blocks of size 32768

processing polynomials in batches of 17

using a sieve bound of 156601 (7107 primes)

using large prime bound of 10805469 (23 bits)

using trial factoring cutoff of 23 bits

polynomial 'A' values have 8 factors

7284 relations (3332 full + 3952 combined from 37551 partial), need 7203

begin with 40883 relations

reduce to 10710 relations in 2 passes

attempting to read 10710 relations

recovered 10710 relations

recovered 8450 polynomials

attempting to build 7284 cycles

found 7284 cycles in 1 passes

distribution of cycle lengths:

   length 1 : 3332

   length 2 : 3952

largest cycle: 2 relations

matrix is 7107 x 7284 (1.0 MB) with weight 203885 (27.99/col)

sparse part has weight 203885 (27.99/col)

filtering completed in 4 passes

matrix is 6491 x 6555 (0.9 MB) with weight 180721 (27.57/col)

sparse part has weight 180721 (27.57/col)

commencing Lanczos iteration

memory use: 0.9 MB

lanczos halted after 104 iterations (dim = 6487)

recovered 62 nontrivial dependencies

p33 factor: 359909105075785195573332655734953

p34 factor: 2775571982790955047631589322232411

elapsed time 00:00:18

1. 1608732996831216508159277659952021701799674006235398744155288667343172997

• Msieve v. 1.53 (SVN 1005)

random seeds: 92208490 c24d8a69

factoring 1608732996831216508159277659952021701799674006235398744155288667343172997 (73 digits)

...