Принципиально новый подход (к факторизации)

[незваный гость]

LazyCat писал(а):

Вы знаете как эти операции реализованы в конкретной программе, сколько мусора насыпал компилятор при создании исполнимого машинного кода, сколько тактов тратит просессор на исполнение одной такой комманды, есть ли конвейер команд, есть ли распараллеливание выполнения команд (не путать с распараллеливанием вычислений), какова тактовая частота процессора ???

Не знаю. Зато знаю, что при эти параметры нужны при определении скорости работы программы. Для определения сложности алгоритма используется число базовых операций. При этом число операций, естественно, зависит от того, какие базовые операции имеются. Например, доступность взятия целой части (деления нацело) может существенно изменить сложность некоторых задач (наилучший известный алгоритм).

Кроме того, скорость роста сложности — это скорость роста, а реальное время зависит еще и от того, где мы начинаем. Вот тут-то и играет то, что Вы упомянули. Но об этом говорить, когда нет еще и алгоритма, рано.

[LazyCat]

Прошу прощения, если Вы восприняли мои замечания как неуважение к участникам форума.
Просто кроме worm2 никто даже не захотел понять сути происходящего. Я не предполагал, что они настолько далеки от прикладного программирования и ,тем более , аппаратных реализаций чего-либо. Это не является оскорблением либо переходом на личности.
А с уважаемым супермодератором мы вместе свиней не пасли и называть меня обиженным ребенком Вам непозволительно !!!
Теперь несколько пояснений:
2 worm2 & Руст - в запарке я несколько неудачно написал b = sr(n), подразумевалось b = n / 2 целочисленно (кстати, для RSA n всегда нечетно, но это особой роли не играет, всегда можно "отбросить" правые нули)
2 tolstopuz - мои высказывания означают, что при одной и той же общей эффективности (если хотите - времени исполнения) аппаратная реализация может быть намного менее оптимальна чем чисто программная (надеюсь Вы не против здравого смысла)
2 незваный гость - молодца !!! именно это я и имел ввиду, особенно если учесть невысокую эффективность этих базовых операции на обычных ПК (на специализированных компьютерах, естественно, эти операции высокоэффективны и даже выделены отдельными машинными инструкциями)

[Macavity]

LazyCat писал(а):

Просто кроме worm2 никто даже не захотел понять сути происходящего.

Что значит не захотели понять, если Вы с самого начала наделали кучу ошибок в алгоритме, да еще и не описали что такое sr()? Вы бы к себе эти претензии обратили... А Вам дали конкретные замечания. И если Вы так уверены в алгоритме, то почему ссылки на RSALab восприняты с обидой?

[LazyCat]

Даже несмотря на наличие ОДНОЙ ошибки только worm2 кинулся проверять алгоритм на компьютере, но остальные не захотели проверить его хотя бы на бумаге.
Функция sr() была подробнейшим образом описана в первом посте (правда на английском)
Насчет RSA никаких обид небыло, было непонимание. Я сказал, что алгоритм интересен но очень сырой и пока ни о какой практической применимости речь не идет. Обратился с призывом к профессионалам (я по образованию не математик) довести идею до формулы и наказать американцев за самоуверенность с их конкурсами. Только и всего.

[нг]

LazyCat,
Замечание за пререкания с модератором. Любые комментарии действий модератора следуют направлять исключительно через ЛС (личные сообщения, ).

Независимо от того, с кем Вы пасете (или не пасете) свиней, я вынужден оценивать Вашу реакцию на критику. Работа у меня такая.

И еще один момент. Никто, я подчеркиваю, никто не обязан проверять и дорабатывать Ваши алгоритмы. worm2 проверил — честь ему и хвала. Остальные дошли до первой ошибки, так нечего их хулить. Задумайтесь: «Я сказал, что алгоритм интересен». Кому он интересен? Вам? Или профессионалам? Но если последнее, то почему Вы, непрофессионал, так уверенно говорите за них?

[LazyCat]

