Псевдопрям Эйлера - Euler pseudoprime

В арифметическом , с нечетным составным целым числом п называется псевдопростое число Эйлера к базовому а , если и п являются взаимно простыми , а

{\ Displaystyle а ^ {(п-1) / 2} \ эквив \ пм 1 {\ pmod {п}}}

(где мод относится к операции по модулю ).

Мотивом для этого определения является тот факт, что все простые числа p удовлетворяют приведенному выше уравнению, которое может быть выведено из малой теоремы Ферма . Теорема Ферма утверждает, что если p простое и взаимно простое с a , то a ^{p −1} ≡ 1 (mod p ). Предположим, что p > 2 простое число, тогда p можно выразить как 2 q + 1, где q - целое число. Таким образом, a ^{(2 q +1) - 1} ≡ 1 (mod p ), что означает, что a ^{2 q} - 1 ≡ 0 (mod p ). Это можно разложить на множители как ( a ^q - 1) ( a ^q + 1) ≡ 0 (mod p ), что эквивалентно a ^{( p −1) / 2} ≡ ± 1 (mod p ).

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

Каждое псевдопростое число Эйлера также является псевдопервичным числом Ферма . Невозможно произвести определенный тест на простоту, основанный на том, является ли число псевдопростым числом Эйлера, потому что существуют абсолютные псевдопростые числа Эйлера , числа, которые являются псевдопростыми числами Эйлера для каждой базы, относительно простой по отношению к себе. Абсолютные псевдопростые числа Эйлера являются подмножеством абсолютных псевдопростых чисел Ферма или чисел Кармайкла , а наименьшее абсолютное псевдопростое число Эйлера равно 1729 = 7 × 13 × 19.

Связь с псевдопростыми числами Эйлера – Якоби

Немного более сильное условие, что

{\ Displaystyle а ^ {(п-1) / 2} \ эквив \ влево ({\ гидроразрыва {а} {п}} \ вправо) {\ pmod {п}}}

где п нечетная составной, то наибольший общий делитель из и п равно 1, и ( / п ) является символом Якобите , является более распространенным определением псевдопростого числа Эйлера. См., Например, страницу 115 книги Коблица, указанной ниже, страницу 90 книги Ризеля или страницу 1003 из. Обсуждение чисел этой формы можно найти в псевдопростом числе Эйлера – Якоби . Абсолютных псевдопростых чисел Эйлера – Якоби не существует.

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

Реализация на Lua

function EulerTest(k)
  a = 2
  if k == 1 then return false
  elseif k == 2 then return true
  else
    if (modPow(a,(k-1)/2,k) == 1) or (modPow(a,(k-1)/2,k) == k-1) then
      return true
    else
      return false
    end
  end
end

Примеры

