Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | |
Раз речь пошла про экстремумы... 14.08.04 00:37 Число просмотров: 3190
Автор: whiletrue <Роман> Статус: Elderman
|
> Функция определена на N и следовательно такие понятия как
> "бесконечно малая" и иже с ними тут не работают. Но всё
> равно даже дать приблизительную оценку невозможно.
> Конкретного доказательства я не смогу привести, но
> достаточно просто построить график этой функции и
> посмотреть как она себя ведёт.
Я поэтому и говорю про дифференцируемость, ибо другого способа нахождения минимумов не знаю.
Думаю, теперь DPP ясно, что задача некорректна.
Когда ф-ция дифференцируема, тогда предыдущая точка как бы жестко связана со следующей... поэтому для нее можно много че хорошего вычислить, а в этом случае каждая следующая точка ведет себя "непредсказуемо".
|
|
<theory>
|
Факторизация больших 13.08.04 14:59
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 13.08.04 15:00 Количество правок: 1
|
|
А можно ли попробовать пробежаться в поисках "0" по локальным минимумам F(x)=N%x, на интервале x от 2 до sqrt(N)?
|
|
А как Ты выявишь области локальных минимумов отсюда? 13.08.04 16:37
Автор: Heller <Heller> Статус: Elderman
|
|
|
| |
Я то подумаю. А спросил - узнать, может кто ковырял, и наковырял доказательства, что точно невозможно. Тогда и думать на эту тему не буду. В и-нете про это ничего не нарыл. 13.08.04 17:16
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 13.08.04 17:19 Количество правок: 3
|
|
|
| | |
Эта ф-ция не диффернцируема 13.08.04 18:16
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 13.08.04 18:22 Количество правок: 3
|
Пусть функция f(x) определена в некоторой окрестности точки x0. Рассмотрим приращение функции в этой точке: df(x)=f(x0+dx)-f(x0). Функция f(x) называется дифференцируемой в точке, если ее приращение можно записать в виде df(x)=A*dx+a(dx)*dx, где dx - приращение независимой переменной, А - постоянная, не зависящая от dx, a(dx) - бесконечно малая функция при dx->0.
Это как раз не твой случай.
Как ты минимумы будешь искать?
Ее необходимо заменить чем-то непрерывным или кусочно-непрерывным. А чем?!
|
| | | |
Это понятно, что функция дискретная. Берем значение в точке... 16.08.04 12:03
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Как ты минимумы будешь искать?
Это понятно, что функция дискретная. Берем значение в точке х, если значение в точке х-1 и в точке х+1 бльше, чем в х, то пусть это и будет локальный минимум.
> Ее необходимо заменить чем-то непрерывным или
> кусочно-непрерывным. А чем?!
Можно попробовать параболой, а лучше кубической кривой интерполировать. Правда есть такие участки, что пока еще не понятно чем.
|
| | | | |
Это случай не когда есть непрерывная табулированная... 16.08.04 13:04
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 16.08.04 13:06 Количество правок: 1
|
> > Как ты минимумы будешь искать?
>
> Это понятно, что функция дискретная. Берем значение в точке
> х, если значение в точке х-1 и в точке х+1 бльше, чем в х,
> то пусть это и будет локальный минимум.
Это случай не когда есть непрерывная табулированная (дискретизированная) ф-ция, а именно дискретная. Нахождение минимумов получается только перебором. И как туда аналитику прикрутить - фиг знает.
> > Ее необходимо заменить чем-то непрерывным или
> > кусочно-непрерывным. А чем?!
>
> Можно попробовать параболой, а лучше кубической кривой
> интерполировать. Правда есть такие участки, что пока еще не
> понятно чем.
Вот в том-то и дело. Если бы можно было какими-то хотя бы кусками аппроксимировать... чем-то, охватывающем как можно больше точек.
|
| | | | | |
А что если попробовать выразить эту функцию как... 16.08.04 16:25
Автор: Heller <Heller> Статус: Elderman
|
|
А что если попробовать выразить эту функцию как рекуррентную? И уже её пробовать исследовать. Как выразить опять же непонятно, но всё таки может у кого какие идеи появятся.. И потом можно искать не области минимумов, а по определённым значениям в точках рекуррентной функции исключать конкретные диапазоны, чем сокращать область поиска корней. Это, на мой взгляд, было бы более продуктивно..
|
| | | | | | |
Тут товарищь volizar уже что-то на тему рекуррентности... 18.08.04 12:39
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 18.08.04 12:45 Количество правок: 3
|
> А что если попробовать выразить эту функцию как
> рекуррентную? И уже её пробовать исследовать. Как выразить
Тут товарищь volizar уже что-то на тему рекуррентности писал:
"http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=105916"
Берём следующее простое число b2, так что b2<b1.
Ищем следующее d. Оно будет равно d: = d + (c - b2)*( b1 - b2).
Само c станет равно c: = c + (b1 - b2).
Если d будет больше b2, d >b2 , то
находим новое c, c = c + d/b2 (без остатка)
новое d, d = d (mod b2)
> опять же непонятно, но всё таки может у кого какие идеи
> появятся.. И потом можно искать не области минимумов, а по
> определённым значениям в точках рекуррентной функции
> исключать конкретные диапазоны, чем сокращать область
Ну и как тут исключить большой интервал?
> поиска корней. Это, на мой взгляд, было бы более
> продуктивно..
У меня есть еще мысль: Разбить ряд простых чисел на группы, перемножить числа в группах, получим несколько очень больших чисел, перебирая эти очень большие числа находим НОД с заданным. Если НОД = 1, берем следующее. Если НОД равен заданному, значит все множители заданного принадлежат этой группе. Иначе НОД и есть один из множителей. Второй находится делением. НОД находится очень быстро. Чтобы избежать попадпния множителей в одну группу, группируем по разному: первая тысяча в первую, вторая во вторую и т.д., затем все числа, стоящие на четных местах, в очередную группу, все на нечетных в еще одну. Проблема в получении произведений этих групп - добраться до килобитных чисел займет много времени. Возможен такой вариант: просто генерим огромное случайное число, оно может оказаться и простым, но с бОльшей вероятностью оно будет произведением множества простых чисел. Если НОД с ним равен заданному или единицы, генерим следующее. Бред это все, конечно, но может кто-нибудь оценит такой метод разложения на простые. Т.е. с вероятностью 0.95 килобитное число раскладывается за N лет на гигагерцовом писюке.
|
| | | |
Тут понятие дефференциируемости неуместно 14.08.04 00:19
Автор: Heller <Heller> Статус: Elderman
|
|
Функция определена на N и следовательно такие понятия как "бесконечно малая" и иже с ними тут не работают. Но всё равно даже дать приблизительную оценку невозможно. Конкретного доказательства я не смогу привести, но достаточно просто построить график этой функции и посмотреть как она себя ведёт.
|
| | | | |
Раз речь пошла про экстремумы... 14.08.04 00:37
Автор: whiletrue <Роман> Статус: Elderman
|
> Функция определена на N и следовательно такие понятия как
> "бесконечно малая" и иже с ними тут не работают. Но всё
> равно даже дать приблизительную оценку невозможно.
> Конкретного доказательства я не смогу привести, но
> достаточно просто построить график этой функции и
> посмотреть как она себя ведёт.
Я поэтому и говорю про дифференцируемость, ибо другого способа нахождения минимумов не знаю.
Думаю, теперь DPP ясно, что задача некорректна.
Когда ф-ция дифференцируема, тогда предыдущая точка как бы жестко связана со следующей... поэтому для нее можно много че хорошего вычислить, а в этом случае каждая следующая точка ведет себя "непредсказуемо".
|
| | | | | |
Пример в тему 14.08.04 01:04
Автор: Heller <Heller> Статус: Elderman
|
> Я поэтому и говорю про дифференцируемость, ибо другого
> способа нахождения минимумов не знаю.
Конкретного способа на самом деле и не существует, однако если взять, например, функцию "наборот" f(x)=x mod n на всём множестве N, то она так же недифференциируема, однако мы можем определить минимумы - это kn. Поэтому и без дифференциирования хотя бы примерно область минимумов указать можно. В случае DPP, если число ~2^1024, то мы можем достаточно точно предположить, что минимум будет ~2^512 :-) Однако такие предположения сводятся к обычному перебору, к сожалению.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
