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

[Батороев]

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

Они сокращают количество повторов метода Миллера-Рабина.

Если сократить число повторов до одного (как это сделали Вы, приняв в качестве "свидетеля простоты" число 2), то на числах $n=2k+1$ (где $k$ - нечетное) тест Миллера-Рабина ничем не отличается от теста Ферма, зато на других - быстрее.

[ubik77]

Батороев в сообщении #808583 писал(а):

Если сократить число повторов до одного (как это сделали Вы, приняв в качестве "свидетеля простоты" число 2), то на числах $n=2k+1$ (где $k$ - нечетное) тест Миллера-Рабина ничем не отличается от теста Ферма, зато на других - быстрее.

Быстрее на один бит из тысячи? Какой в этом смысл с точки зрения быстродействия?

[Ales]

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

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

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

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

-- 02.01.2014, 09:54 --

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

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

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

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

Шифрование должно производится открытым методом.
Дешифрование - тайным методом.

Метод RSA успешен благодаря тому, что не удается разложить на множители достаточно большие числа.
Маленькие числа легко разлагаются на множители.
Сложность расшифровки последовательного 10-кратного метода RSA с 10-значными числами (= 5-значное простое * 5-значное простое) можно оценить сверху: $ 10 \cdot 10^5$.

[ubik77]

Ales в сообщении #808597 писал(а):

Метод RSA успешен благодаря тому, что не удается разложить на множители достаточно большие числа.
Маленькие числа легко разлагаются на множители.
Сложность расшифровки последовательного 10-кратного метода RSA с 10-значными числами (= 5-значное простое * 5-значное простое) можно оценить сверху: $ 10 \cdot 10^5$.

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

[Ales]

Ales в сообщении #808597 писал(а):

Я 8-килобитовое, которое дал выше, генерировал где-то час, а 4-килобитовое генерируется в пределах двух минут.

Можно оценить сложность этого алгоритма нахождения n-битового простого числа:
$f(2n) = 32 f(n) \to f(n) = C n^5 $.
Одна степень происходит из частоты простых чисел, ее никак не убрать.
Остаются четыре степени, которые определяются алгоритмом возведения в степень $N-1 \mod N$.
Из них - одна - сам цикл последовательного возведения в квадрат.

Остальные три получаются на шаге цикла: $a^2 \cdot b \mod N$.
По моим прикидкам там достаточно двух степеней,
а одна степень получается лишняя.

-- Чт янв 02, 2014 12:57:57 --

Следует ожидать, что время проверки на простоту будет расти как 4-ая степень длины простого числа.

-- Чт янв 02, 2014 13:23:39 --

Лишняя "степень" скорее всего возникла из-за случайного распределения простых чисел.
Интервал для поиска только в среднем оценивается как $n$.
В некоторых неудачных случаях он может быть $ 2n $ или $3n$.

[ubik77]

Ales в сообщении #808607 писал(а):

По моим прикидкам там достаточно двух степеней,
а одна степень получается лишняя.

Вот алгоритм квадратов (SX-алгоритм):
http://granitnayki.com/?p=212

Операцию модульного возведения в квадрат (y*y mod m)
теоретически можно реализовать немного быстрее чем
последовательное умножение и остаток от деления на m:
http://en.wikipedia.org/wiki/Multiplication_algorithm#Peasant_or_binary_multiplication

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

[Ales]

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

Но это теоретически, на практике у меня не получилось сделать в GMP чтобы работало быстрее.

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

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

[ubik77]

Ales в сообщении #808627 писал(а):

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

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

Это всё и так делается, а с решетом даже ещё навороченнее чем тут написано. Но с какого-то момента усложнять решето становится невыгодно, потому что усложнение в 10 раз (к примеру) дает дополнительный отсев чисел только 2%. В итоге всё-равно всё упирается в проверку Ферма.

[Батороев]

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

Какой в этом смысл с точки зрения быстродействия?

В том, что для чисел вида $n=2^mk+1$, где $k$ - нечетное, a $m$ достаточно большое, нет необходимости возводить $2$ в степень $n-1=2^mk$, а зачастую обходятся меньшими степенями.

[ubik77]

Батороев в сообщении #808634 писал(а):

В том, что для чисел вида $n=2^mk+1$, где $k$ - нечетное, a $m$ достаточно большое, нет необходимости возводить $2$ в степень $n-1=2^mk$, а зачастую обходятся меньшими степенями.

Эти числа не представляют интереса для криптографии.

[Ales]

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

В итоге всё-равно всё упирается в проверку Ферма.

А Вы не пробовали оценить время работы Вашего алгоритма проверки Ферма?
Например для чисел длины 32, 64, 128, 256, 512, 1024?

[ubik77]

Ales в сообщении #808644 писал(а):

А Вы не пробовали оценить время работы Вашего алгоритма проверки Ферма?
Например для чисел длины 32, 64, 128, 256, 512, 1024?

В каком смысле "оценить"? Для чего это нужно?
У меня написана программа, и видно сколько по времени эта операция (тест Ферма) выполняется на числах разной длины.
Оценка времени поиска простого числа как "4-ая степень длины" близка к реальности (с предварительным применением решета).

[Ales]

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

Для чего это нужно?

Чтобы понять, имеет ли смысл улучшать алгоритм проверки Ферма.

[ubik77]

Ales в сообщении #808669 писал(а):

Чтобы понять, имеет ли смысл улучшать алгоритм проверки Ферма.

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

[Ales]

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

Возможно именно для двойки его можно как-то оптимизировать.

Думаю, что нельзя.
2 нужно возводить в квадрат.
Уже на 10-м шаге выходим на $2^{1024}$, вылезаем за модуль и получаем обычное число.


Для кольца вычетов по модулю нечетного простого числа 2, как элемент кольца,
должно быть ничем не лучше и не хуже других чисел.

Зато 2-ка имеет особые свойства для операций с элементами кольца,
ведь 2-ка делит число ненулевых вычетов.

Найти у 2-ки какие-то особые свойства, как элемента кольца - сверхдостижение,
возможно взламывающее загадку дискретного логарифма.

-- Чт янв 02, 2014 16:42:46 --

Можно еще так рассуждать: достаточно часто $2^k$ пробегает все ненулевые вычеты,
и любой вычет - это какая-то степень 2.
Поэтому операции с любым вычетом не хуже и не лучше, чем операции с 2.