강한 유사 소수

강한 유사 소수는 Miller-Rabin 소수 검정을 통과하는 합성 숫자입니다.모든 소수는 이 검정을 통과하지만 합성물의 일부도 통과하므로 "의사 소수"가 됩니다.

모든 코프림 기저(카마이클 수)에 대한 유사 소수가 존재하는 페르마 유사 소수와 달리, 모든 기저에 대한 강력한 유사 소수인 합성물은 없습니다.

동기부여 및 첫 번째 사례

n = 31697이 가능한 소수(PRP)인지 조사하려고 합니다.우리는 기저 a = 3을 선택하고 페르마의 작은 정리에서 영감을 받아 다음을 계산합니다.

${\displaystyle 3^{31696}\equiv 1pmod {31697}}}$

이것은 31697이 페르마 PRP(베이스 3)임을 보여주기 때문에 프라임으로 의심할 수 있습니다.이제 반복적으로 지수를 절반으로 나눕니다.

$디스플레이 스타일 3^{{\48}\equiv 1158pmod {31697}}}$

${\displaystyle 3^{7924}\equiv 1pmod {31697}}}$

${\displaystyle 3^{3962}\equiv 28419 mod {31697}}}$

처음 몇 번은 흥미로운 것을 산출하지 못했지만(결과는 여전히 1 모듈로 31697), 지수 3962에서 우리는 1도 마이너스 1(즉, 31696) 모듈로 31697이 아닌 결과를 봅니다.이는 31697이 실제로 복합적이라는 것을 증명합니다(29×1093과 같습니다).모듈로 a 소수, 나머지 1은 1과 마이너스 1 외에 다른 제곱근을 가질 수 없습니다.이것은 31697이 기본 3에 대한 강력한 유사 소수가 아님을 보여줍니다.

다른 예에서는 n = 47197을 선택하고 동일한 방법으로 계산합니다.

${\displaystyle 3^{47196}\equiv 1pmod {47197}} 표시$

$디스플레이 스타일 3^{23598}\equiv 1mod {47197}}$

${\displaystyle 3^{11799}\equiv 1pmod {47197}}}$

이 경우 홀수 지수에 도달할 때까지 결과는 1(모드 47197)로 계속됩니다.이 상황에서, 우리는 47197이 3루수가 될 가능성이 높다고 말합니다.이 PRP는 사실 복합적인 것으로 밝혀졌기 때문에(3개가 아닌 다른 염기를 선택하면 알 수 있음) 47197은 3개의 염기에 대한 강력한 유사 소수입니다.

마지막으로, n = 74593을 고려하면 다음과 같습니다.

${\displaystyle 3^{74592}\equiv 1pmod {74593}}}$

${\displaystyle 3^{37296}\equiv 1pmod {74593}}}$

${\displaystyle 3^{18648}\equiv 74592\pmod {74593}}}$

여기서, 우리는 마이너스 1 모듈로 74593에 도달하는데, 이는 프라임으로 완벽하게 가능한 상황입니다.이러한 상황이 발생하면 (지수가 아직 홀수가 아님에도 불구하고) 계산을 중지하고 74593이 기저 3에 대한 강력한 확률 소수(그리고 밝혀진 바와 같이 강력한 유사 소수)라고 말합니다.

형식 정의

다음과 같은 경우, d가 홀수인^s 홀수 합성수 n = d · 2 + 1을 강(Fermat) 유사 소수라고 합니다.

${\displaystyle a^{d}\equiv 1mod {n}} 표시$

또는

${displaystyle a^{d\cdot 2^{r}}\equiv -1pmod {n}}\mbox{mbox}(일부의 경우)0\leq r<s.}$

(숫자 n이 위의 조건 중 하나를 만족하고 그것이 소수인지 아직 알 수 없다면, a를 기저로 할 수 있는 강력한 가능한 소수라고 말하는 것이 더 정확합니다.하지만 만약 우리가 n이 소수가 아니라는 것을 안다면, 우리는 강한 유사 소수라는 용어를 사용할 수 있습니다.)

π ±1(mod)이면 정의가 사소한 것으로 충족되므로 이러한 사소한 기저는 종종 제외됩니다.

가이는 실수로 모든 소수가 만족하지 않는 ^[1]첫 번째 조건만 가진 정의를 제공합니다.

강한 유사 소수의 특성

a를 기저로 하는 강력한 유사 소수는 항상 오일러-야코비 유사 소수, 오일러^[2] 유사 소수 및 페르마 유사 소수이지만 모든 오일러 및 페르마 유사 소수가 강력한 유사 소수는 아닙니다.카마이클 수는 일부 기저에서는 강력한 유사 소수일 수 있습니다. 예를 들어, 561은 기저 50에 대한 강력한 유사 소수이지만 모든 기저에는 그렇지 않습니다.

