Задача для матметода Яна

[Alexey Kurtakov]

Hi All,

Референсы:
1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. -М.:
Советское радио, 1968, -440с.
2. www.rsa.com -> RSALabs

Задача. Дано составное число N. Требуется найти его разложение на множители.
Частный случай - два близких (относительна размера чисел) по размеру больших
простых множителя.
На сложности данной задачи базируется криптостойкость алгоритма RSA.

Остаточные классы.
В соответствии с китайской теоремой об остатках:
по остаткам числа от его деления на взаимно простые числа P1,P2,...,PK,
возможно однозначное восстановление данного числа при условии что оно меньше
произведения P1*P2*...PK.

Операции кольца (сложение, вычитание, умножение) можно проводить независимо
(паралельно)
со всеми остатками.
A*B=(A1*B1, A2*B2, ... , AK*BK), где AI и BI - остатки от деления A и B на
Pi.

Операции вызывающие сложность в реализации:
деление, сравнение, выход за диапазон (его расширение).

Вид моего генератора:
Берутся два случайных простых числа заданного размера (возможно разного).
Ищется их произведение.
В качестве оснований для системы остаточных классов беруться первые простые
числа
начиная с 3. В количестве необходимом для однозначного представления числа N.
Перевод произведения в остаточные классы - ВХОД.
Перевод сомножителей в остаточные классы - ВЫХОД.


Фальсификация Яном невозможна!
Ибо: любой участник спора может сгенирировать вход (при этом он будет знать
выходы)
и сообщить его Яну, если Ян правильно найдет выходы значит либо его
"отмывание черного ящика работает", либо он нашел алгоритм факторизации чисел
пока неизвестный всем остальным!
(Просьба не подавать на вход заведомо простое число - это проверяется
средствами простой математики).

Для любого входа существует тривиальное решение: ВЫХОД1=ВХОД, ВЫХОД2=E. E=(1,
1, ..., 1).

Вопросы:

1 Ян, возможно ли решение данной задачи вашим методом?
2 Ян, возможно следует изменить форму входных данных, укажите какой формой Вам
будет легче оперировать.
3 Ко всем. Насолько соответствует данная задача этой эхе, учитывая что метод
решения будет базироваться на ИИ?

К модератору. По вашему требованию готов перенести дальнейшее обсуждение в
другие эхи (ru.math, ru.algorithms),
но вопрос опробирования метода Яна Кромарчука начал обсуждаться здесь, вся
переписка по этому вопросу находится
в этой эхе, поэтому считаю логичным полученые результаты оставлять в этой эхе
а не раскидывать по соседским дворам.

ЗЫ ниже написан нормальный почтовый ящик.

С уважением, Алексей. ***@stv.ru

[Yan Korchmaryuk]

Hello, Alexey!
Colleague(s) !

■ Quoting message from Alexey Kurtakov to All
■ [29 May 05 at 11:06]


AK> Референсы:
AK> 1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах.
AK> -М.: Советское радио, 1968, -440с.
AK> 2. www.rsa.com -> RSALabs

AK> Задача. Дано составное число N. Требуется найти его разложение на
AK> множители. Частный случай - два близких (относительна размера чисел) по
AK> размеру больших простых множителя.
AK> Hа сложности данной задачи базируется криптостойкость алгоритма RSA.

Эх, ничо себе! Это же задача, эквивалентная "найти закономерность в
распределении простых чисел"!!! Поскольку на множители всякое число, по
основной теореме арифметики, раскладывается по степеням простых чисел, и никак
иначе!
Есть, наработаны за годы истории математики, разные апроксимации распределений
простых чисел. И я отдал дань, в свое время, этому труду. Kогда занималчя
теорией фракталов. И первым дело, конечно же, прогнал машину на ряду простых
чисел. Так вот, она выдает хорошую _апроксимацию_. Поскольку конечный ее
результат - построение блок-схемы из белых ящиков, в каждом из которых сидит
какая-то элементарная функция математики, какое-то элементарное передаточное
звено.
Этой задачей - я заниматься HЕ БУДУ!
Принципиально.
Сначала докажите мне теорему.
Что простые числа, их распределение, могут быть описаны конечным счетным
набором элементарных функций ...

AK> Остаточные классы.
AK> В соответствии с китайской теоремой об остатках:
AK> по остаткам числа от его деления на взаимно простые числа P1,P2,...,PK,
AK> возможно однозначное восстановление данного числа при условии что оно
AK> меньше произведения P1*P2*...PK.

Знаю. См. выше.

