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

[dmd]

Интересно, как $x$ зависит от $p$ в сравнении $3^\frac{M-1}{2p}\equiv -2^x\pmod M$

Возможно ли ответить на этот вопрос?

[dmd]

В общем получается $M|3^{s+zi}+2^{x+pj}$

где $M=2^p-1$, $s=\frac{M-1}{2p}$,
$p$ - искомое простое и оно же мультипликативный период двойки по модулю $M$,
$z$ - мультипликативный период тройки по модулю $M$,
$s$ и $x$ - наименьшие дискретного логарифмирования соответственно по основанию $3$ и $2$ по модулю $M$,
$i$ и $j$ - произвольные целые $>0$.

Т.е. $x$ зависит от $p$ постольку, поскольку $p$ образует модуль $M$.

[dmd]

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

$i$ и $j$ - произвольные целые $>0$

т.е. $\geqslant 0$

[dmd]

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

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

$i$ и $j$ - произвольные целые $>0$

т.е. $\geqslant 0$

хотя нет, $i$ и $j$ - любые целые, включая отрицательные.



Для делимости $M|3^{s+zi}+2^{x+pj}$ значение $s=\frac{M-1}{2p}$ минимально. Чтоб ещё сильнее облегчить возведение в степень по модулю нужно что-то другое.
Допустим $M|3^{t}-k2^{y}$, где $k$ - нечетное натуральное $<p$, и $0<y<p$. Вроде как соответствующие $t<\frac{M-1}{2p}$ существуют.



Интересно, что код

znlog(2,Mod(3,M))

вычисляется только для подходящих $p$, для всех остальных выдаёт ошибку

znlog: gen_Shanks_log: supplied order (= p) is incorrect.

Что это означает?

[maxal]

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

Что это означает?

Использование двух аргументов в znlog подразумевает, что второй является примитивным корнем - и если это не так, то возникает ошибка.
Попробуйте znlog(2,Mod(3,M),znorder(Mod(3,M)))

[dmd]

С примитивным корнем то же самое: для подходящих $p$ вычисляется, для неподходящих - ошибка

