2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение31.12.2013, 21:14 
Заслуженный участник


09/09/10
3729
ubik77 в сообщении #808152 писал(а):
Но я думаю, что в GMP возведение в степень по модулю тоже делается методом квадратов.

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 01:42 


24/05/09

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

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 03:50 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 09:31 


15/06/13
31
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. Это ключевой момент для поиска больших простых чисел. Но у меня не хватит мозгов и подготовки, не мой уровень. За такое научные звания дают.

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 11:26 


24/05/09

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

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

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 11:55 
Заслуженный участник


12/08/10
999
$M_{43112609}=2^{43112609}-1$ - числа Мерсена

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 12:08 


24/05/09

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 12:50 


15/06/13
31
Null в сообщении #808300 писал(а):
$M_{43112609}=2^{43112609}-1$ - числа Мерсена

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 14:43 


24/05/09

2054
ubik77 в сообщении #808309 писал(а):
Нет, мне нужно не для таких чисел, а для обычных простых. Которые в практической криптографии применяются.

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

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 15:06 


15/06/13
31
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, то число точно не
простое и его можно отбросить.

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение01.01.2014, 23:45 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 08:12 


24/05/09

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

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 08:32 
Заслуженный участник


09/09/10
3729
Alexu007 в сообщении #808569 писал(а):
А если 2 в степени N-1 по модулю N равно 1, то число точно простое?

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 08:43 


15/06/13
31
Alexu007 в сообщении #808569 писал(а):
А если 2 в степени N-1 по модулю N равно 1, то число точно простое?

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

-- 02.01.2014, 09:54 --

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

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

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

 Профиль  
                  
 
 Re: Возведение в степень по модулю (можно ли ускорить для осн.2)
Сообщение02.01.2014, 09:55 


15/06/13
31
Joker_vD в сообщении #808493 писал(а):
ubik77
Кстати, в Википедии в статье о тесте Соловея–Штрассена есть ссылка на интересную работу по быстрой генерации ключей для RSA. Может, что-то интересное там увидите.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 56 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group