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

[iJoy]

вот оптимизировал с использованием замечательного битового массива
(миллиард просеял за 195 секунд):

Dim dt As DateTime = Now
Dim max As ULong = 1000000000UL '1 млрд.
Dim s As ULong = Int(Math.Sqrt(ULong.MaxValue))
Dim b As New BitArray(max + 1)
For f As ULong = 0 To b.Length - 1
    b(f) = True
Next
b(0) = False : b(1) = False
Dim n As New List(Of ULong)
Dim i, ix As ULong
Do
    ix = 0
    For f As ULong = i + 1 To max
        If b(f) Then
            ix = f
            Exit For
        End If
    Next
    If ix = 0 Then Exit Do
    i = ix
    n.Add(i)
    If i <= s Then
        For f As ULong = i ^ 2 To max Step i
            b(f) = False
        Next
    End If
Loop
MsgBox("Найдено простых чисел: " & n.Count & " из " & max & vbCrLf & _
       "Наибольшее простое число: " & n(n.Count - 1) & vbCrLf & _
       "Затраченное время, сек.: " & DateDiff(DateInterval.Second, dt, Now))

кажется тут оптимизировать уже нечего?

-- 21.07.2011, 23:11 --

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

Можно намного быстрее:

http://www.primefan.ru/stuff/pict/benchmark.gif

Замечательные результаты. Даже многопоточность используется. А можно на исходники взглянуть?

[venco]

iJoy в сообщении #470359 писал(а):

сдвиги есть типа i = i << 4 (сдвиг на 4 бита влево), но как они тут помогут, если нужно бит n установить в 0?

Вместо Math.Floor(i/8) использовать (i >> 3).
Вместо 2 ^ (f Mod 8) использовать 1<<(f and 7).
Вместо ULong использовать UInteger.
Вместо Math.Sqrt(ULong.MaxValue) >= i использовать max_i >= i, а max_i посчитать один раз (снаружи цикла) как Math.Sqrt(max).

[iJoy]

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

Вместо Math.Floor(i/8) использовать (i >> 3).
Вместо 2 ^ (f Mod 8) использовать 1<<(f and 7).
Вместо ULong использовать UInteger.
Вместо Math.Sqrt(ULong.MaxValue) >= i использовать max_i >= i, а max_i посчитать один раз (снаружи цикла) как Math.Sqrt(max).

Спасибо огромное. Такая оптимизация ускоряет алгоритм примерно в 100 раз!

[Droog_Andrey]

iJoy в сообщении #470369 писал(а):

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

Можно намного быстрее:

http://www.primefan.ru/stuff/pict/benchmark.gif

Замечательные результаты. Даже многопоточность используется. А можно на исходники взглянуть?

Версия 3.0 ещё быстрее: http://www.primefan.ru/stuff/pict/benchmark30.gif

А исходники вот тут: http://code.google.com/p/primesieve/

[SerjeyMinsk]

Возвращаясь к первому посту темы и сути обсуждения (кто помнит), то хотелось бы продолжить о сути и поговорить (кто еще есть на форуме).
Разобрался я со сложностями алгоритмов и как они образуются. (Как уже и писал, прошу прощения из-за своего неведения вопроса, ASSA действительно оказалась непригодной не только для больших чисел, но и для нужд криптографии, хотя в виду детерминированности алгоритма, то в теории чисел, я продолжаю считать, что место этому алгоритму есть) Но сейчас о другом.
За этот год, ASSA меня привела к совершенно другому алгоритму генерации простых чисел и одновременно детерминированному тесту простоты (так как есть и доказательство) c полиномиальной сложностью, который превосходит всем известный детерминированный тест AKS.
Требуется рецензия на эту работу, и прошу помощи форумчан, кто является экспертом в этом вопросе и знает суть темы, подсказать к кому конкретно можно обратиться. Рецензия требуется для дальнейшей коммерциализации и практического применения этого алгоритма в криптографии (системы с открытым ключом).

[aleksm2]

Добрый день, SerjeyMinsk !

я к.ф.-м.н. , специализируюсь по теории чисел.

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

пишите мне в Skype (www.skype.com) aleksm2

Всего доброго!
до встречи

[dmd]

dmd в сообщении #453635 писал(а):

Сумма кубов $a^3+b^3=(a+b)(a^2-ab+b^2)$

Пусть $3|(M-1)$, тогда либо $(a+b):M$, либо $(a^2-ab+b^2):M$,
где $a=3^s$, $s=\frac{M-1}{6p}$ и $b$ - степень двойки.

