Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Черт его знает, может в этом случае удасться избавиться от е... 29.03.05 10:36 Число просмотров: 4594
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> К тому, что не стоит "возиться" с простыми, и лучше > работать просто с целыми, я пришел из простого рассуждения: > количество простых чисел, меньших N, с точностью до > порядка, равно N/ln (N).
Черт его знает, может в этом случае удасться избавиться от е и ln().
> Что означает, что для чисел порядка 10^70 простым будет > "каждое" трехсотое(тысячное, сто тысячное, не очень важно). > В то же время, чтобы найти это простое необходимо (при > проверке в лоб) проверить каждое из них на > взаимную простоту со всеми найдеными, а это примерно 10^67 > (10^65) . :) За это время можно произвести довольно большое > количество операций со всеми этими числами, среди которых > одно простое.
Не надо проверок. Во первых простые генеряться решетом Эратосфена без делений и проверок. Во вторых апроксимационная формула может оказаться очень простой и очень точной, как на первый взгляд не покажется.
> > > (n/e)^(n-log по основанию n/e от n). Неясно, как > > > остаток получить. :) > > > > Это как раз просто, нужно просто на каждом этапе > возведения > > в степень вычислять остаток: > ??? Может я ошибся (Или мало понял) :). но шел разговор о > (n/e)^(n-log по основанию n/e от n). Где степень (n-log по > основанию n/e от n), т.е. порядка n. > Если на каждом этапе вычислять остаток, то количество > этапов будет порядка n. А это не реализуемо в "приличное > "время.
А не надо ничего ни на что делить. Остаток автоматом получается. Посмотрим на исходную функцию (n/e)^n % n. Вычисляем только (n/e), а дальше элементарнейшим алгоритмом возведения в степень по модулю, который во всех реализациях RSA используется.
> Кстати, можно еще рассмотреть только произведение чисел от > корень(N) до корень(N)/2. (С вероятностью 50% на успех, или > выше, если предположить, что исходные множители должны быть > одинакового размера.)
Хорошо, но если алгоритм 100% взлома на всем интервале будет работать для килобитных чисел несколько минут, то и с половинкой интервала не стОит замарачиваться.
> P.S. в связи с тем, что я не могу создать сообщение, пишу > здесь. :) > Как найти решение сравнения a*x*x+b*x+c=0 mod p, где p > простое.
Сначала полезно придумать критерий для коэффициентов, при котором решений нет. Например все они четные.
А вообще то сомневаюсь, что кроме как перебором можно решить.
|
|
|