следующая тема »

[Антон Серго]

2 All: держитесь в рамках темы (см. сабж.)!

[Urix]

Дмитрий! Я подобрал для Вас пример. В качестве делителей берутся простые 5 и 7. Как видно, мантиссы чисел (второй числовой столбик) удовлетворяют условию теоремы. И окончательные "загоны", особенно последний. 3,501<5<7<9,999.

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

Да, а 9999, 3501 и 1001 получаются потому, что я сразу исключаю тривиальные случаи 1 и N.

E2    1,00   9999
 P      7,00   7000
 M      5,92   5916
 Q      5,00   5000
 N    35,00   3501
N2 1225,00   1225
E1    1,00   1001
====================
3   9999,0   3501,0
2   999,90   350,10
1   99,990   35,010
0   9,9990   3,5010

SQRT((E2+1)*N)=5916,0797
SQRT(P*Q)=5916,0797
SQRT((E2+1)*N2)=3500

Что касается русского языка, то в нем очень важную роль играет слово "если".

P.S. Где-нибудь на следующей неделе я опубликую в приложении №4 программу, реализующую целочисленную часть алгоритма. Потом, где-то через месяц полный алгоритм уже в приложении №5. И в приложении №6 приведу алгоритм, вычислительная сложность которого для больших чисел является логарифмом от квадрата логарифма N. log2(log2(N)^2)=20 операций "огораживания" для 1000-разрядных чисел.

Или дать кому-то из молодых возможность отличиться самостоятельно? Ваше мнение, друзья?

[Urix]

Виталий!

Как там было? "Не учите меня жить, а лучше помогите материально".

Пожалуйста, если не сложно, скажите Антону, что точно должно стоять и он поправит. А то я ему шлю текст, он его потом переводит для сайта, а текст на экране расползается. Оба мы в это время материмся...

[BeeVee]

По-моему, нужно просто дать уважаемому Urix сообщение, зашифрованное алгоритмом RSA с хорошей длиной ключа, и попросить расшифровать его за сутки.

А там видно будет, кто здесь прав.

Как вам такой вариант?

[Dmitry]

Urix, я чрезвычайно рад, что вы все-таки сумели найти пример, подтверждающий вашу теорему. Хочу только обратить ваше внимание, что в математике нет такого понятия как доказывающий пример, зато есть понятие опровергающего примера. И неважно сколько подтверждающих примеров найдено, если известен хоть один опровергающий (см. мое предыдущее сообщение), все остальные пасы руками бесполезны - фокус провалился, теорема неверна. Поэтому повторюсь - мне очень нравится факторизовать число 55. Поэтому разрешите я в соответствии с вашим алгоритмом QFACT начну его факторизовать прямо здесь.

N=55 < 2⁶-1, следовательно  k=6  и i=0, 1,...5

i = 0 a₀=2

E2	1.00	4096
M	7.42	3797
N	55.00	3520
N2	3025.00	3025
E1	1.00	2048

Ура, условие теоремы выполнено M > N > N2, значит можно начинать загонять львов в загон [N;E2]

3520 - 4096
1760 - 2048
880 - 1024
440 - 512
220 - 256
110 - 128
55 - 64
27 - 32
13 - 16
6 - 8
3 - 4
1 - 2

Ooops (I did it again). Мы еще даже ружья не достали, а наши львы 5 и 11 похоже уже видали в гробу всякие загоны, муары, голограммы и Геделя и гуляют себе на свободе несмотря (или здесь все-таки не смотря) на все наши шаманские танцы с бубнами. Все Uriх, ну нафиг такую охоту, сожрут еще, охотьтесь один.

PS. Если вы обратили внимание я изменил порядок перебора i, начав с 0. Можете проверить на досуге, здесь нет никакой хитрости. Мне посто не хотелось утомлять других наблюдением того, как охотники сначала бестолково слоняются по заповедникам, где охота запрещена, а потом молча наблюдают за тем, как львы начинают разбегаться сначала по одному прежде чем рвануть из загона сразу всей стаей.

[Urix]

Дмитрий! Спасибо, что поправили.

Антон не даст соврать, у него есть одно из первых описаний, в котором еще присутствует теорема о проекциях чисел на интервале выравнивания. Совсем упустил ее из виду когда занимался сокращениями текста. В самой первой версии, которую никто не видел, было 11 лемм и 2 теоремы на 34 листах. Вот Вам и пример того, как проявляет себя суррогратное, упрощенное знание. Из-за потери нюансов получается нонсенс. Необходимое условие осталось, а вот достаточное утеряно.

Смысл теремы о проекциях в том, что если в границы "загона" не попадает число sqrt(a)*a^n, то берутся два загона [N:a*a^n],[N/sqrt(2):sqrt(a)*a^n] для sqrt(a)*a^n<N<E2 и [a^n:N],[sqrt(a)*a^n:sqrt(a)*N] для E1<N<sqrt(a)*a^n. В основе теоремы лежат свойства произведений sqrt(a)*sqrt(a)=a, sqrt(a)/sqrt(a)=1 и M*M=N*E=P*Q

Для рассматриваемого случая имеем
2^12/sqrt(2)=2896,30937...
N''=N'/sqrt(2)=2489,01586...

Соотвественно, дополнительные загоны получаются такими:
2489,0158 - 2896,3093
1244,5079 - 1448,1546
622,2539 - 724,0773
311,1269 - 362,0386
155,5634 - 181,0193
77,7817 - 90,5096
38,8908 - 45,2548
19,4454 - 22,6274
9,7227 - 11,3137
4,8613 - 5,6568
2,4306 - 2,8284
1,2153 - 1,4142