AK> Операции кольца (сложение, вычитание, умножение) можно проводить независимо
AK> (паралельно)
AK> со всеми остатками.
AK> A*B=(A1*B1, A2*B2, ... , AK*BK), где AI и BI - остатки от деления A и B
AK> на Pi.

См. выше.

AK> Операции вызывающие сложность в реализации:
AK> деление, сравнение, выход за диапазон (его расширение).

См. выше.

AK> Вид моего генератора:
AK> Берутся два случайных простых числа заданного размера (возможно разного).
AK> Ищется их произведение.
AK> В качестве оснований для системы остаточных классов беруться первые простые
AK> числа
AK> начиная с 3. В количестве необходимом для однозначного представления числа
AK> N. Перевод произведения в остаточные классы - ВХОД.
AK> Перевод сомножителей в остаточные классы - ВЫХОД.


AK> Фальсификация Яном невозможна!

Вы ошибаетесь.

Я уже провел статанализ, по неполному и зашумленному набору данных,
опубликованных Вами. Всеми имеющимися у меня статпакетами, по всем доступным
методам. У меня теперь уже есть функции распределения вероятностей, которыми я
с достаточной точностью могу генерить тройки удовлетворяющих распределению
чисел.

AK> Ибо: любой участник спора может сгенирировать вход (при этом он будет знать
AK> выходы)
AK> и сообщить его Яну, если Ян правильно найдет выходы значит либо его
AK> "отмывание черного ящика работает", либо он нашел алгоритм факторизации
AK> чисел пока неизвестный всем остальным!

Вы ошибаетесь. Забывая про "достаточную точность".
Если такого алгоритма нет ни у кого - никто не сможет опровергнуть найденные
мною выходы. Это уже Вам придется "доказывать", что они не удовлетворяют
закономерности. Вы же - не знаете такой закономерности, верно? Kакможно
осуждать за нарушения закона, не зная самого закона?

AK> (Просьба не подавать на вход заведомо простое число - это проверяется
AK> средствами простой математики).

AK> Для любого входа существует тривиальное решение: ВЫХОД1=ВХОД, ВЫХОД2=E.
AK> E=(1, 1, ..., 1).

AK> Вопросы:

AK> 1 Ян, возможно ли решение данной задачи вашим методом?
AK> 2 Ян, возможно следует изменить форму входных данных, укажите какой формой
AK> Вам будет легче оперировать.
AK> 3 Kо всем. Hасолько соответствует данная задача этой эхе, учитывая что
AK> метод решения будет базироваться на ИИ?

Ответ.
Я _не_ _буду_ заниматься СЕЙЧАС данной задачей.
Потому что она - ФУHДАМЕHТАЛЬHА!!!
А моя машина - всего лишь генерит аппроксимирующий набор белых ящиков. Со сколь
угодно достаточной для практики точностью найденного решения. А не заменяет
собой гения-математика.
Это - ясно?

AK> K модератору. По вашему требованию готов перенести дальнейшее обсуждение в
AK> другие эхи (ru.math, ru.algorithms),
AK> но вопрос опробирования метода Яна Kромарчука начал обсуждаться здесь, вся
AK> переписка по этому вопросу находится
AK> в этой эхе, поэтому считаю логичным полученые результаты оставлять в этой
AK> эхе а не раскидывать по соседским дворам.

AK> ЗЫ ниже написан нормальный почтовый ящик.

AK> С уважением, Алексей. ***@stv.ru
^^^^^^^^^^

Это вот этот?

Мне тут Йож уже давал подсказки.
И я опять, вчера еще, пытался забросить Вам файл, и опять неудачно.
Kороче, мой провайдер ВООБЩЕ не может ничего доставлять на stv.ru.
Почему - не знаю. :(
Попробуйте купить карточку, и временно завести ящик там, где я Вас просил:
rambler.ru, interdacom.ru, mail.ru

Yours faithfully,
Yan Korchmaryuk (Synergetic). (B-})

[Alexander Prudaev]

Hello, Yan!

30 Май 05 03:20, Yan Korchmaryuk wrote to Alexey Kurtakov:

AK>> Референсы:
AK>> 1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных
AK>> классах. -М.: Советское радио, 1968, -440с. 2. www.rsa.com ->
AK>> RSALabs

AK>> Задача. Дано составное число N. Требуется найти его разложение на
AK>> множители. Частный случай - два близких (относительна размера
AK>> чисел) по размеру больших простых множителя. Hа сложности данной
AK>> задачи базируется криптостойкость алгоритма RSA.

