информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Все любят медАтака на InternetПортрет посетителя
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / theory
Имя Пароль
ФОРУМ
все доски
FAQ
IRC
новые сообщения
site updates
guestbook
beginners
sysadmin
programming
operating systems
theory
web building
software
hardware
networking
law
hacking
gadgets
job
dnet
humor
miscellaneous
scrap
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Это я к тому, что может быть простая формула для вычисления... 30.03.05 00:10  Число просмотров: 4208
Автор: 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.

А к чему это?
<theory> Поиск 






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2024 Dmitry Leonov   Page build time: 1 s   Design: Vadim Derkach