Американский программист Райан Проппер (Ryan Propper) сообщил об успешной факторизации числа RSA-210, то есть 210-значного полупростого числа — числа, представимого в виде произведения двух простых чисел. 210 десятичных знаков соответствуют 696 битам информации.

Вычислительный процесс продолжался несколько месяцев и завершился 26 сентября 2013 года.

Полупростое число R-210

N = 245246644900278211976517663573088018467026787678332759743
4144517150616008300385872169522083993320715491036268271916798
6407977672324300560059203563124656121846581790410013185929961
9933817012149335034875870551067

Найденные простые множители

prp105 factor: 4359585683259407917999519653872144063854709102
65220196318705482144524085345275999740244625255428455944579
prp105 factor: 5625457617268841037562770073044474817438769440
07510545104946851094548396577479473472146228550799322939273

Это достижение не является рекордом. В 2009 году в рамках неофициального продолжения конкурса RSA Factoring Challenge было факторизовано число RSA-768 (232 десятичных знака, 704 бита), так что ключи RSA-1024 (309 десятичных знаков) уже находятся на расстоянии вытянутой руки.

Последний фрагмент логов

Mon Sep 23 11:09:41 2013 commencing Lanczos iteration (32 threads)
Mon Sep 23 11:09:41 2013 memory use: 26956.9 MB
Mon Sep 23 11:10:27 2013 restarting at iteration 1026631 (dim = 64920012)
Mon Sep 23 11:13:33 2013 linear algebra at 99.3%, ETA 15h43m
Mon Sep 23 11:14:32 2013 checkpointing every 30000 dimensions
Tue Sep 24 02:21:56 2013 lanczos halted after 1033963 iterations (dim = 65383602)
Tue Sep 24 02:24:01 2013 recovered 22 nontrivial dependencies
Tue Sep 24 02:24:17 2013 BLanczosTime: 55712
Tue Sep 24 02:24:17 2013 elapsed time 15:28:33
Tue Sep 24 03:21:13 2013
Tue Sep 24 03:21:13 2013
Tue Sep 24 03:21:13 2013 Msieve v. 1.52 (SVN 936M)
Tue Sep 24 03:21:13 2013 random seeds: 6af9ef2b 972abb4d
Tue Sep 24 03:21:13 2013 factoring 24524664490...51067 (210 digits)
Tue Sep 24 03:21:14 2013 no P-1/P+1/ECM available, skipping
Tue Sep 24 03:21:14 2013 commencing number field sieve (210-digit input)
Tue Sep 24 03:21:14 2013 R0: -8311128239923121259046301811046853
Tue Sep 24 03:21:14 2013 R1: 63190692009226810471
Tue Sep 24 03:21:14 2013 A0: -46373978032319633360321876974395396247530766893600
Tue Sep 24 03:21:14 2013 A1: 4926444336634688706035599320492329943566740
Tue Sep 24 03:21:14 2013 A2: 415031002380786834672968277117654072
Tue Sep 24 03:21:14 2013 A3: -35317070927593920606305065701
Tue Sep 24 03:21:14 2013 A4: -1333072472407237353592
Tue Sep 24 03:21:14 2013 A5: 44263602924186
Tue Sep 24 03:21:14 2013 A6: 744120
Tue Sep 24 03:21:14 2013 skew 21829368.04, size 3.501e-15, alpha -11.183, combined = 1.204e-15 rroots = 6
Tue Sep 24 03:21:14 2013
Tue Sep 24 03:21:14 2013 commencing square root phase
Tue Sep 24 03:21:14 2013 reading relations for dependency 1
Tue Sep 24 03:21:25 2013 read 32695123 cycles
Tue Sep 24 03:22:39 2013 cycles contain 106934058 unique relations
Tue Sep 24 05:32:17 2013 read 106934058 relations
Tue Sep 24 05:44:28 2013 multiplying 106934058 relations
Tue Sep 24 11:02:59 2013 multiply complete, coefficients have about 6529.43 million bits
Tue Sep 24 11:03:59 2013 initial square root is modulo 21002549
Tue Sep 24 16:02:07 2013 GCD is 1, no factor found
Tue Sep 24 16:02:07 2013 reading relations for dependency 2
Tue Sep 24 16:03:51 2013 read 32693851 cycles
Tue Sep 24 16:05:11 2013 cycles contain 106953756 unique relations
Tue Sep 24 18:27:03 2013 read 106953756 relations
Tue Sep 24 18:40:10 2013 multiplying 106953756 relations
Wed Sep 25 00:19:45 2013 multiply complete, coefficients have about 6530.65 million bits
Wed Sep 25 00:20:52 2013 initial square root is modulo 21068617
Wed Sep 25 05:22:23 2013 GCD is N, no factor found
Wed Sep 25 05:22:23 2013 reading relations for dependency 3
Wed Sep 25 05:22:52 2013 read 32688271 cycles
Wed Sep 25 05:24:16 2013 cycles contain 106919358 unique relations
Wed Sep 25 07:44:54 2013 read 106919358 relations
Wed Sep 25 07:58:11 2013 multiplying 106919358 relations
Wed Sep 25 13:29:11 2013 multiply complete, coefficients have about 6528.53 million bits
Wed Sep 25 13:30:14 2013 initial square root is modulo 20953879
Wed Sep 25 18:25:01 2013 GCD is N, no factor found
Wed Sep 25 18:25:01 2013 reading relations for dependency 4
Wed Sep 25 18:26:40 2013 read 32684333 cycles
Wed Sep 25 18:27:56 2013 cycles contain 106923636 unique relations
Wed Sep 25 20:42:16 2013 read 106923636 relations
Wed Sep 25 20:53:54 2013 multiplying 106923636 relations
Thu Sep 26 02:18:38 2013 multiply complete, coefficients have about 6528.80 million bits
Thu Sep 26 02:19:46 2013 initial square root is modulo 20968403
Thu Sep 26 07:17:57 2013 sqrtTime: 187003
Thu Sep 26 07:17:57 2013 prp105 factor: 4359585...55944579
Thu Sep 26 07:17:57 2013 prp105 factor: 5625457...22939273
Thu Sep 26 07:17:57 2013 elapsed time 51:56:44

  • Подпишись на наc в Telegram!

    Только важные новости и лучшие статьи

    Подписаться

  • Подписаться
    Уведомить о
    0 комментариев
    Межтекстовые Отзывы
    Посмотреть все комментарии