합성수 n은 ^[3][4]n 이하의 모든 기저의 최대 4분의 1에 대한 강한 유사 소수입니다. 따라서 모든 기저에 강한 유사 소수인 "강한 카마이클 수"는 없습니다.따라서 랜덤 기저가 주어지면 숫자가 해당 기저에 대한 강력한 유사 소수일 확률이 1/4보다 작으므로 널리 사용되는 Miller-Rabin 소수 검정의 기초가 됩니다.실제 고장 확률은 일반적으로 훨씬 작습니다.폴 에르도스와 칼 포메랑스는 1986년에 만약 임의의 정수 n이 밀러-라빈 소수점 b에 합격한다면, n은 거의 확실하게 ^[5]소수점이 된다는 것을 보여주었습니다.예를 들어, 처음 2,500,000,000개의 양의 정수 중 2진수로 추정되는 정수는 1,091,987,405개이지만, 그 중 21,853개만이 유사 소수이고, 후자가 ^[6]전자의 부분 집합이기 때문에 더 적은 수의 강한 유사 소수입니다.그러나 아르노는 307 미만의 모든 염기에 강력한 유사 소수인 397자리 카마이클 번호를 제공합니다.그러한 숫자가 아마도 소수로 잘못 선언될 가능성을 줄이는 한 가지 방법은 베일리에서처럼 강력한 가능성 있는 소수 테스트와 루카스 가능성 있는 소수 테스트를 결합하는 것입니다.PSW 우선 순위 검정.

어떤 ^[2]기저에도 강력한 유사 소수가 무한히 많습니다.

예

베이스 2에 대한 첫 번째 강한 유사 소수는

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ...(OEIS의 시퀀스 A001262)

첫 번째부터 세 번째 베이스는

121, 703, 1891, 381, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... (OIS의 경우 시퀀스 A020229)

1번부터 5번 베이스는

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (OEIS의 시퀀스 A020231)

베이스 4의 경우 OEIS: A020230을 참조하고 베이스 6에서 100의 경우 OEIS: A020232에서 OEIS: A020326을 참조합니다.위의 조건을 여러 기저로 테스트함으로써 하나의 기저를 단독으로 사용하는 것보다 다소 더 강력한 소수점 검정을 받게 됩니다.예를 들어, 기저 2⁹, 3 및 5에 대해 동시에 강한 유사 소수인 25·10보다 작은 숫자는 13개뿐입니다.이들은 의 ^[2]표 7에 나열되어 있습니다.가장 작은 숫자는 25326001입니다.즉, n이 2532001보다 작고 n이 기저 2, 3, 5에 대한 강력한 확률 소수이면 n은 소수입니다.

이것을 더하면, 3825123056546413051은 9개의 베이스 2, 3, 5, 7, 11, 13, 17, 19, ^[8]23에 대한 강력한 유사 소수입니다.^[9] 따라서, n이 3825123056546413051보다 작고 n이 이 9개의 염기에 대한 강력한 가능성 소수라면, n은 소수입니다.

반드시 최상의 것은 아닌 염기를 현명하게 선택함으로써 더 나은 테스트를 구성할 수 있습니다.예를 들어, 7개의 기저 2, 325, 9375, 28178, 450775, 9780504 및 1795265022 ^[10]모두에 대한 강력한 유사 소수인 ${{displaystyle<2^{64$}}는 없습니다.

a를 기초로 하는 가장 작은 강한 유사 소수

a	최소 SPSP	a	최소 SPSP	a	최소 SPSP	a	최소 SPSP
1	9	33	545	65	33	97	49
2	2047	34	33	66	65	98	9
3	121	35	9	67	33	99	25
4	341	36	35	68	25	100	9
5	781	37	9	69	35	101	25
6	217	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	91	44	9	76	15	108	91
13	85	45	481	77	39	109	9
14	15	46	9	78	77	110	111
15	1687	47	65	79	39	111	55
16	15	48	49	80	9	112	65
17	9	49	25	81	91	113	57
18	25	50	49	82	9	114	115
19	9	51	25	83	21	115	57
20	21	52	51	84	85	116	9
21	221	53	9	85	21	117	49
22	21	54	55	86	85	118	9
23	169	55	9	87	247	119	15
24	25	56	55	88	87	120	91
25	217	57	25	89	9	121	15
26	9	58	57	90	91	122	65
27	121	59	15	91	9	123	85
28	9	60	481	92	91	124	25
29	15	61	15	93	25	125	9
30	49	62	9	94	93	126	25
31	15	63	529	95	1891	127	9
32	25	64	9	96	95	128	49

레퍼런스