Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Это я к тому, что может быть простая формула для вычисления... 30.03.05 00:10 Число просмотров: 4386
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> И возвращаясь к "простому" факториалу, надо будет найти все
> простые на интервале, и
> для больших чисел по решету надо будет пройтись всеми
> простыми, которые меньше чем корень из
> кандидатов. При этом даже если будет отсеяно 9999999 из
> 1000000, то по этому последнему необходимо будет пройтись
> всеми простыми, количество которых существенно больше, чем
> 1000000 на десятки порядков.
> Но тем, не менее, если считаешь, что "простой факториал"
> даст выигрыш, может так оно и есть.
Это я к тому, что может быть простая формула для вычисления простого факториала, которую пока не нашли и для обычного. НАПРИМЕР, взяли простое число, возвели его в степень, где показатель - его "порядковый номер", потом его "порядковый номер" возвели в степень того что получилось в первый раз. Или что-нибудь в этом духе. И не надо ничего вычислять и генерить сами числа, перемножать их.
> > > И еще, какая понадобится точность для N=10^k, k
> > знаков, или
> > > больше чем 10^k? :)
> >
> > n-k. Хотим +/-10 - надо -(к-1), хотим +/-100 - надо
> -(к-2).
> То есть, приводя для случая rsa-1024~10^308 нам надо
> получить
> 308 знаков и 308 членов полинома? Полиномиальная сложность?
Это я к формуле Стерлинга. Там погрешность -4, или 0.0001, насколько я помню. Если мы не хотим перебирать более 10 чисел в окресности приближенного факториала, то нам нужно, чтоб к-1 десятичных знаков были точными из к знаков всего.
> Да, ты прав. Просто это было ограничение, которое могло бы
> упростить вычисления.
> Да, вылизывать код на АСМе, чтобы выиграть один порядок из
> 100 - пустая трата времени.
> Тем не менее, если рассматривать два ряда
> 1*2*3*....*100 и
> 101*102*103*...*200, то 1*100 отличается от 50*51 в 25 раз,
> в то время как
> 101*200 отличается от 150*151 в 1.1, что означает, что
> значение первого ряда от 50^50 будет отличаться
> на пару десятков порядков, в то время как значение второго
> от 150^50 всего на 2.
А к чему это?
|
|
|
подробно о проекте
Анализ криптографических сетевых...
