Поиск простых чисел

[ananova]

Алгоритм может работать при малых числах (например, до наименьшего числа Кармайкла), а при больших числах - может и сбой дать... Необходимо убедиться, что Ваш алгоритм не "спотыкается" о числа Кармайкла. (Я бы с этого начал проверку его возможностей).

[SerjeyMinsk]

Бодигрим в сообщении #325621 писал(а):

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

Где публиковаться, к кому обратиться, что предпринимать?

В рецензируемом математическом журнале, желательно посвященном проблемам теории чисел. Обратиться - с макетом статьи в редакцию. Что предпринимать - выбрать язык, составить статью. Я бы вначале описал метод порождения простого числа, доказал бы строго, что он порождает только простые числа, привел бы примеры простых чисел, полученных с его помощью, которые можно проверить и получить другими известными методами, а затем уже числа, которые недосягаемы для других методов.

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

О числе какого порядка вообще идет речь?

(Оффтоп)

Ну вот вижу совет. Спасибо, Бодигрим!

А какие журналы существуют в Беларуси имеющие авторитетное мнение, не подскажете? Или все авторитетные "буржуйские"? Или в России. В России должны ведь быть однозначно. Я говорил, что не математик и "этого мира" вообще не знаю.
Мы можем доказать в ASSA, что выдаваемые им числа будут простыми и только простыми вне зависимости от величины $N^2$
Можем, как на основе ASSA так и на основе другого алгоритма доказать простоту любого числа не используя технические вычислительные средства. Пока работа с большими числами ( порядка$N^{43112609}$ ) требует недельных расчетов. На машине можно быстрее конечно, но нет программистов пока.
В тысячу знаков - можно попробовать выложить. Если принципиально. Однако-ж зачем? пока не понимаем. Времени занимает не намного меньше. Ничего-ж не поменяет это на форуме, а мы только время потратим.
У нас есть в сто крат интересней ASSA мысли, но тут до сих пор этот алгоритм не могут признать и включится в интереснейшую работу, а с кем дальше его идти в форуме?
Вот и прошу уже хоть практических советов каких (и весьма благодарен, что откликнулись)

[serval]

Никакие практические проверки не отменят проверки теории положенной в основу алгоритма.

[SerjeyMinsk]

ananova в сообщении #325754 писал(а):

Алгоритм может работать при малых числах (например, до наименьшего числа Кармайкла), а при больших числах - может и сбой дать... Необходимо убедиться, что Ваш алгоритм не "спотыкается" о числа Кармайкла. (Я бы с этого начал проверку его возможностей).

Первые 10 чисел Кармайкла можно легко посмотреть в действии алгоритма (где-то здесь выложен программный код реализованный до 12-значных (там потом надо просто знания программистов чтобы увеличить "дальность" расчетов). Справляется без проблем.(и более того даже внимание на них не обращает ( не в обиду Кармайклу))

-- Вс май 30, 2010 22:10:16 --

serval в сообщении #325763 писал(а):

Никакие практические проверки не отменят проверки теории положенной в основу алгоритма.

Ну так тут и предлагал участникам дискуссии её и создать совместно либо описать существующими. Мы ведь от дискуссии не отказываемся. Свою-то работу я уже сделал. Нужны специалисты для дальнейшего развития причем хорошие, опытные специалисты в математике и просто умные люди. Тут надо сторонники алгоритма, а не противники. Неприятелей итак хватает. Я уверен, что немногие здесь понимают какую практическую значимость он несет для криптографии. (не буду о математике пока).

[SerjeyMinsk]

(Оффтоп)

Да, если вдруг кто-либо проявит интерес к алгоритму ASSA и внесет в него упрощение, существенную модернизацию и вообще - смело прибавляйте свою букву в название алгоритма.

Подскажите, сколько существует способов для поиска чисел Мерсенна? Не простых, а вообще всех. Я пока вижу два разных подхода к их получению. Один в википедии есть, второй могу выложить только там формулу надо подправить правильно. Поможет кто-нибудь?

[serval]

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

предлагал участникам дискуссии её и создать совместно либо описать существующими

Видимо, я пропустил описание алгоритма. Или вы приводили формулу? Как же это я. Оно (она) еще здесь? Стоит искать?

[SerjeyMinsk]

serval в сообщении #325881 писал(а):

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

предлагал участникам дискуссии её и создать совместно либо описать существующими

Видимо, я пропустил описание алгоритма. Или вы приводили формулу? Как же это я. Оно (она) еще здесь? Стоит искать?

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.

Вот этот алгоритм реализованный программно. В этом виде вроде только для малых чисел (там что-то с массивом надо делать чтобы увеличивать "дальность")

[serval]

А формула? В самом первом посте вы говорили про формулу которая по заданному числу выдает все простые меньше него. Есть такая?

[SerjeyMinsk]

serval в сообщении #325889 писал(а):

А формула? В самом первом посте вы говорили про формулу которая по заданному числу выдает все простые меньше него. Есть такая?

[quote="SerjeyMinsk в сообщении #283023"]

[serval]

Выбрать нечетное $n$
Вычислить:
$n^2$
$a=n^2-3n$ # Иначе говоря $a=n(n-3)$ ?
$b=2n$
$c=n^2-(n-2)^2$ # Иначе говоря $c=4(n-1)$ ?
Выбрать $d<c$. Из четных $A\leqslant d$ исключить
$A\equiv a\ (mod\ 10)$
$A\equiv (a-b-b)\ (mod\ 14)$
и так далее. # Как выглядят общие члены последовательностей из которых выбираются числа в правой части сравнения?
Исключить $A\equiv b\ (mod\ e)$ где $e\equiv 6\ (mod\ 4)$
Из оставшихся $A$ получить
$p=n^2-A$
Все они будут простыми.

Или

Выбрать нечетное $n$
Вычислить:
$c=4n-4$ # Иначе говоря $c=4(n-1)$ ?
Из последовательности $A=c-2i$ где $i$ пробегает значения $i=1 \ldots \dfrac{a-2}{2}$ исключить
$A\equiv 2n\ (mod\ 2n-4)$
$A\equiv 6n\ (mod\ 2n-12)$
и так далее. # И снова - как выглядят общие члены последовательностей из которых выбираются числа в правой части сравнения?
Исключить $A\equiv RN\ (mod\ 6)$ # Что такое $RN$ ?
Из оставшихся $A$ получить
$p=n^2-A$
Все они будут простыми.

Я ничего не напутал?

[SerjeyMinsk]

serval в сообщении #325910 писал(а):

Выбрать нечетное $n$
Вычислить:
$n^2$
$a=n^2-3n$ # Иначе говоря $a=n(n-3)$ ?
$b=2n$
$c=n^2-(n-2)^2$ # Иначе говоря $c=4(n-1)$ ?
Выбрать $d<c$. Из четных $A\leqslant d$ исключить
$A\equiv a\ (mod\ 10)$
$A\equiv (a-b-b)\ (mod\ 14)$
и так далее. # Как выглядят общие члены последовательностей из которых выбираются числа в правой части сравнения?
Исключить $A\equiv b\ (mod\ e)$ где $e\equiv 6\ (mod\ 4)$
Из оставшихся $A$ получить
$p=n^2-A$
Все они будут простыми.

Или

Выбрать нечетное $n$
Вычислить:
$c=4n-4$ # Иначе говоря $c=4(n-1)$ ?
Из последовательности $A=c-2i$ где $i$ пробегает значения $i=1 \ldots \dfrac{a-2}{2}$ исключить
$A\equiv 2n\ (mod\ 2n-4)$
$A\equiv 6n\ (mod\ 2n-12)$
и так далее. # И снова - как выглядят общие члены последовательностей из которых выбираются числа в правой части сравнения?
Исключить $A\equiv RN\ (mod\ 6)$ # Что такое $RN$ ?
Из оставшихся $A$ получить
$p=n^2-A$
Все они будут простыми.

Я ничего не напутал?

1."Иначе говоря"- сейчас проверяю.
2. Каждый член этой последовательности равен двум по модулю 4
3. R - это член последовательности равный двум по модулю 4.

[serval]

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

2. Каждый член этой последовательности равен двум по модулю 4
3. R - это член последовательности равный двум по модулю 4

О каких последовательностях идет речь? Распишите в явном виде. Хотя бы словами - я приведу в читаемый вид.
Вообще, давайте сосредоточимся на втором варианте (после "Или"), он более прозрачен.

[SerjeyMinsk]

serval
"Иначе говоря" - совершенно верно!
Это уже упростило алгоритм. Если есть желание - вписывайте свою букву в название.

О последовательностях чуть попозже распишу. К вечеру.

[SerjeyMinsk]

serval, начал думать тут о последовательностях и у Вас хочу спросить: "А вы о каких последовательностях спрашиваете?"
Вообще для больших чисел он неприменим.

[Droog_Andrey]

Ну вот вам три числа.

A=803837457453639491257079614341942108138837688287558145837488917522
29742737653336521865023361639600454579150420236032087665699667609872
84043965408232928738791850869166857328267761771029389697739470167082
30428687109997439976544144845341155872450633409279022275296229414984
2306881685404326457534018329786111298960644845216191652872597534901

B=803837457453639491257079614341942108138837688287558145837488917522
29742737653336521865023361639600454579150420236032087665699667609872
84043965408232928738791850869166857328267761771029389697739470167082
30428687109997439976544144845341155872450633409279022275296229414984
2306881685404326457534018329786111298960644845216191652872597536801

C=803837457453639491257079614341942108138837688287558145837488917522
29742737653336521865023361639600454579150420236032087665699667609872
84043965408232928738791850869166857328267761771029389697739470167082
30428687109997439976544144845341155872450633409279022275296229414984
2306881685404326457534018329786111298960644845216191652872597537421

Определите с помощью ASSA, какие из чисел простые, а какие - составные.