[req] быстрая факторизация небольших чисел

Тема в разделе "WASM.CRYPTO", создана пользователем wAX, 1 ноя 2008.

  1. wAX

    wAX New Member

    Публикаций:
    0
    Регистрация:
    1 ноя 2008
    Сообщения:
    2
    Доброго дня, господа!
    Хочется иметь возможность быстро факторизовать числа до 13 (десятичных) знаков.
    Платформа linux. Если есть название готового пакета - буду рад услышать название.
     
    wAX, 1 ноя 2008
    #1
  2. um0v

    um0v New Member

    Публикаций:
    0
    Регистрация:
    10 окт 2008
    Сообщения:
    32
    um0v, 1 ноя 2008
    #2
  3. flankerx

    flankerx New Member

    Публикаций:
    0
    Регистрация:
    2 июл 2004
    Сообщения:
    423
    Адрес:
    Moscow, Russia
    Если до 13 десятичных знаком, то это алгоритмы trial division, ECM и Pollard-Rho. Реализацию можно посмотреть тут: http://www.komite.net/laurent/soft/ecm/ecm-6.0.1.html

    Всякие qs/nfs/msieve работать будут, но для таких небольших чисел они нафиг не нужны.
     
    flankerx, 2 ноя 2008
    #3
  4. wAX

    wAX New Member

    Публикаций:
    0
    Регистрация:
    1 ноя 2008
    Сообщения:
    2
    um0v, flankerx:
    Благодарствую, господа. То, что нужно. Под Gentoo этого добра нет, но написать ebuild - не проблема. Ещё раз, огромное спасибо.
     
    wAX, 6 ноя 2008
    #4