id: Гость   вход   регистрация
текущее время 05:21 22/01/2018
Автор темы: nonseriousman, тема открыта 21/12/2017 11:11 Печать
Категории: криптография, алгоритмы
http://www.pgpru.com/Форум/Криптография/ПростейшийАлгоритмРазложенияНаМножители
создать
просмотр
ссылки

Простейший алгоритм разложения на множители


Algorithm for factoring integers, so simple, that it may be realized even on an abacus.


Алгоритм разложения целых чисел на множители, настолько простой, что его можно реализовать
даже на конторских счетах.



The algorithm is composed by me, Miliaev Viktor Konstantinovich, born 26, July, 1950.
It is written in MQL4 15.12. 2017. E-mail: tenfacet27@gmail.com


Алгоритм сочинил я, Миляев Виктор Константинович, дата и место рождения: 26 июля 1950 года,
г. Борисоглебск Воронежской обл.
Он написан 15 декабря 2017 года на языке MQL4. E-mail: tenfacet27@gmail.com


 
Комментарии
— ВасВас (25/12/2017 15:52)   профиль/связь   <#>
комментариев: 5   документов: 0   редакций: 0
Интересно... Чем-то похож на мой годичной давности)))
В вашем алгоритме для факторизации числа 341 надо сделать 309 сравнений "d и b" а в моём всего 32 раза некоторго "х" с нулём))) И у меня всего 3 действия в каждом из условий)))
А вообще по факту алгоритмически быстрее тупо последовательно перебирать множители от 2 до N.
Добавте в ваш код функцию вывода c,a,d,b в каждое сравнение d и b после всех вычислений, и всё будет понятно.
— nonseriousman (27/12/2017 00:04)   профиль/связь   <#>
комментариев: 2   документов: 2   редакций: 0
Нельзя ли прислать ваш алгоритм?
— ВасВас (27/12/2017 12:22, исправлен 27/12/2017 12:28)   профиль/связь   <#>
комментариев: 5   документов: 0   редакций: 0

\код на Python 3:\


Интересно что чётность начальных квадратов совпадает с чётностью квадратов из ответа. Также совпадают остатки чётных квадратов при делении на 4.

— nonseriousman (28/12/2017 22:45)   профиль/связь   <#>
комментариев: 2   документов: 2   редакций: 0
Уважаемый ВасВас,
Нет смысла сравнивать время работы этих двух программ на нескольких конкретных числах. Ни вы, ни я не знаем, какова их асимптотическая сложность. Я просто еще этим не занимался. Но дело совсем не в этом, а в том, что ваша программа – реализация «метода Ферма», который известен уже триста лет
Мой же алгоритм основан на совершенно другой идее, которая, насколько я на настоящий момент в курсе, является новой, не появлявшейся еще в теме «факторизация». Мне кажется, что пока я не должен описывать эту идею, хотя, конечно, когда-нибудь я это сделаю. Однако, очень может быть, что кто-то, глядя на программу, и сам догадается, на какой идее она основана, и тогда для него сразу отпадет вопрос о корректности моего алгоритма.
— ВасВас (29/12/2017 12:07)   профиль/связь   <#>
комментариев: 5   документов: 0   редакций: 0
Вопрос стоит не о корректности а о целесообразности. не мой не ваш для факторизации использовать не целесообразно, но они хорошо подходят для понимания сути того что происходит с числами. А это понимание может хорошо помочь в поиске эффективного алгоритма.
— ВасВас (29/12/2017 13:13)   профиль/связь   <#>
комментариев: 5   документов: 0   редакций: 0
Сейчас я занимаюсь проверкой своих идей, надеюсь я их пройду за выходные, о результатах возможно напишу сюда.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3