singlepost

Алгоритм Диффи – Хеллмана << На главную или назад  

Возникло некоторое непонимание того, какими же должны быть параметры степени на самом деле.
Вики говорит, что необходимо возводить додесятиразрядное число в, как минимум, сторазрядную степень.

С точки зрения вычисления, я это не предтсавляю возможным.

39 ответов в теме “Алгоритм Диффи – Хеллмана”

  1. 12
    Подмогаев Свят ответил:

    Всем спасибо!
    332 хода))

  2. 11
    Леонид Максимов ответил:

    да, упустил :) )

  3. 10
    Михаил Асташкевич ответил:

    > эээ… а разве возведение в степерь по модулю требует длинной арифметики?

    Ну… стозначную степень надо же делить на два=)

  4. 9
    Денис Лисов ответил:

    Леонид, когда модуль трехсотзначный, то по логике требует. Как иначе?

  5. 8
    Денис Лисов ответил:

    Говорит-говорит, что русская, что английская.
    //ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%B...

    Михаил, именно.

    Подмогаев Свят, если вам требуется возвести число в стозначную степень, возьмите алгоритм, время работы которого пропорционально количеству знаков в степени. Такие существуют.

  6. 7
    Леонид Максимов ответил:

    эээ… а разве возведение в степерь по модулю требует длинной арифметики?

  7. 6
    Владимир Медведев ответил:

    >>>Говорит-говорит, что русская, что английская.
    туплю, не заметил название темы

  8. 5
    Владимир Медведев ответил:

    >>>Вики говорит
    Пруфлинк встудию!

  9. 4
    Михаил Асташкевич ответил:

    log2 (10^100) ~ 330. Неплохая сложность, нужно только длинную арифметику написать.

  10. 3
    Подмогаев Свят ответил:

    логарифм степени и есть порядок степени.

  11. 2
    Сергей Аганезов ответил:

    телефон – решение!!

  12. 1
    Денис Лисов ответил:

    С точки зрения вычисления вам нужен разумный алгоритм возведения в степень по заданному модулю, который работает за время порядка логарифма степени, а не порядка степени. Это вполне реально.

Клуб программистов работает уже ой-ой-ой сколько, а если поточнее, то с 2007 года.