YK> Эх, ничо себе! Это же задача, эквивалентная "найти закономерность в
YK> распределении простых чисел"!!! Поскольку на множители всякое число,
YK> по основной теореме арифметики, раскладывается по степеням простых
YK> чисел, и никак иначе! Есть, наработаны за годы истории математики,
YK> разные апроксимации распределений простых чисел. И я отдал дань, в
YK> свое время, этому труду. Kогда занималчя теорией фракталов. И первым
YK> дело, конечно же, прогнал машину на ряду простых чисел. Так вот, она
YK> выдает хорошую _апроксимацию_. Поскольку конечный ее результат -
YK> построение блок-схемы из белых ящиков, в каждом из которых
YK> сидит какая-то элементарная функция математики, какое-то элементарное
YK> передаточное звено. Этой задачей - я заниматься HЕ
YK> БУДУ! Принципиально. Сначала докажите мне теорему. Что простые числа,
YK> их распределение, могут быть описаны конечным счетным набором
YK> элементарных функций ...

последнее уже сделано. известна эта самая функция от 26
переменных, есть и другие функции от одной переменной.
всё доказано. обратите внимание на результаты Ю. В. Матиясевича
о диофантовости рекурсивных множеств (опубликовано в 1970 году),
существуют многочлены, множество положительных значений которых в
точности является множеством всех простых чисел.
у меня есть этот самый многочлен в .htm файле, могу кинуть
в ууе - 910 байт, но только с разрешения [ко]модератора.

Alexander

All around
an eerie sound

[Yan Korchmaryuk]

Hello, Alexander!
Colleague(s) !

■ Quoting message from Alexander Prudaev to Yan Korchmaryuk
■ [30 May 05 at 18:26]

YK> БУДУ! Принципиально. Сначала докажите мне теорему. Что простые числа,
YK> их распределение, могут быть описаны конечным счетным набором
YK> элементарных функций ...

AP> последнее уже сделано. известна эта самая функция от 26
AP> переменных, есть и другие функции от одной переменной.
AP> всё доказано. обратите внимание на результаты Ю. В. Матиясевича
AP> о диофантовости рекурсивных множеств (опубликовано в 1970 году),

Это любопытно. Где посмотреть?

AP> существуют многочлены, множество положительных значений которых в
AP> точности является множеством всех простых чисел.
AP> у меня есть этот самый многочлен в .htm файле, могу кинуть
AP> в ууе - 910 байт, но только с разрешения [ко]модератора.

Hе стОит. Отпишите мне в мыло свой емайл, я вам тоже отпишу емайлом, и если
пройдет, кинете мне аттач на емайл.

Yours faithfully,
Yan Korchmaryuk (Synergetic). (B-})

[Michael Tulupov]

Пpиветствую, Alexander!

AP> у меня есть этот самый многочлен в .htm файле, могу кинуть
AP> в ууе - 910 байт, но только с разрешения [ко]модератора.
А из HTM вынуть текст и написать так ?
Хотя бы урл кинь на источник.

P.S.: Ян опять отмазался.
Счётчик ожидания сбрасывается.
Мне тоже ничего не пришло.

Michael Tulupov
...

[Alexander Prudaev]

Hello, Michael!

31 Май 05 08:35, Michael Tulupov wrote to Alexander Prudaev:

AP>> у меня есть этот самый многочлен в .htm файле, могу кинуть
AP>> в ууе - 910 байт, но только с разрешения [ко]модератора.
MT> А из HTM вынуть текст и написать так ?
MT> Хотя бы урл кинь на источник.

написать функцию от 26 переменных? а я что очень похож
на мазохиста? не думаю, что вы бы стали этим заниматься.
кроме того я попытался проверить эту функцию, и получил
интересные результаты. функция не всегда работает, т.е.
выдаёт составное число, я объясняю это тем что либо сам
допустил ошибку в её написании либо её допустил тот, кто
забивал в htm. урл не помню.

вот функция от одного аргумента, выражающая
простое число через его номер:

n^2+1 m
-- / -- / \\
\ | \ | ┌ ┐||
P(n)= / Zn| n-/ | ((k-1)!)^2 - k*|((k-1)!)^2/k|||
-- \ -- \ └ ┘//
m=0 k=2

Zn(x)=1, если x>0
Zn(x)=0, если x<=0

MT> P.S.: Ян опять отмазался.
MT> Счётчик ожидания сбрасывается.
MT> Мне тоже ничего не пришло.

да что отмазлся?! Может быть у него действительно
есть какой-нибудь свой способ, метод, но вот только
эксперимент поставить, нет ни желания, ни времени, ни
средств. А сколько дней Ян требует E-mail?
Ящик на яндексе зарегистрировать не судьба?

кроме того на N входов-выходов можно подобрать множество
функций у которых N-1 вход-выход будут совпадать, а эNный
выход будет отличаться. Чем ваша функция лучше или хуже
функции которая будет получена по методу Яна?
я не вижу смысла в предлагаемом вами эксперименте.
что требуется сделать яну? - найти функцию с совпадающими
входами-выходами для N заданных?