...

Если допустим $5|(M-1)$, $a^5+b^5=(a + b) (a^4 - a^3 b + a^2 b^2 - a b^3 + b^4)$, то снова два варианта: либо $(a+b):M$, либо $(a^4 - a^3 b + a^2 b^2 - a b^3 + b^4):M$,
где $a=3^s$, $s=\frac{M-1}{10p}$ и $b$ - степень двойки.

Если простое $q|(M-1)$, $a^q+b^q=(a + b) (a^{q-1} - ... + b^{q-1})$, то та же вилка: либо $(a+b):M$, либо $(a^{q-1} - ... + b^{q-1}):M$,
где $a=3^s$, $s=\frac{M-1}{2qp}$ и $b$ - степень двойки.

Кстати, решение квадратного уравнения $a^2-ab+b^2$ по модулю $M$, где $a=3\pmod M$ и $b$ - неизвестное, обязано существовать и без возведения в крутую степень по модулю. Поэтому следующий код тоже работает:

mtf()=
{
local(M:int);
local(a,t);
forprime(p=2, 5000,
 M= (2^p-1):int;
 a= Mod(3,M);
 t= polrootsmod(a^2 - a*X + X^2, M);
 if(#t==2, print(p))
)
};

Тогда, если для большого $p$ получена частичная факторизация $M-1$, то имеет смысл сначала проверить, существует ли решение соответствующего полинома по модулю $M$

polrootsmod(a^{q-1} - ... + X^{q-1}, M)

где $a=3\pmod M$ и простое $q|(M-1)$

Если не существует, то сразу можно отбраковывать данное $p$.
Правильно ли это?

[dmd]

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

[ananova]

aleksm2
А можно без скайпа сообщить?

(Оффтоп)

не люблю общаться по скайпу

[dmd]

(Оффтоп)

Прошу помощи.
Хотел рассмотреть соответствующие квадратичные вычеты-невычеты по модулю $M$ и запутался. По идее функция символа Кронекера для невычетов должна возвращать $-1$

mkr()=
{
local(h,M:int);
forprime(p=3, 108,
  M= 2^p-1;
  h= lift(-Mod((M^2+27)/4,M));
  print(p,"    ",kronecker(h,M),"    ",#polrootsmod(x^2 - h,M))
 )
};

но она во всех случаях возвращает $1$

? mkr()
3    1    2
5    1    2
7    1    2
11    1    0
13    1    2
17    1    2
19    1    2
23    1    0
29    1    0
31    1    2
37    1    0
41    1    0
43    1    0
47    1    0
53    1    0
59    1    0
61    1    2
67    1    0
71    1    0
73    1    0
79    1    0
83    1    0
89    1    2
97    1    0
101    1    0
103    1    0
107    1    2

Почему так?

[maxal]

dmd в сообщении #517211 писал(а):

Хотел рассмотреть соответствующие квадратичные вычеты-невычеты по модулю $M$ и запутался. По идее функция символа Кронекера для невычетов должна возвращать $-1$

Только по простым модулям. Для составных модулей она для некоторых невычетов может возвращать 1. Подробности - см. в Википедии.
Если хочется знать наверняка, то используйте функцию issquare(), только учтите, что она будет факторизовать модуль.

Кроме того, в "h= lift(-Mod((M^2+27)/4,M));" можно смело выкинуть "M^2" так как это ноль по модулю вашего нечетного M.

[magistr07]

По теме. Свежая новость. В Израиле, г.Реховот, определён алгоритм построения ряда простых чисел. Проверка алгоритма на построение рядов из 100000 и 1000000 чисел прошла успешно. Ошибок не было. Ряды строились от произвольно заданных простых чисел. Например 79 и следующие за ним 100000 чисел, 193 и следующие за ним 1000000 чисел. Кроме этого, насколько известно, алгоритм так прост, что прописывается в течение 2-х минут в Microsoft XL и мгновенно выдаёт ряд чисел в пределах разрешающей способности программы. Автор из бывшего союза. Имеет он отношение или нет к известному институту Вайцмана, что в г.Реховот, - инфы нет.
Будут ещё новости, - отпишусь.

[Sonic86]

Дайте ссылку лучше. Нагуглить новость не могу

[Someone]

magistr07 в сообщении #518332 писал(а):

определён алгоритм построения ряда простых чисел

Ничего не понял. Какого ряда?

[bot]

И в самом деле, кому нужен алгоритм построения 100000 простых чисел вслед за любым простым, если достаточно указать одно простое вслед за любым?