Разложить на любые множители

[arseniiv]

(Оффтоп)

Признайтесь — использование тега [code] было ошибкой.

[SerjeyMinsk]

arseniiv в сообщении #483867 писал(а):

(Оффтоп)

Признайтесь — использование тега было ошибкой.

Если Вам так удобней.... Какой есть.

Метод квадратичных вычетов "ACCA". Авторы: Табалевич С., Александров С., Васин А.,


Program abube;
uses crt;
var
flag:array[1..1000] of integer;
a,b,c,n,y,i,j,k,d,p:integer;
begin
clrscr;
writeln('Vvedite ne4etnoe 4islo');
readln(n);
if ((n mod 2) = 0) then
begin
writeln('Prosil zhe ne4etnoe!');
writeln('Budet ',n+1);
n:=n+1;
end;
writeln;

a:=n*n-3*n;
b:=2*n;
c:=n*n-(n-2)*(n-2);
d:=c-2;
for i:=1 to (c div 2)+1 do
flag[i]:=2;

k:=6;
j:=3;
p:=0;
Flag[1]:=1;
while (k<>b) do
begin
y:=(a-p*b) mod k;
y:=y div 2;

i:=1;
for y:=y+1 to (d div 2)+1 do
begin
if (i=1) then
flag[y]:=1;
i:=i+1;
if (i>j) then
i:=1;
end;
k:=k+4;
j:=j+2;
p:=p+1;
end;

for i:=1 to (d div 2)+1 do
if (flag[i]=2) then
write(n*n-(i-1)*2,'; ');

readkey;
end.

[arseniiv]

(Оффтоп)

Я имел в виду, что тот текст было незачем оформлять, так только уменьшалась его читаемость. Кода я не просил.

[SerjeyMinsk]

arseniiv в сообщении #483870 писал(а):

(Оффтоп)

Я имел в виду, что тот текст было незачем оформлять, так только уменьшалась его читаемость. Кода я не просил.

Я так и не могу осилить оформление формул. Постоянные ошибки. Только поэтому.

[arseniiv]

(Оффтоп)

При оформлении текста с ними в [code] они, скорее всего, не начнут смотреться лучше.

[Sonic86]

SerjeyMinsk в сообщении #483808 писал(а):

x=b (mod e), (e = 6(mod 4)).

Вот здесь как-то плохо написано. $e$ чему равно (я не думаю, что $e$ - это класс вычетов).
Если я правильно понял эта фраза даже излишняя.

SerjeyMinsk в сообщении #483808 писал(а):

a= n² – 3n, b= 2n, c= 4n - 4.
A = (0,2,4,6, ..., d) (d < с).

Видимо, имеется ввиду $A= \{ 0;2;4;6;...;4n-6\}$

SerjeyMinsk в сообщении #483808 писал(а):

Доказательство:
Каждый шаг алгоритма представляется в виде:
n²-(2k+1)n = R (mod(4k+2)) → n²-R = 0 (mod(2k+1)) → n²-(R+(2k+1)m) = 0 (mod(2k+1))
n, m, k – натуральные числа.
Справедливость данных выводов доказывает, что на выходе нет составных чисел.

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

А вообще ничего так выглядит. Я проверил для $n^2=81$ - алгоритм действительно выдает простые числа.
Кроме того, Вы забыли написать - это метод генерации последовательностей простых чисел. Т.е. факторизации чисел здесь нет (может у Вас там где-то есть более кошерный вариант, но в написанном здесь ничего подобного нету). А раз ее нет, то имеет смысл сравнить скорость работы своего алгоритма с существующими методами проверки на простоту. Что-то мне подсказывает, что они могут быстрее работать (у Вас метод строится, скорее всего, на решете).

В любом случае: если будете это куда-то сдавать - нужно найти асимптотику числа шагов алгоритма и сравнить ее с асимптотикой существующих алгоритмов.
Например, уже сразу видно, что если это будет быстрее решета Эратосфена (а это самое медленное решето, см в Вики ссылки), то лишь в константу раз и памяти может будет есть лишь в константу раз меньше. У Вас в цикле происходит $O(n)$ сравнений. В то же время, можно решетом Эратосфена за $O(\sqrt{n})$ вычислить все простые числа до $n$ и просто за $O(\frac{n}{\ln n})$ операций просеять участок из $[(n-2)^2,n^2]$ (ха! так решето Эратосфена даже быстрее будет в $O(\ln n)$ раз! Тогда вообще смысла нет.). Памяти кушаем $O(n)$. Ну код простой, да.
И еще забыл сказать: за поиск в массиве $A$ сложность еще увеличивается в $O(\ln n)$ раз.

Ссылка на Вики:
http://ru.wikipedia.org/wiki/%D0%A0%D0% ... 0%BD%D0%B0
посмотрите там еще и решето Аткина - вот Вам с ним надо будет сравнивать тогда.

-- Вс сен 18, 2011 03:51:53 --

SerjeyMinsk в сообщении #483871 писал(а):

Я так и не могу осилить оформление формул. Постоянные ошибки. Только поэтому.

Странно. Там же автопроверка стоит - там же все ошибки пишутся.

[SerjeyMinsk]

Sonic86 его можно оптимизировать и без использования массива и решета, но сложность все равно будет только лишь немного лучше Аткина, то есть для практического применения в криптографии или при поиске самых больших чисел он не пригоден и представляет только лишь теоретический интерес.
Разложение на множители я не публиковал еще здесь. Изучаю пока сам каковы возможности нового метода факторизации, но главное, что в нем нет вычислений в виде деления или извлечения корня. Вот, никак калькулятор найти не могу в который бы 500-значные числа влазили.

