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

[LazyCat]

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

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

А далее все как в школе учили:
a = p + q = n + 1 - \phi(n)
b = p - q = \sqrt{a^2 - 4n}
p = (a + b)/2
q = (a - b)/2

Этот метод идеален и для проверки простоты чисел: \phi(n) = n - 1
Если под него подвести хорошую математическую базу, то рухнет ПОЧТИ вся криптография с открытыми ключами

[PAV]

Заголовок исправлен

[Someone]

Ну чего тут обсуждать. Вот ссылка: http://www.rsa.com/rsalabs/node.asp?id=2093.
Берите там числа, факторизуйте и получайте премии. От $30000.

[Macavity]

LazyCat писал(а):

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

a = n;
b = sr(n);
c = 0;
do {
  c++;
  if(!sr(a)) a += b;  //sr(a) -- a /= 2, shift right (return low bit) -- very effective hardware realization
} while(!a);

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

А далее все как в школе учили:
a = p + q = n + 1 - \phi(n)
b = p - q = \sqrt{a^2 - 4n}
p = (a + b)/2
q = (a - b)/2

Этот метод идеален и для проверки простоты чисел: \phi(n) = n - 1
Если под него подвести хорошую математическую базу, то рухнет ПОЧТИ вся криптография с открытыми ключами

А что такое sr()? Вообще не мешало бы побольше комментариев...

Но если Вы считаете, что решили проблему факторизации, то зайдите вначале на сайт RSA и срубите немного деньжат(тысяч 10 или 20 доларов), заодно проверите эффективность алгоритма.


update
О! Someone меня опередил...

[Руст]

LazyCat писал(а):

a = n;
b = sr(n);
c = 0;
do {
  c++;
  if(!sr(a)) a += b;  //sr(a) -- a /= 2, shift right (return low bit) -- very effective hardware realization
} while(!a);

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

Ничего не понял в вашем алгоритме (не понятно, что за функция sr(n)).
Но судя по тому, что ответ равен 2c или 4c, а число c вычисляется добавлением по 1, количество операций пропорционально n. А это очень много. Уже школьный алгоритм факторизации требует корень из n опеаций. Для тестирования на простоту уже имеется полиномиальный (относительно количества цифр, т.е ln(n) ) алгоритм. А современные алгоритмы факторизаций требует порядка $exp(\sqrt[3]{ln(n)})$ операций.

[worm2]

LazyCat писал(а):

a = n;
b = sr(n);
c = 0;
do {
  c++;
  if(!sr(a)) a += b;  //sr(a) -- a /= 2, shift right (return low bit) -- very effective hardware realization 
} while(!a);

Я так понял, sr(n) примерно такая:

int sr(int &n)
{
  int res = (n & 1) ? 1 : 0;
  n>>=1;
  return res;
}

или всё-таки такая:

int sr(int &n)
{
  n>>=1;
  return (n & 1) ? 1 : 0;
}

Потом у меня сомнения насчёт строчки:

while(!a);

Может быть, надо так:

while(a);

В любой из комбинаций этих вариантов у меня получается либо зависание при n = 11, либо после цикла c = 1 при любом n > 1.

[LazyCat]

Спасибо за активность ! Ответы по-порядку.
1. Ехидные посылания на rsalabs я в расчет не принимаю (мне их деньги не нужны - все равно не заплатят)
2. Функция sr(a) - это сдвиг вправо на один бит с возвратом вышедшего бита в качестве результата функции, можно считать это делением на 2 (смотреть основы программирования на каком-нибудь языке)
3. То что алгоритм медленный и так понятно, потому и обратился к математикам с просьбой развить идею и вывести, например, формулу расчета i-го члена получающейся прогрессии(кстати, последние члены очень интересны) или нечто подобное.

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

[Someone]

LazyCat писал(а):

1. Ехидные посылания на rsalabs я в расчет не принимаю (мне их деньги не нужны - все равно не заплатят)

