Как видим, для поиска квадратичного
Пример 6
Как видим, для поиска квадратичного невычета r можно использовать функцию JacobiSymbol. В качестве г можно брать небольшие нечетные числа и вычислять для них символ Якоби. (Для квадратичного невычета символ Якоби равен -1.) Как только мы найдем квадратичный невычет r, можем проверить, выполняется ли сравнение r2 k =-1 (mod 32n+l). Теперь легко написать функцию, вычисляющую квадратичный невычет.
ММ3nr[nn_]:= Module[{r=5, JS=JacobiSymbol[5, nn]}, While[JS!=-1 && r<nn, r+=2; If[GCD[r,nn]= =1, JS=JacobiSymbol[r,nn]]];r]
Чтобы запрограммировать критерий простоты, воспользуемся функцией PowerMod.
MMSnPrime[n_]:= Module[{t = 3*2^n+1), If[Mod[n,4]!=0, PowerMod[5,(t-1)/2,t]==t-l, PowerMod[ММЗnr[t],(t-1)/2,t]==t-l]]
Теперь, наконец, можем написать окончательную версию программы.
M3nv01[n_]:= Block[{j=l» nnprime=25000,primen=Prime[nnprime], nn=Min[n,primen]}, While [MMkn[3,j]<= primen && j<=n, {If[MM3nPrime[j],Print[j]], J++H; If[j<n, t=Sort[DeleteCases[Array[f3,nnprime,3],Null]]; While[j<=nn, If[fx[j,t], If[MM3nPrime[j],Print[j]]];j++]]]
Запуская программу с параметром nnprime = 10000 и 25000, убеждаемся, что при этих (и всех промежуточных) значениях генерация таблицы начинается после вывода показателя 12, но до вывода показателя 18. Затем программа довольно быстро добирается до показателя 3912, после вывода которого "уходит в себя" аж до вывода показателя 20 909. (Заметьте, что, в отличие от предыдущей версии программы, перерыв между показателями 534 и 2 208 не слишком заметен — эту "достопримечательность" вы запросто можете пропустить, если выйдете выпить чашечку кофе!)
Оказывается, что число 3*2n+ 1 является простым при n = 1, 2, 5, 6, 8, 12,
18, 30, 36, 41, 66, 189, 201, 209, 276, 353, 408, 438, 534, 2 208, 2 816, 3 168, 3 189, 3 912, 20 909, 34 350,. 42 294, 42 665, 44 685, 48 150, 55 182, 59 973, 80 190, 157 169, 213 321. При всех других n, не превосходящих 300 000, число 3*2n + 1 яляется составным.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий