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

[Droog_Andrey]

Для криптографии 64-битные простые давно устарели. Вот килобит - это уже серьёзно. И проще найти кандидаты в простые такого размера с помощью, скажем, PFGW, а потом доказать простоту с помощью Primo.

[SerjeyMinsk]

Droog_Andrey в сообщении #241245 писал(а):

Для криптографии 64-битные простые давно устарели. Вот килобит - это уже серьёзно. И проще найти кандидаты в простые такого размера с помощью, скажем, PFGW, а потом доказать простоту с помощью Primo.

Количество арифметических операций в ASSA столько-же (уже не говорю, что меньше) притом, что алгоритм детерминированный, а не вероятностный.
Я говорю о генерации ключей.

[Droog_Andrey]

Попробуете на 337-значном примере и убедитесь сами.

[SerjeyMinsk]

Droog_Andrey в сообщении #241277 писал(а):

Попробуете на 337-значном примере и убедитесь сами.

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

-- Вт сен 08, 2009 00:23:50 --

Droog_Andrey в сообщении #241241 писал(а):

Посмотрел. 100-значные не потянет, и даже 30-значные. Предел - где-то 20 знаков.

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

-- Вт сен 08, 2009 00:25:11 --

[/quote]

[venco]

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

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

Либо вы публиковали здесь какой-то другой алгоритм, либо сильно заблуждаетесь.

[SerjeyMinsk]

venco в сообщении #241360 писал(а):

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

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

Либо вы публиковали здесь какой-то другой алгоритм, либо сильно заблуждаетесь.

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

[venco]

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

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

Ну так вы бы объяснили его своими словами, без необходимости знания языка Паскаль, и ограничений, вызванных его применением.
Тем более, что код вы из своего сообщения удалили.

И, кстати, я думаю несколько человек, кто успел посмотреть ваш код, поняли как он образовывается и почему на выходе получаются простые числа. По крайней мере, я понял.

[Droog_Andrey]

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

Скиньте программу и программный код в которой вы работаете

Для начала PFGW: http://www.mersenneforum.org/showthread.php?t=12281

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

Говорю-же. Есть рабочая программа, работающая с тысячными числами. Привезут -можете подьехать и посмотреть её работу. Там несущественные дополнения в алгоритме.

Очевидно, там существенно другой алгоритм. Могу и подъехать, но для начала удалённо потестим.

[SerjeyMinsk]

Droog_Andrey в сообщении #241385 писал(а):

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

Скиньте программу и программный код в которой вы работаете

Для начала PFGW: http://www.mersenneforum.org/showthread.php?t=12281

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

Говорю-же. Есть рабочая программа, работающая с тысячными числами. Привезут -можете подьехать и посмотреть её работу. Там несущественные дополнения в алгоритме.

Очевидно, там существенно другой алгоритм. Могу и подъехать, но для начала удалённо потестим.

Я говорю не о PFGW в которой вы работаете, а о той программе в которой вы тестировали алгоритм ASSA.

Удаленно тестить лично мне нужды нет. Кто проявляет научный интерес - интересна не программа, а уравнение. Развлекать здесь кого-то я не собираюсь.

-- Вт сен 08, 2009 14:45:50 --

venco в сообщении #241378 писал(а):

И, кстати, я думаю несколько человек, кто успел посмотреть ваш код, поняли как он образовывается и почему на выходе получаются простые числа. По крайней мере, я понял.

Помогите тогда перевести его на научный язык. В виде формулы записать его. Поможете? Буду искренне благодарен.

Вот сам алгоритм.

Выбрать нечётное n в квадрате
Вычислить
a=n в квадрате - 3 n,
b=2n,
c= n в квадрате - (n-2) в квадрате
A= (2,4,6,...,d) (d меньше с)
Пометить или удалить из А все элементы, сравнимые с (а) ( mod 10)
Все сравнимые с ( a-b-b) (mod 14)
И так далее.
Наконец, когда (a-b-b-...-b)=b,
пометить или удалить x=b (mod e), (e= (три черты, не знаю как пишется
в вебе)6(mod 4)).
Простые числа : n в квадрате - х (х- непомеченный элемент).


Этот-же вариант, только покрасивее что-ли:

Выбрать нечетное n.
4n-4=a

A= ( a-2, a-4, a-6,...,2)
Пометить или удалить из А число, равное (2n) (mod 2n-4).
Затем все, сравнимые с (6n) (mod 2n-12)
И так далее...
Наконец, сравнимые с (RN) (mod6)
Все непомеченные числа являются разностями между квадратом выбранного
числа и искомыми простыми числами.

-- Вт сен 08, 2009 15:01:07 --

( mod 10), (mod 14) ,(mod 18) Вообщем через 4 и так далее.

[Droog_Andrey]

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

И так далее.
Наконец, когда (a-b-b-...-b)=b,

Описанный здесь цикл повторяется порядка $n$ раз. Это около $10^{50}$ повторений для 100-значного числа.

[SerjeyMinsk]

Droog_Andrey в сообщении #241500 писал(а):

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

И так далее.
Наконец, когда (a-b-b-...-b)=b,

Описанный здесь цикл повторяется порядка $n$ раз. Это около $10^{50}$ повторений для 100-значного числа.

Вы знаете я в этом еще не очень разбираюсь. Я все на бумаге делаю и считаю вручную.
Я так понимаю именно это влияет на скорость?
А если количество операций а-b сократить? Подумаю.

Но как Вы посчитали, не могу понять?

-- Ср сен 09, 2009 00:19:42 --

Нет, сокращение количества операций повлияет на точность и метод превратится в вероятностный.
Во всяком случае я пока не вижу сокращения операций a-b в другом виде.

[SerjeyMinsk]

Так что кто-нибудь поможет? Или мне здесь уже не надеятся?

[venco]

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

Так что кто-нибудь поможет?

В чём?

[SerjeyMinsk]

venco в сообщении #241727 писал(а):

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

Так что кто-нибудь поможет?

В чём?

См. предыдущий пост обращенный к вам.

[venco]

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

venco в сообщении #241727 писал(а):

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

Так что кто-нибудь поможет?

В чём?

См. предыдущий пост обращенный к вам.

Ok.
1. Возьмём список нечётных чисел в диапазоне $\bigl((2k-1)^2, (2k+1)^2\bigr)$.
2.1. Вычеркнем из списка все числа, делящиеся на $2k-1$.
2.2. Вычеркнем из списка все числа, делящиеся на $2k-3$.
...
2.k-1. Вычеркнем из списка все числа, делящиеся на $3$.
3. Невычеркнутые числа - простые.