Откуда Вы знаете, что не заплатят? Кому-то ведь заплатили. И, в любом случае, Вы могли бы продемонстрировать результат разложения здесь. Это было бы очень эффектно, и Вы сразу приобрели бы кучу сторонников. Вы не первый претендент на изобретение сверхэффективного алгоритма разложения на множители, с которым я сталкиваюсь. У Ваших предшественников ничего действительно эффективного не оказалось.

[Руст]

Я так и не понял из ваших объяснений sr(n)=n>>1 (деление на два на цело) или sr(n)=n&1 (т.е. последний бит - остаток при делении на 2). При пояснении могли бы проверить работает ли ваш алгоритм в принципе. Хотя, с точки зрения быстродействия как уже было отмечено абсолютно не пригодный алгоритм.

[LazyCat]

sr(n) такая (проверка на четность и деление на 2):

int sr(int &n) 
{ 
  int res = (n & 1) ? 1 : 0; 
  n>>=1;   // or n/=2; 
  return res; 
}

и, конечно же,

while(a);

Прошу извинения за опечатку [/code]

[tolstopuz]

LazyCat писал(а):

1. Ехидные посылания на rsalabs я в расчет не принимаю (мне их деньги не нужны - все равно не заплатят)

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

[LazyCat]

Вообще-то, я обратился к профессионалам за помощью и советом(см. первый пост), но, как оказалось, профессионалы-то по болтовне(без обид, это я к слову). Алгоритм действительно очень сырой(потому-что новый) и требуется его математическая интерпритация.
А по поводу быстродействия я рекомендую математикам брать пример с физиков, оперирующих весьма конкретными килограммами, метрами, вольтами и т.д., а не абстрактными величинами "$exp(\sqrt[3]{ln(n)})$ операций ". Вы знаете как эти операции реализованы в конкретной программе, сколько мусора насыпал компилятор при создании исполнимого машинного кода, сколько тактов тратит просессор на исполнение одной такой комманды, есть ли конвейер команд, есть ли распараллеливание выполнения команд (не путать с распараллеливанием вычислений), какова тактовая частота процессора ???
Без знания этого вообще не правомерно сравнивать эфективность программных и аппаратных способов (опять см. первый пост), т.е., например, некая операция очень эфективным програмным алгоритмом может быть выполнена за 1сек, то аппаратно она же может быть выполнена за 1 микросек.
Но похоже я ошибся форумом

[Руст]

У вас b не меняется. Например если n чётное, то b=0. Поэтому ваша программа вычислит в качестве c - число двоичных знаков числа n, т.е. $c=1+[log_2(n)].$
Для нечётных n результат для с будет максимум на 1 больше числа цифр. Программа ваша считает совсем другое.

[tolstopuz]

LazyCat писал(а):

абстрактными величинами "$exp(\sqrt[3]{ln(n)})$ операций ". Вы знаете как эти операции реализованы в конкретной программе, сколько мусора насыпал компилятор при создании исполнимого машинного кода, сколько тактов тратит просессор на исполнение одной такой комманды, есть ли конвейер команд, есть ли распараллеливание выполнения команд (не путать с распараллеливанием вычислений), какова тактовая частота процессора ???

Извините, знакомо ли вам обозначение и смысл нотации "О большое"? Насколько я понимаю по вашему $exp$, незнакомо. Давайте вы сначала ознакомитесь с этой нотацией, а потом уже будете излагать свое квалифицированное мнение по этому поводу.

LazyCat писал(а):

Но похоже я ошибся форумом

Фантастика на втором этаже.

[нг]

LazyCat:

LazyCat писал(а):

Вообще-то, я обратился к профессионалам за помощью и советом(см. первый пост), но, как оказалось, профессионалы-то по болтовне(без обид, это я к слову).
…
А по поводу быстродействия я рекомендую математикам брать пример с физиков,
…
Но похоже я ошибся форумом

Замечание за неуважение к участникам форума (Вы также балансируете на грани перехода на личности).

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

Если Вы, после того, как разберетесь, останетесь при своем мнении, следует доказывать, почему они не правы. Поверьте, к доказательствам математики относятся всерьез.