Alexander

[Yan Korchmaryuk]

Hello, Alexander!
Colleague(s) !

■ Quoting message from Alexander Prudaev to Michael Tulupov
■ [01 Jun 05 at 01:19]

MT> P.S.: Ян опять отмазался.
MT> Счётчик ожидания сбрасывается.
MT> Мне тоже ничего не пришло.

AP> да что отмазлся?! Может быть у него действительно
AP> есть какой-нибудь свой способ,

Действительно, есть.

AP> метод, но вот только
AP> эксперимент поставить, нет ни желания, ни времени, ни
AP> средств.

Желание - есть. Всего остального - нет.

AP> А сколько дней Ян требует E-mail?

Именно.
А мы все еще не можем такую элементарнейшую вещь сделать, как "сверка данных".
А работать на грязных данных - я принципиально не буду!
Это профанация самой идеи.

AP> Ящик на яндексе зарегистрировать не судьба?

За час можно было бы.
И стоит-то всего 100 р, цена карточки.

AP> кроме того на N входов-выходов можно подобрать множество
AP> функций у которых N-1 вход-выход будут совпадать, а эNный
AP> выход будет отличаться. Чем ваша функция лучше или хуже
AP> функции которая будет получена по методу Яна?

Тоже верно.

По статистике, которую я ручками получил на грязных данных, она имеет
существенно ценозный вид. Т.е., речьидет о мультифрактале.
Имеющем обратностепенное (Ципфа-Бредфорда-Парето) распределение, до
третьего порядка и выше.

Это значит, что я могу так настроить ГСЧ, что он будет выдавать случано
распределенные величины. И они формально будут удовлетворять условию задачи.

AP> я не вижу смысла в предлагаемом вами эксперименте.

Я тоже. Он архинекорректен!

AP> что требуется сделать яну? - найти функцию с совпадающими
AP> входами-выходами для N заданных?

Похоже, народ вообще не знает, что такое "САР". :(

Yours faithfully,
Yan Korchmaryuk (Synergetic). (B-})

[Dmitry Batov]

Привет _Alexey_ ! Пишет тебе *Dmitry* !

29 Май 05 11:06, _Alexey Kurtakov_ ══ /All/:


AK> Задача. Дано составное число N. Требуется найти его разложение на
AK> множители. Частный случай - два близких (относительна размера чисел)
AK> по размеру больших простых множителя. Hа сложности данной задачи
AK> базируется криптостойкость алгоритма RSA.

можно конечно подойти и алгоритмически, но проблема скорей
алгоритмически-аппаратная. С испокон веков к сложным вычислительным процессам
подходили индексированными таблицами. С развитием плотности записи оптических
систем, появилась возможность создавать очень большие носители с многослойной и
голографической записью. это для дисков. но если это переколбасить на довольно
широкую ленту - типа как голограммы для кассовых аппаратов, можно получить
объемы во много порядков выше.

объем таблицы можно сократить убирая избыточность. ленту можно кэшировать в
дисковом массиве на 3 уровне, в ОЗУ на 2 уровне, и проце на 1 уровне. задача
сведется к линейной оптимизации механических перемещений порционных вычислений

помнится на старых вычислительных комплексах с магнитной лентой были аппараты с
ваакумным натяжением ленты и способных перематывать довольно быстро километры
пленки, не буду даже комментировать на сколько данный носитель будет емким по
сравнению с Blu-Ray при многоцветном и голографическом способе записи

ИМХО без аппаратно-программного комплекса такие вещи на ширпотребе пока не
решаются. вот если начнут штамповать стабильные мощные квантовые компьютеры -
тогда да, но ведь сразу-же сменят принципы кодирования :)

[Moderator of RU AI]

┌┴┴┴┴┴┴┴┴┐ С горячим электронным приветом!
└┬┬┬┬┬┬┬┬┘ Цитирую: Alexey Kurtakov -> All, 29 Май 2005

AK> К модератору. По вашему требованию готов перенести дальнейшее
AK> обсуждение в другие эхи (ru.math, ru.algorithms), но вопрос
AK> опробирования метода Яна Кромарчука начал обсуждаться здесь,
AK> вся переписка по этому вопросу находится в этой эхе, поэтому считаю
AK> логичным полученые результаты оставлять в этой эхе а не раскидывать по
AK> соседским дворам.

Продолжайте здесь.

С моих слов записано верно. Moderator of RU.AI.

... [Брутальные Маргиналы Team] [Pipe Smokers Team]