О факторизации

Тема в разделе "WASM.HEAP", создана пользователем UbIvItS, 5 янв 2007.

  1. crypto

    crypto Active Member

    Публикаций:
    0
    Регистрация:
    13 дек 2005
    Сообщения:
    2.533
    UbIvItS
    Ссылочку дай на такой кодекс :)
     
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    ты мне лучше либу дай, так как предварительные выкладки показывают, что дип у новой методы на реальном подсосе подрабатывает и эти выкладки надо проверить на деле. а ты в очередной раз занимаешься пустыми придирками - заняться больше не чем :))
     
  3. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    итак, на данный момент времени, я размышляю как использовать частично - адекватный критерий выбора бинарного треда (точней это можно назвать спуском). действует он следующим образом: n=p^2-pk, где q=p-k - критерий позволяет осуществить спуск до тех пор пока q>n^.5 - как только q<n^.5, критерий становится неадекватным.
    если у кого есть мысли как заюзать это дело - пишите: на форуме, мне - буду рад. одна голова хорошо, а Горыныч лучше :)))
     
  4. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    Итак, на сайт я выложил новую редакцию мана - добавил 2-е заметки: одна объясняет почему работает дип, а другая как малость улучшить брут форс. Впрочем, новые результаты оптимизма не внушают, но, наверняка, факторизация имеет простое решение - поэтому до него так трудно добраться. Если у меня хватит времени, я решу этот вопрос.
     
  5. halyavin

    halyavin New Member

    Публикаций:
    0
    Регистрация:
    13 май 2005
    Сообщения:
    252
    Адрес:
    Russia
    Не мелочись - ищи лучше контрпример к теореме Ферма. Ну и пусть ее доказательство оптимизма не внушает, но, наверняка, задача поиска контрпримера имеет простое решение - поэтому до него никому еще не удалось добраться. Если у тебя хватит времени, то ты построишь контрпример.
     
  6. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    За идею, конечно, спасибо.
    итак, если кто найдёт быстрый способ решения x+2xy+y=z
    z- известно
    x, y -??
    , то он решит вопрос факторизации.
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    ещё один путь: пусть мы знаем p+q=z(p,q-?? z-известно), тогда можно найти p & q по бинарному дереву.
    так что, если сделать методику нахождения пар чисел n & n0, n=p0*q0 (q0, p0-известно) n=pq (p,q-??), p+q=p0+q0=z
     
  8. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Удивительно, да? Вопрос зрителям: из какого тривиального утверждения получена эта "хитрая" формула? Надо будет задать вопрос классу 8-9ому, интересно, сразу ли увидят :)
     
  9. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    гмммм, причем тут хитрость и класс :))?? - здесь идет вопрос о форме представления числа n через, которое можно выйти на p & q. ты меня ещё упрекни в том, что я юзаю операции сложения/вычитания -----> ВЕДЬ ЭТО ВТОРОЙ ПЕРВЫЙ КЛАСС !!!!!!!!!!!!!!!...!!
     
  10. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    и, кстати, про число F(14) - числа ферма давно довольно быстро факторизируют - поюзай пакет mathematica
     
  11. halyavin

    halyavin New Member

    Публикаций:
    0
    Регистрация:
    13 май 2005
    Сообщения:
    252
    Адрес:
    Russia
    Тем не менее никому F(14) разложить пока не удалось: http://en.wikipedia.org/wiki/Fermat_number . Как-только разложишь - приходи сюда. А тему давно пора стереть с сервера. Автору, если ему действительно интересна эта тема, советую для начала осилить http://en.wikipedia.org/wiki/Integer_factorization . Кроме того, в интернете есть электронные математические журналы. Если ты открыл что-то стоящее, то надо писать туда, а не на форум.
     
  12. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    в новой редакции мана я описал способ нахождения z. Щас я не делаю новых версий разбивалки, так как занимаюсь реализацией алгоса сжатия, с которым е...шился два года :))
     
  13. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    я проверяю алгосы на практике, а не пишу док - ва - поэтому путь в журналы по математике для меня заказан :)))
     
  14. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    еще один способ нахождения z(приближенно): ceil(n/2^i)+2^i - чётно --> z=ceil(n/2^i)+2^i, а в обратном случае -------> z=ceil(n/2^i)+2^i+1. так же можно юзать floor
     
  15. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    на сайт выкинул ман с алгосами сжатия, не много позже, солью сырец с примером реализации простейшей схемы.
     
  16. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    кстати, если кто захочет присоедениться по реализации алгосов сжатия - буду рад.
    и помните: факторизацией я заниматься не перестал :)) - есть две новые весьма любопытные методы, но руки пока не дотягиваются их прокатить.
     
  17. Ultrin Faern

    Ultrin Faern New Member

    Публикаций:
    0
    Регистрация:
    25 июн 2006
    Сообщения:
    170
    А что - в алгоритмах сжатия есть что-то новое?
    Насколько я знаю сейчас есть три варианта
    1) LZ-подобные - поиск\замена кодом подстрок
    2) Коды Хафмана
    3) Арифметическое сжатие

    Первый вариант самый распостраненный, последний вариант самый крутой (теоретически).

    Насчет факторизации . Предлагаю - выложить число N=p*q из сертификата Микрософта. И ждем здесь в студии числа p и q по вашему алгоритму. А до выхода этих чисел больше воду в ступе толочь не стоит. :)
     
  18. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    ну, во-первых, выложеные алгосы по сжатию работают по совершенно иному принципу, чем перечисленные: если в этих трех код распухает, то в dscc он наоборот сужается(само название, кстати, говорит о главном отличии: кодируется место в файле, а не вероятность; место в словаре). координатки способны работать на файлах с заведомо малой избыточностью. еще пример (dscc vs. ариф. сжатия) : ариф. сжатие не способно юзать код второй раз - dscc способно, короче, читай и сам поймешь в чем различия.
    насчет факторизации: я не говорю, что способен прямо сейчас разбить любое число. и даже, если я разобью сертификат ms - я не стану себе подписывать место в тюряге:))
     
  19. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    тот, кто перенёс мою тему в разряд базара видимо считает, что я в чём - то сильно не прав: мне интересно увидить доводы, может быть они и впрям верны.
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    и, кстати, если кто подумал, что в этих строчках я говорю о некоем вечном двигателе алгосов сжатия(я ещё до такого оптимизма не дожил):))), то это совершенно неверное предположение ----------> внимательно читайте ман.