С супермодератором я абсолютно согласен, но призываю всех(вне зависимости от профиля работы) не переходить на личности. Это только вредит делу. Столько постов и одни только выяснения отношений. Это первое. Второе, я НИКОГО и НИКЧЕМУ не обязываю. Я просто советуюсь. Как Вы, уважаемый супермодератор, отнесетесь к человеку, который вместо помощи и совета пошлет Вас, например, на RSA. Кстати, ни Someone ни tolstopuz (которых Вы яростно защищаете) ни на одну ошибку не указали а развели флейм, мешая другим плодотворно работать !!! Перед созданием поста я внимательно изучил остальные ветки форума и прекрасно знаю на чьи посты и как реагировать(игнорировать, как не несущие никакой полезной информации).
А алгоритм я назвал интересным только потому, что он нестандартен и тем не менее работает. Еще раз повторю, я обратился сюда за помощью а не за выяснением отношений.
Прошу кого-нибудь внятно ответить расчитывать ли мне на какие либо конструктивные предложения или оказание помощи выходит за рамки данного форума ???

[Someone]

LazyCat писал(а):

Вот на досуге придумал алгоритм вычисления функции Эйлера с весьма эффективной аппаратной реализацией (даже в домашних условиях) :D

a = n;
b = n/2;
c = 0;
do {
  c++;
  if(!(a & 1)) {a>>=1; a+=b;}
  else a>>=1;
} while(a);

\phi(n) = 2c
or
\phi(n) = 4c

LazyCat писал(а):

Кстати, ни Someone ни tolstopuz (которых Вы яростно защищаете) ни на одну ошибку не указали а развели флейм, мешая другим плодотворно работать !!!

А зачем я дожен заниматься поиском ошибок? Я вижу, что Вы вычисляете функцию Эйлера последовательным сложением единиц. Для того, чтобы метод был практически интересным, его нужно применять к числам порядка $10^{200}$ и даже больше. Значение $\phi(n)$, конечно, меньше $n$, но не намного. Чтобы просуммировать $10^{200}$ единиц, не хватит времени существования Вселенной, даже если мы всю наблюдаемую часть Вселенной превратим в компьютеры и заставим их складывать эти самые единицы. И никакое аппаратное ускорение не поможет. Отсюда и моё "ехидство". Я ведь не первый раз сталкиваюсь с претендентами на открытие сверхэффективных методов разложения на множители, и всегда предлагаю им продемонстрировать свой алгоритм на деле, вместо того, чтобы трепать языком.

К тому же, Ваша процедура даёт ещё не функцию Эйлера, а какой-то её делитель. Вы предполагаете, что получается $\frac{\phi(n)}2$ или $\frac{\phi(n)}4$? Это неверно. Неверно даже то, что $\frac{\phi(n)}c$ является степенью двойки. А это означает, что, вычислив $c$, мы не будем знать, на что его умножить, чтобы получить $\phi(n)$, и даже не сможем быстро подобрать, поскольку чисел, на которые можно умножать, также будет слишком много.

Вот код на языке компьютерной системы Mathematica, реализующий Ваш алгоритм:

Fhi[n_Integer] := Module[{a, b, c}, 
  a = n; b = Floor[n/2]; c = 0; Label[One]; c++; If[
    Mod[a, 2] == 0, a = Floor[a/2] + b, a = Floor[a/2]]; If[a > 0, Goto[One]]; c]

Проверьте соответствие своему коду.

Вот код, использующий определённую выше функцию:

For[j=61,j≤70,j++,P1=Prime[j];For[k=2,k<j,k++,P2=Prime[k];n=
  P1 P2;F1=Fhi[n];F2=EulerPhi[n];m=F2/F1;If[2^Floor[Log[2,
    m]]≠m,Print["P1 = ",P1,", P2 = ",P2,
    ", n = ",n,", Fhi = ",F1,", EulerPhi = ",F2,",
     EulerPhi/Fhi = ",FactorInteger[F2/F1]];Print[
      "Fhi = ",FactorInteger[F1]]]]]

Вот пара строк, напечатанных этим кодом:

P1 = 349, P2 = 331, n = 115519, Fhi = 1740, EulerPhi = 114840, EulerPhi/Fhi = {{2, 1}, {3, 1}, {11, 1}}
Fhi = {{2, 2}, {3, 1}, {5, 1}, {29, 1}}

Это означает, что для числа $n=349\cdot 331=115519$ Ваш алгоритм даёт $c=1740=2^2\cdot 3\cdot 5\cdot 29$, в то время как $\phi(n)=114840=c\cdot 2\cdot 3\cdot 11$.

Так что интересного предмета для обсуждения пока не видно.

[нг]

Тема перенесена в Карантин до исправления сообщения LazyCat. Повторяю, любые комментарии действий модератора следуют направлять исключительно через ЛС (личные сообщения, ).

[нг]

Тема закрыта за исчерпанием интереса автора (к соблюдению правил). Возвращена из карантина.