Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Про то, что не стоит "возиться" с простыми, и лучше работать... 28.03.05 22:26 Число просмотров: 4026
Автор: Searcher Статус: Незарегистрированный пользователь
Отредактировано 28.03.05 22:59 Количество правок: 2
|
> Я там тоже ошибся, в програмке, которая проверяля
> предположение. При очередном "сворачивании" "обнуляется"
> каждая вторая "производная".
> Короче все равно "не катит".
> Была мысль поработать над быстрым вычислением "простого"
> факториала, то есть произведения вех простых чисел не более
> заданного. Но похоже там все еще сложнее.
К тому, что не стоит "возиться" с простыми, и лучше работать просто с целыми, я пришел из простого рассуждения:
количество простых чисел, меньших N, с точностью до порядка, равно N/ln (N).
Что означает, что для чисел порядка 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) до корень(N)/2. (С вероятностью 50% на успех, или выше, если предположить, что исходные множители должны быть одинакового размера.)
P.S. в связи с тем, что я не могу создать сообщение, пишу здесь. :)
Как найти решение сравнения a*x*x+b*x+c=0 mod p, где p простое.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
