Возведение в степень по модулю (можно ли ускорить для осн.2)

[Joker_vD]

ubik77 в сообщении #808152 писал(а):

Но я думаю, что в GMP возведение в степень по модулю тоже делается методом квадратов.

Там на самом деле вариация на тему, метод скользящего окна: "Handbook of Applied Cryptography", алгоритм 14.85 (источник).

[Alexu007]

Какого размера числа интересуют?

Например: $ (2^{499})\mod\ 1125 = 938$ предложенной мной функцией вычисляется за доли секунды, практически мгновенно. И разрядности int64 хватает.

[Joker_vD]

Alexu007
Ну очевидно там у товарища числа длиной в килобайты, раз так долго возводится. А $1125$ укладывается в 11 бит, это даже не смешно.

Вы попробуйте вашим методом посчитать $2^{M_{43112609}-1}\pmod{M_{43112609}}$

[ubik77]

Alexu007 в сообщении #808264 писал(а):

Какого размера числа интересуют?
Например: $ (2^{499})\mod\ 1125 = 938$ предложенной мной функцией вычисляется за доли секунды, практически мгновенно. И разрядности int64 хватает.

499 это мало. Число показатель степени - килобайт двоичных разрядов или даже больше.

-- 01.01.2014, 10:42 --

Joker_vD в сообщении #808225 писал(а):

ubik77 в сообщении #808152 писал(а):

Но я думаю, что в GMP возведение в степень по модулю тоже делается методом квадратов.

Там на самом деле вариация на тему, метод скользящего окна: "Handbook of Applied Cryptography", алгоритм 14.85 (источник).

Да, похоже там серьёзно проработали тему. Вряд ли что-то получится кардинально улучшить. Хотя этот метод не намного эффективнее простых квадратов, не в разы.
А хотелось бы как-нибудь ускорить для основания 2. Это ключевой момент для поиска больших простых чисел. Но у меня не хватит мозгов и подготовки, не мой уровень. За такое научные звания дают.

[Alexu007]

Joker_vD в сообщении #808269 писал(а):

Alexu007
Ну очевидно там у товарища числа длиной в килобайты, раз так долго возводится. А $1125$ укладывается в 11 бит, это даже не смешно.

Вы попробуйте вашим методом посчитать $2^{M_{43112609}-1}\pmod{M_{43112609}}$

Дык подсчитать то можно, только для этого длинная арифметика нужна, в инт64 такая цифра не поместится. И скорость уже будет зависеть и от скорости длинной арифметики, и неизвестно, что перевесит. Впрочем, длинная арифметика у меня есть и я могу подсчитать, если вы расшифруете, что за число M_43112609

[Null]

$M_{43112609}=2^{43112609}-1$ - числа Мерсена

[Alexu007]

Мдя, эк куда вы загнули... Я пас.

[ubik77]

Null в сообщении #808300 писал(а):

$M_{43112609}=2^{43112609}-1$ - числа Мерсена

Нет, мне нужно не для таких чисел, а для обычных простых. Которые в практической криптографии применяются.

[Alexu007]

ubik77 в сообщении #808309 писал(а):

Нет, мне нужно не для таких чисел, а для обычных простых. Которые в практической криптографии применяются.

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

Например: деление случайного числа из 64 десятичных цифр на первые 100 000 простых чисел, выполняется много быстрее секунды.

[ubik77]

Alexu007 в сообщении #808331 писал(а):

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

Например: деление случайного числа из 64 десятичных цифр на первые 100 000 простых чисел, выполняется много быстрее секунды.

