Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Даже по решету эратосфена придется "пройтись" простыми до... 29.03.05 11:50 Число просмотров: 4353
Автор: Searcher Статус: Незарегистрированный пользователь
Отредактировано 29.03.05 12:03 Количество правок: 1
|
> Не надо проверок. Во первых простые генеряться решетом
> Эратосфена без делений и проверок.
Даже по решету эратосфена придется "пройтись" простыми до корня из N. т.е. если N~10^70,
то пройтись придется простыми до 10^35. (Если я правильно знаю решето)
> Во вторых
> апроксимационная формула может оказаться очень простой и
> очень точной, как на первый взгляд не покажется.
? Осталось ее найти.
> А не надо ничего ни на что делить. Остаток автоматом
> получается. Посмотрим на исходную функцию (n/e)^n % n.
> Вычисляем только (n/e), а дальше элементарнейшим алгоритмом
> возведения в степень по модулю, который во всех реализациях
> RSA используется.
Тогда что остается неприменимого в формуле Стирлинга? Только точность.
Интересно, как получить остальные члены в полиноме для увеличения точности.
И еще, какая понадобится точность для N=10^k, k знаков, или больше чем 10^k? :)
> Хорошо, но если алгоритм 100% взлома на всем интервале
> будет работать для килобитных чисел несколько минут, то и с
> половинкой интервала не стОит замарачиваться.
Это если будет, а если нет? И еще, если рассматривать только половинку (верхнюю) интервала,
то относительное изменение чисел (отношение максимального члена к минимальному) будет максимум в 2 раза, что может снизить неточность, по сравнению
с нижней половиной, где относительное изменение чисел будет 10^35 (Если N 10^70).
> Сначала полезно придумать критерий для коэффициентов, при
> котором решений нет. Например все они четные.
> А вообще то сомневаюсь, что кроме как перебором можно
> решить.
Жаль. Хочется быстрее чем перебором. :)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