п	Псевдопростые числа Эйлера по основанию n
1	9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, 123, 125, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 165, 169, 171, 175, 177, 183, 185, 187, 189, 195, 201, 203, 205, 207, 209, 213, 215, 217, 219, 221, 225, 231, 235, 237, 243, 245, 247, 249, 253, 255, 259, 261, 265, 267, 273, 275, 279, 285, 287, 289, 291, 295, 297, 299, ... (все нечетные композиты)
2	341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, ...
3	121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 7381, 8401, 8911, ...
4	341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...
5	217, 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, ...
6	185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365, ...
7	25, 325, 703, 817, 1825, 2101, 2353, 2465, 3277, 4525, 6697, 8321, ...
8	9, 21, 65, 105, 133, 273, 341, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1541, 1661, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 5461, 6305, 6533, 6601, 7161, 8321, 8481, 9265, 9709, ...
9	91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ...
10	9, 33, 91, 481, 657, 1233, 1729, 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401, ...
11	133, 305, 481, 645, 793, 1729, 2047, 2257, 2465, 4577, 4921, 5041, 5185, 8113, ...
12	65, 91, 133, 145, 247, 377, 385, 1649, 1729, 2041, 2233, 2465, 2821, 3553, 6305, 8911, 9073, ...
13	21, 85, 105, 561, 1099, 1785, 2465, 5149, 5185, 7107, 8841, 8911, 9577, 9637, ...
14	15, 65, 481, 781, 793, 841, 985, 1541, 2257, 2465, 2561, 2743, 3277, 5185, 5713, 6533, 6541, 7171, 7449, 7585, 8321, 9073, ...
15	341, 1477, 1541, 1687, 1729, 1921, 3277, 6541, 9073, ...
16	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919, ...
17	9, 91, 145, 781, 1111, 1305, 1729, 2149, 2821, 4033, 4187, 5365, 5833, 6697, 7171, ...
18	25, 49, 65, 133, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2149, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6517, 6601, 7345, .. .
19	9, 45, 49, 169, 343, 561, 889, 905, 1105, 1661, 1849, 2353, 2465, 2701, 3201, 4033, 4681, 5461, 5713, 6541, 6697, 7957, 8145, 8281, 8401, 9997, ...
20	21, 57, 133, 671, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2761, 3201, 5461, 5473, 5713, 5833, 6601, 6817, 7999, ...
21 год	65, 221, 703, 793, 1045, 1105, 2465, 3781, 5185, 5473, 6541, 7363, 8965, 9061, ...
22	21, 69, 91, 105, 161, 169, 345, 485, 1183, 1247, 1541, 1729, 2041, 2047, 2413, 2465, 2821, 3241, 3801, 5551, 7665, 9453, ...
23	33, 169, 265, 341, 385, 481, 553, 1065, 1271, 1729, 2321, 2465, 2701, 2821, 3097, 4033, 4081, 4345, 4371, 4681, 5149, 6533, 6541, 7189, 7957, 8321, 8651, 8745, 8911, 9805, ...
24	25, 175, 553, 805, 949, 1541, 1729, 1825, 1975, 2413, 2465, 2701, 3781, 4537, 6931, 7501, 9085, 9361, ...
25	217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ...
26	9, 25, 27, 45, 133, 217, 225, 475, 561, 589, 703, 925, 1065, 2465, 3325, 3385, 3565, 3825, 4741, 4921, 5041, 5425, 6697, 8029, 9073, ...
27	65, 121, 133, 259, 341, 365, 481, 703, 1001, 1541, 1649, 1729, 1891, 2465, 2821, 2981, 2993, 3281, 4033, 4745, 4921, 4961, 5461, 6305, 6533, 7381, 7585, 8321, 8401, 8911, 9809, 9841, 9881, ...
28 год	9, 27, 145, 261, 361, 529, 785, 1305, 1431, 2041, 2413, 2465, 3201, 3277, 4553, 4699, 5149, 7065, 8321, 8401, 9841, ...
29	15, 21, 91, 105, 341, 469, 481, 793, 871, 1729, 1897, 2105, 2257, 2821, 4371, 4411, 5149, 5185, 5473, 5565, 6097, 7161, 8321, 8401, 8421, 8841, ...
30	49, 133, 217, 341, 403, 469, 589, 637, 871, 901, 931, 1273, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 4081, 4097, 5729, 6031, 6061, 6097, 6409, 6817, 7657, 8023, 8029, 8401, 9881, ...

Наименьшее псевдопростое число Эйлера по основанию n

п	Наименьшая ВПСП	п	Наименьшая ВПСП	п	Наименьшая ВПСП	п	Наименьшая ВПСП
1	9	33	545	65	33	97	21 год
2	341	34	21 год	66	65	98	9
3	121	35 год	9	67	33	99	25
4	341	36	35 год	68	25	100	9
5	217	37	9	69	35 год	101	25
6	185	38	39	70	69	102	133
7	25	39	133	71	9	103	51
8	9	40	39	72	85	104	15
9	91	41 год	21 год	73	9	105	451
10	9	42	451	74	15	106	15
11	133	43 год	21 год	75	91	107	9
12	65	44 год	9	76	15	108	91
13	21 год	45	133	77	39	109	9
14	15	46	9	78	77	110	111
15	341	47	65	79	39	111	55
16	15	48	49	80	9	112	65
17	9	49	25	81 год	91	113	21 год
18	25	50	21 год	82	9	114	115
19	9	51	25	83	21 год	115	57
20	21 год	52	51	84	85	116	9
21 год	65	53	9	85	21 год	117	49
22	21 год	54	55	86	65	118	9
23	33	55	9	87	133	119	15
24	25	56	33	88	87	120	77
25	217	57	25	89	9	121	15
26	9	58	57	90	91	122	33
27	65	59	15	91	9	123	85
28 год	9	60	341	92	21 год	124	25
29	15	61 год	15	93	25	125	9
30	49	62	9	94	57	126	25
31 год	15	63	341	95	141	127	9
32	25	64	9	96	65	128	49

Смотрите также

Вероятное простое число

Languages

In other projects