Вот например, число N (8килобит в 16-ричном представлении):
88111DEA9581F51D70CFC9D55278789E596C3E5150F1050F7EE2841277137E6038EAF3DDE52C56FB5F505D9B66B23A6533BC78D2D3814F51F55DE8DC199BBD7B87A15EC6B1A5A6C4D88D8BFC18F6D98D4EA5DFD494DB73E68E0EFEBDE9EF801BAB36E77DD7E357C6087220F7E723138106468C84126A3F31D5B302B1FED2CCD37E90504497D3CBA0213E0B3F55F5EA9A095AF33BDB9AD34BDB6C4E672F38DF86F8D5AAB0DD1A48AAA3C83DE6F67E8C2A88DD175ABE9C8BCBE4567781811232D264013B446FDFDAEF892E5A1D6BFA5D62F5E83D6B67F93EFAC73C99E6BD147E46625DC5635B526A617A3C78B73FE42789CD2B0769A2BF87438973A7227D1B7D34DBF67DB4B16A04C80206C38A980DBF633D18774E62AAAA1ED99EBE0E2FC78CA2B7C528D49F4A12A1DFD975BFEF3CA043AB7201A6EA11B2CE097FD0976111F553A6A603923C1739B0094B7960B4301AD081EFA8D365F7F77318BEEC9E8CB8BFC8884FA2F3A69999A07E3EDA1BAB4814E0D755E3E223B0572739EC72A0ABB65892F75354411B38CF24FA2E46E257F8918DBF6ACE7096BCB866213F6B8B493DF9E17D801FD974B6426ACD30D9E756F3EE1F5CFFA52EDC9B83A4095F683646B16DADC6594967CCE0D752CB05C34CA898B70D3B771BCB2FD3EC45E61C5A37D6DCBCF9B0AA43D18AF687FDC4915E2E0E1C71E1EBE5B093D1E7D78B36360D7A2027924088111DEA9581F51D70CFC9D55278789E596C3E5150F1050F7EE2841277137E6038EAF3DDE52C56FB5F505D9B66B23A6533BC78D2D3814F51F55DE8DC199BBD7B87A15EC6B1A5A6C4D88D8BFC18F6D98D4EA5DFD494DB73E68E0EFEBDE9EF801BAB36E77DD7E357C6087220F7E723138106468C84126A3F31D5B302B1FED2CCD37E90504497D3CBA0213E0B3F55F5EA9A095AF33BDB9AD34BDB6C4E672F38DF86F8D5AAB0DD1A48AAA3C83DE6F67E8C2A88DD175ABE9C8BCBE4567781811232D264013B446FDFDAEF892E5A1D6BFA5D62F5E83D6B67F93EFAC73C99E6BD147E46625DC5635B526A617A3C78B73FE42789CD2B0769A2BF87438973A7227D1B7D34DBF67DB4B16A04C80206C38A980DBF633D18774E62AAAA1ED99EBE0E2FC78CA2B7C528D49F4A12A1DFD975BFEF3CA043AB7201A6EA11B2CE097FD0976111F553A6A603923C1739B0094B7960B4301AD081EFA8D365F7F77318BEEC9E8CB8BFC8884FA2F3A69999A07E3EDA1BAB4814E0D755E3E223B0572739EC72A0ABB65892F75354411B38CF24FA2E46E257F8918DBF6ACE7096BCB866213F6B8B493DF9E17D801FD974B6426ACD30D9E756F3EE1F5CFFA52EDC9B83A4095F683646B16DADC6594967CCE0D752CB05C34CA898B70D3B771BCB2FD3EC45E61C5A37D6DCBCF9B0AA43D18AF687FDC4915E2E0E1C71E1EBE5B093D1E7D78B36503F

формулу смотрите в самом первом сообщении треда.
двойку нужно возвести в N-1 по модулю N.

У меня порядка секунды занимает вычисление.
Но для поиска простого числа таких чисел надо перебрать много,
поэтому быстродействие имеет значение. Или час ждать результата,
или 15 минут например.

-- 01.01.2014, 16:09 --

Alexu007 в сообщении #808331 писал(а):

Например: деление случайного числа из 64 десятичных цифр на первые 100 000 простых чисел, выполняется много быстрее секунды.

Это решето. Конечно, оно тоже применяется перед основной
проверкой. Для решета есть ещё более хитрые методы, я тут не буду
их писать. Но всё упирается именно в быстродействие теста Ферма.
Если 2 в степени N-1 по модулю N не равно 1, то число точно не
простое и его можно отбросить.