? p=61;M=2^p-1;znlog(2,znprimroot(M))
%9 = 718213396312462050
? p=67;M=2^p-1;znlog(2,znprimroot(M))
  ***   at top-level: p=67;M=2^p-1;znlog(2,znprimroot(M
  ***                              ^--------------------
  *** znlog: gen_Shanks_log: supplied order (= 67) is incorrect.
  ***   Break loop: type 'break' to go back to GP
break>
? p=67;M=2^p-1;znlog(2,Mod(3,M),znorder(Mod(3,M)))
  ***   at top-level: p=67;M=2^p-1;znlog(2,Mod(3,M),zno
  ***                              ^--------------------
  *** znlog: gen_Shanks_log: supplied order (= 67) is incorrect.
  ***   Break loop: type 'break' to go back to GP
break>
? p=89;M=2^p-1;znlog(2,znprimroot(M))
%10 = 326871808125915016405948530
? p=97;M=2^p-1;znlog(2,znprimroot(M))
  ***   at top-level: p=97;M=2^p-1;znlog(2,znprimroot(M
  ***                              ^--------------------
  *** znlog: gen_Shanks_log: supplied order (= 97) is incorrect.
  ***   Break loop: type 'break' to go back to GP
break>
? p=97;M=2^p-1;znlog(2,Mod(3,M),znorder(Mod(3,M)))
  ***   at top-level: p=97;M=2^p-1;znlog(2,Mod(3,M),zno
  ***                              ^--------------------
  *** znlog: gen_Shanks_log: supplied order (= 97) is incorrect.
  ***   Break loop: type 'break' to go back to GP
break>

[maxal]

dmd
Проблема в том, что по модулю $2^{67}-1$ примитивного корня не существует. И результат вызова znprimroot(2^67-1) неопределен...

-- Sat Jul 16, 2011 04:57:21 --

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

? p=67;M=2^p-1;znlog(2,Mod(3,M),znorder(Mod(3,M)))
  ***   at top-level: p=67;M=2^p-1;znlog(2,Mod(3,M),zno
  ***                              ^--------------------
  *** znlog: gen_Shanks_log: supplied order (= 67) is incorrect.
  ***   Break loop: type 'break' to go back to GP

А эта ошибка означает всего лишь, что $3^x\equiv 2\pmod{2^{67}-1}$ не имеет решений.

[dmd]

maxal в сообщении #468915 писал(а):

Проблема в том, что по модулю $2^{67}-1$ примитивного корня не существует.

Сначала не понял, как не существует, если существует. Оказалось это версия 2.6.0 глупит (и 2.5.0 и 2.4.х), в версии 2.3.5 таки не существует.

[maxal]

dmd
Вот так и не существует - см., например, в википедии
Легко убедится, что $2^{67}-1 = 193707721\cdot 761838257287$, а потому примитивного корня по модулю $2^{67}-1$ не существует.

Что же касается PARI/GP - в документации сказано:

Цитата:

znprimroot(n) returns a primitive root (generator) of (Z/nZ)^*, whenever this latter group is cyclic (n = 4 or n = 2p^k or n = p^k, where p is an odd prime and k >= 0). If the group is not cyclic, the result is undefined.

Обратите внимание на выделенное предложение.

[dmd]

maxal в сообщении #468915 писал(а):

А эта ошибка означает всего лишь, что $3^x\equiv 2\pmod{2^{67}-1}$ не имеет решений.

Возможно, кроме двух фильтрующих $p$ сравнений с остатками в виде степеней двойки

$3^{\frac{M-1}{p}}\equiv 2^y\pmod M$

$3^{\frac{M-1}{2p}}\equiv -2^x\pmod M$

$x=\frac{y}{2}$ либо $x=\frac{y+p}{2}$

существует и третье с остатком в виде двойки строго в первой степени

$3^t\equiv 2\pmod M$

-- Вс июл 17, 2011 13:34:16 --

maxal в сообщении #469067 писал(а):

dmd
Вот так и не существует - см., например, в википедии
Легко убедится, что $2^{67}-1 = 193707721\cdot 761838257287$, а потому примитивного корня по модулю $2^{67}-1$ не существует.

Что же касается PARI/GP - в документации сказано:

Цитата:

znprimroot(n) returns a primitive root (generator) of (Z/nZ)^*, whenever this latter group is cyclic (n = 4 or n = 2p^k or n = p^k, where p is an odd prime and k >= 0). If the group is not cyclic, the result is undefined.

Обратите внимание на выделенное предложение.

Это теперь понятно. Непонятно, почему новые версии конкретный результат возвращают, будто бы примитивный корень существует.

                  GP/PARI CALCULATOR Version 2.5.0 (released)
           i686 running linux (ix86/GMP-5.0.2 kernel) 32-bit version
                        compiled: Jul  1 2011, gcc-4.2.4
                 (readline v5.2 enabled, extended help enabled)

                     Copyright (C) 2000-2011 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes
WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 4000000, primelimit = 500509
? p=67;M=2^p-1;znprimroot(M)
%1 = Mod(3, 147573952589676412927)

Версия 2.3.5 чётко ответила - не существует.

[maxal]

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

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

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

[iJoy]

Практически классическое решето Эратосфена.
На P4 3.0GHz 2Gb RAM поиск в пределах миллиона занимает 3-5 сек.
Подскажите пожалуйста, где здесь узкое место (VB.NET)?

Dim dt As DateTime = Now
Dim max As ULong = 1000000 '1 млн.
Dim b(Math.Ceiling(max / 8) - 1) As Byte
For f As ULong = 0 To b.Length - 1
    b(f) = 255
Next
b(0) = b(0) Xor 1
Dim n As New List(Of UInteger)
Dim i As ULong, ix As ULong, bx As Byte
Do
    ix = 0
    For f As ULong = i To max - 1
        If b(Math.Floor(f / 8)) And (2 ^ (f Mod 8)) Then
            ix = f + 1
            Exit For
        End If
    Next
    If ix = 0 Then Exit Do
    i = ix
    n.Add(i)
    If Math.Sqrt(ULong.MaxValue) >= i Then
        For f As ULong = i ^ 2 - 1 To max - 1 Step i
            bx = b(Math.Floor(f / 8))
            b(Math.Floor(f / 8)) = bx And (bx Xor (2 ^ (f Mod 8)))
        Next
    End If
Loop
MsgBox("Найдено простых чисел: " & n.Count & " из " & max & vbCrLf & _
       "Наибольшее простое число: " & n(n.Count - 1) & vbCrLf & _
       "Затраченное время, сек.: " & DateDiff(DateInterval.Second, dt, Now))

[venco]

По моему, слабое место - сам VB.
Я не знаю, насколько эффективно исполняются операции типа Math.Floor(i/8) и 2 ^ (f Mod 8).
Подозеваю, что они в сотни раз медленнее Сишных битовых операций.
Если в VB есть битовые сдвиги - надо использовать их.

[iJoy]

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

По моему, слабое место - сам VB.

Между vb.net и C# по скорости практически разницы никакой, ибо оба они сначала в MSIL компилируются.

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

Я не знаю, насколько эффективно исполняются операции типа Math.Floor(i/8) и 2 ^ (f Mod 8).
Подозеваю, что они в сотни раз медленнее Сишных битовых операций.
Если в VB есть битовые сдвиги - надо использовать их.

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

начальный вариант этого кода использовал массив b() as boolean, работал быстрее в разы (до 100млн. за 12-17 сек.), но непомерно прожорлив к памяти.

[Droog_Andrey]

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

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