[Sonic86]

SerjeyMinsk в сообщении #483900 писал(а):

Sonic86 его можно оптимизировать и без использования массива и решета, но сложность все равно будет только лишь немного лучше Аткина

Я что-то даже не уверен, что он будет лучше решета Эратосфена, о чем писал.
Я могу точно вычислить асимптотику с коэффициентом, но мне немного в лом - все-таки понадобится около получаса.

SerjeyMinsk в сообщении #483900 писал(а):

Разложение на множители я не публиковал еще здесь.

А, ну тогда понятно.

SerjeyMinsk в сообщении #483900 писал(а):

Изучаю пока сам каковы возможности нового метода факторизации, но главное, что в нем нет вычислений в виде деления или извлечения корня.

Ну корень-то не особо страшен - он вообще один раз обычно используется. И его можно неявно переписать. Я вот, когда решето пишу, пишу так:

if(d*d<n){
... // основной код
}

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

SerjeyMinsk в сообщении #483900 писал(а):

Вот, никак калькулятор найти не могу в который бы 500-значные числа влазили.

А Maple Вам не нравится? Я там как-то числа длиной во весь экран писал. И команда ifactor разложения на множители там есть.
Есть также PARI/GP, о нем здесь: topic14229.html - он реально работает быстрее Maple (я на нем раскладывал на множители числа $C_{2n-1}^{n-1}-1$ - после $n=160$ Maple начинает почти полностью зависать вместе с системой, а PARI/GP не вешает систему и через некоторое время выдавал результат (количественно не скажу, но минимум в 2 раза быстрее)).

[Someone]

SerjeyMinsk в сообщении #483900 писал(а):

Вот, никак калькулятор найти не могу в который бы 500-значные числа влазили.

Вы же программируете на C++, если не ошибаюсь. Возьмите библиотеку WinNTL или GMP, они с числами любого размера работают.

SerjeyMinsk в сообщении #483900 писал(а):

Разложение на множители я не публиковал еще здесь.

Про методы GNFS, SIQS и им подобные знаете? http://gilchrist.ca/jeff/factoring/index.html Там в документации к программам есть описания методов.

[SerjeyMinsk]

Sonic86, Maple и PARI/GP сейчас качаю. Команда ifactor там выполняется либо методом решета числового поля либо методом эллиптических кривых. На сегодняшний день это самые быстрые методы разложения на множители в виде различных модификаций, но даже они не могут факторизировать большие числа за полиномиальное время, а наш метод легко справляется. Мне нужен в этих программах только калькулятор с существующим методом быстрого возведения в степень (его достаточно). Я делаю лишь несколько операций возведения в степень, умножения и вычитания для того чтобы разложить число на два сомножителя.

Someone
К сожалению, я абсолютно не знаю языков программирования.
Спасибо, там прямо в названии и написаны методы которые они используют.
Метод решета числового поля
Метод квадратичного решета
Метод эллиптических кривых
Поэтому не пришлось читать документацию.

P\S Эх, нам бы толковых программистов в команду....

-- Вс сен 18, 2011 11:39:28 --

Да, совершенно все отлично считает в PARI/GP. Спасибо,Sonic86. Единственное, не могу понять как записывать результаты.
Например число $2^5^0^0^0^0$ разлаживает на два сомножителя моментально. Ну всмысле времени занимает столько-же сколько возвести в степень.

[Sonic86]

SerjeyMinsk в сообщении #483931 писал(а):

Да, совершенно все отлично считает в PARI/GP. Спасибо,Sonic86. Единственное, не могу понять как записывать результаты.

Я с ним знаком не глубже, чем написано по приведенной ссылке. Дальше Вам придется самому. Или же задайте вопрос в той теме.

[SerjeyMinsk]

Sonic86 в сообщении #483938 писал(а):

SerjeyMinsk в сообщении #483931 писал(а):

Да, совершенно все отлично считает в PARI/GP. Спасибо,Sonic86. Единственное, не могу понять как записывать результаты.

..... Или же задайте вопрос в той теме.

Как в PARI/GP calcularor 2.3.4 cкопировать результат операции в отдельный файл?

[Sonic86]

SerjeyMinsk в сообщении #483943 писал(а):

Как в PARI/GP calcularor 2.3.4 cкопировать результат операции в отдельный файл?

Да не в этой теме, а в той, которая по ссылке, где про PARI написано
Я не знаю.
А кстати! В той теме есть! Я же как-то в файл выводил!
Вот оно: post255964.html#p255964

[Someone]

SerjeyMinsk в сообщении #483931 писал(а):

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

Да??? Не продемонстрируете на примере? Не $2^{50000}$, а, например,

$62228434012141194686457165582049291407015047117621576082062061979834546972543$.

Насколько я знаю, это в пределах возможностей GNFS. Но для Вас и

\begin{multline*}918043961292405380474313317942681851757795965146243315005316581958964279714434\\ 5473117821653771454735241831830504632208791702287600455730577640999025181429\end{multline*}

не должно быть проблемой.

[SerjeyMinsk]

Someone
Да!
Когда разберусь как записывать в файл результаты и копировать ваше число в программу, и если данное число можно привести к специальному виду, пожалуйста. Не вижу проблем.
Пока просто лень и времени нет заниматься бессмысленными действиями.