[Joker_vD]

ubik77
Кстати, в Википедии в статье о тесте Соловея–Штрассена есть ссылка на интересную работу по быстрой генерации ключей для RSA. Может, что-то интересное там увидите.

[Alexu007]

А если 2 в степени N-1 по модулю N равно 1, то число точно простое?

(Оффтоп)

Зачем в RSA обязательно использовать длинные простые числа? Можно зашифровать более короткими, но последовательно несколько раз (допустим, 10). При этом, если бы шифрование осуществлялось однократно недлинным ключом, подобрать такой ключ было бы несложно, а критерием правильности служил бы осмысленный текст на выходе. Но при расшифровке многократно зашифрованного текста осмысленный текст появится только если последовательно применить все 10 правильных ключей, во всех остальных случаях результатом (правильным, но не окончательным) будет не поддающаяся идентификации "абракадабра".

То есть, даже "угадав" 9 ключей из 10, на выходе будет всё та же "абракадабра", ничего не будет указывать на то, что предыдущие ключи подобраны правильно.

[Joker_vD]

Alexu007 в сообщении #808569 писал(а):

А если 2 в степени N-1 по модулю N равно 1, то число точно простое?

$2^{11\cdot31-1}\equiv1\pmod{11\cdot31}$.

[ubik77]

Alexu007 в сообщении #808569 писал(а):

А если 2 в степени N-1 по модулю N равно 1, то число точно простое?

Нет, иногда, но очень редко, может быть составным.
После теста Ферма отбрасываются точно не простые числа, если не отброшено, на следующем шаге число проверяется другими тестами, которые медленнее Ферма.

-- 02.01.2014, 09:54 --

Alexu007 в сообщении #808569 писал(а):

Зачем в RSA обязательно использовать длинные простые числа? Можно зашифровать более короткими, но последовательно несколько раз (допустим, 10). При этом, если бы шифрование осуществлялось однократно недлинным ключом, подобрать такой ключ было бы несложно, а критерием правильности служил бы осмысленный текст на выходе. Но при расшифровке многократно зашифрованного текста осмысленный текст появится только если последовательно применить все 10 правильных ключей, во всех остальных случаях результатом (правильным, но не окончательным) будет не поддающаяся идентификации "абракадабра".
То есть, даже "угадав" 9 ключей из 10, на выходе будет всё та же "абракадабра", ничего не будет указывать на то, что предыдущие ключи подобраны правильно.

Интересная мысль. Конечно, два простых числа по 4кбит сгенерировать намного проще и быстрее чем одно на 8кбит. Я 8-килобитовое, которое дал выше, генерировал где-то час, а 4-килобитовое генерируется в пределах двух минут. Но если бы было так просто, то почему это не делают? Тут необходима теоретическая оценка. Как-то пока нет уверенности.

А вдруг там можно за какие-нибудь несколько бит уцепиться в следующем ключе (они должны иметь определённое значение) и так подобрать нужный ключ на одном шаге?

[ubik77]

Joker_vD в сообщении #808493 писал(а):

ubik77
Кстати, в Википедии в статье о тесте Соловея–Штрассена есть ссылка на интересную работу по быстрой генерации ключей для RSA. Может, что-то интересное там увидите.

Это я читал. Данная работа не представляет интереса. Описанное ими решето детское, есть лучше алгоритмы. Сравнивают с какой-то малоизвестной "профессиональной программой" и утверждают что у них быстрее. Они сокращают количество повторов метода Миллера-Рабина. А какой в этом смысл, если метод Ферма всего за один цикл отбрасывает непростые, а потом уже число можно мучить сколько угодно циклов любым из известных методов?
Тест Соловея-Штрассена не быстрее теста Ферма (как они утверждают). В общем эта статья типичный пример лженауки и очковтирательства: http://www.youtube.com/watch?v=a5tQScolXmg