Как видно, целые делители четко попадают в дополнительные "загоны". Так что "львам" все равно деваться некуда. Они пойманы. И голограммы теперь уже на каждом углу можно встретить. И Гёделя пока никто не опроверг. И из "мало" нельзя сделать "много".

Сегодня вечером дополню описание алгоритма.

[Dmitry]

Юрий, я рад, что смог хоть чем-то оказаться полезным и буду с нетерпением ожидать внесения необходимых исправленний, но тем не менее хотел бы:
1. Обратить ваше внимание, что в рассмотренном случае для нахождения делителей числа 55 достаточно было перебрать всего 6 чисел, ни одно из которых с учетом новых дополнений так и не было отсеяно. Возможно в других случаях и будет достигнут какой-то выигрыш, но пока сама его возможность, не говоря уж о его величине, для меня увы не очевидны.
2. Торжественно заявить, что пока вы сами не произнесете здесь что-то типа: "Мамой клянусь, вот текст, в котором никто не забыт, и ничто не забыто!" - даже не взгляну на него больше.

ЗЫ. Да, совсем забыл, когда будете вносить изменения, обратите пожалуйста также внимание, что для рассмотренного случая отмечен также тот прискорбный факт
SQRT((E2)*N)=3797,09
SQRT(P*Q)=SQRT(2560*2816)=2684,95
Правда зато
SQRT((E1)*N)=2684,95, но тогда хотелось бы более четкого понимания, каковы точные границы интервалов.

[Urix]

Я этим алгоритмом занимась давно и он мне надоел хуже горькой редьки. Хочу побыстрее выловить всех bug-ов в описании и забыть о нем раз и навсегда. Есть вещи поинтереснее.

Тут Вы ошиблись. Перебрать надо не 6, а всего 3 числа: 2,3,5 до первого делителя. Тривиальные случаи рассматривать нет смысла. Учитывать их надо, но не тратить на них время. Отсев в алгоритме осуществляется на шаге №5. Или, что возможно будет лучше, делать компромисс между вычислениями "загонов" и проверками на делимость прямо в функции "огораживания". Поэтому, в приведенном мной примере первым числом, которое нужно проверить на делимость будет целое число 5, как попавшее в интервал 4,8613 - 5,6568, а в Вашем примере число 7, как попавшее в интервал 6-8. Но, 5 проверяется раньше, значит надо сделать всего одну проверку на делимость, а не три. Вот Вам уже и выигрыш, хотя и маленький, по числу проверок на делимость.

Что касается неочевидной малости затрат. Надеюсь, что Вы не сможете опровергнуть, что для 1000-разрядного числа надо построить всего 1000 или 2000 проекций "загонов" на числовую ось для основания 2. А учитывать надо всего лишь 500 или 1000, поскольку хотябы один делитель, если число не простое, обязательно меньше sqrt(N). Для других целых оснований, больших 2, проекций "загонов" на числовую ось будет меньше. Вот Вам и чисто логарифмическая зависимость. Я еще пока не встречал алгоритмов, которые давали бы логарифмические зависимости роста вычислительной сложности от роста числа N. Это первый. Существенный выигрыш должен проявлять себя на больших числах, поскольку операция "огораживания" сама по себе достаточно трудоемка. При росте числа оснований, совместные интервалы очень быстро уменьшаются в ширине и их количество сокращается, поэтому нет необходимости строить все проекции "загонов" для добавляемого основания. Это еще одно уменьшение вычислительных затрат.

P.S. Если Вы никогда ранее не видели датчиков положения, основанных на муаровых решетках с числом штрихов n/n+1, то советую Вам с ними ознакомиться. Многое прояснится и станет более понятным, поскольку это уже можно "пощупать руками".
P.P.S. Мамой клянусь - это выкручивание рук. Деструктивный подход. Я изложил идею, не нравится - не пользуйтесь. Я Вас не заставляю. Изложение идеи или даже сама идея может содержать ошибки, но это не основание для выкручивания рук.

[Dmitry]

Тут Вы ошиблись. Перебрать надо не 6

Признаю, после того как до трех ночи заборы в пустыне строишь и не такого еще можно написать.

[Urix]

Дмитрий! Я поправил статью и выслал её Антону Серго. Смотрите, что получается в результате на Вашем примере.

E2                   4096
sqrt(2)*P            3982
sqrt(N)               3797
sqrt(2)*Q            3620
N                     3520
sqrt(2)*E1           2896
P                     2816
sqrt(2)*sqrt(N)      2685
Q                     2560
sqrt(2)*N            2489
E1                   2048


Окончательные границы "загонов", которые надо проецировать на числовую ось, будут такими: 2489-2897 и 3520-4096. 2897 вместо 2896 появилось из-за ошибок округления. Соответственно, из-за ошибок округления интервалы, содержащие сами делители, будут 5-5 и 10-11, а не 4-5 и 9-11.

sqrt(2) появилось потому, что 5*512=2560 и 11*256=2816, и степень "хвоста" 512*256=2^9*2^8=2^17 получается нечетной, в то время как степень "хвоста" sqrt(N)*sqrt(N) будет четной. Для получения точного равенства E2*N=M*M=P*Q приходится домножать P и Q на sqrt(2). Иначе не выполняется A<C<D<B, если A*B=C*D, A<B, C<D, A<C.

И еще. Вполне возможно, что алгоритм не работает для каких-то чисел. Но для некоторых он работает и мы с Вами в этом убедились. Я брал большее количество чисел и больших значений. Если не для всех чисел работает, тогда это означает, что класс чисел, которые могут быть использованы для RSA, сужен. Вопрос - на сколько. И тогда это всего лишь еще один "камень в огород" RSA, а не на его "могилу". Но и это уже хорошо. Значит, надо исследовать, для каких чисел этот алгоритм не работает и почему. Так что...

P.S. А я пока допишу программулину и буду сам смотреть, что и как.