Psevdopraštevilo

Iz Wikipedije, proste enciklopedije

Psévdopráštevilo je celo število, ki ima določeno lastnost, vezano na praštevila, samo pa ni praštevilo.

Najpomembnejša praštevila izhajajo iz Fermatovega malega izreka in se zato imenujejo Fermatova psevdopraštevila. Izrek pravi, da če je p praštevilo in je a tuje p, potem je a^p-1 - 1 deljivo s p. Če število x ni praštevilo, a je tuj x in x deli a^x-1 - 1, se x imenuje praštevilo za bazo a. Število x, ki je psevdopraštevilo za vse vrednosti a, katera so x tuja, se imenuje Carmichaelovo število.

Najmanjše psevdopraštevilo za bazo 2 je 341. Ni praštevilo, ker je enako 11 · 31, vendar zanj velja Fermatov mali izrek, 2³⁴¹ = 2 (mod 341).

Velika praštevila se uporabljajo na področjih kot je na primer kriptografija z javnim ključem RSA. Običajni algoritem za generiranje praštevil poišče naključna liha števila in preveri, če so praštevila. Preverjanje praštevil pa je počasno. Če ne potrebujemo natančnega testa (sestavljeno število z malo verjetnostjo smatramo za praštevilo), lahko uporabimo hitre algoritme na osnovi Fermatovega malega izreka. Na preprost način, na primer, ugotovimo ali je število x praštevilo z izbiro naključnega števila a in preverimo ali x deli a ^x - a. Če je odgovor nikalen, potem x ne more biti praštevilo in obratno, imamo lahko x za "verjetno praštevilo", ter tako nadaljujemo s preverjanjem za druge vrednosti a.

Izboljšane inačice tega algoritma nam dajo močno verjetna praštevila. Monier in Rabin sta pokazala, da je za izboljšan algoritem za vsak a verjetnost pojavitve napačnega praštevila vsaj 3 od 4.

Obstaja neskončno mnogo psevdopraštevil (in celo neskončno mnogo Carmichaelovih števil), vendar so zelo redka. Pod 1000 so samo 3 psevdopraštevila za bazo 2 in pod milijon samo 245. Psevdopraštevila za bazo 2 se imenujejo Pouletova števila ali včasih Sarrusova ševila ali tudi Fermatova števila. (SIDN A001567). Pouletova števila in Carmichaelova števila (krepko) pod 10000 so:

n		n		n		n		n
1	341 = 11 · 31	11	2821 = 7 · 13 · 31	21	8481 = 3 · 11 · 257	31	15709 = 23 · 683	41	30121 = 7 · 13 · 331
2	561 = 3 · 11 · 17	12	3277 = 29 · 112	22	8911 = 7 · 19 · 67	32	15841 = 7 · 31 · 73	42	30889 = 17 · 23 · 79
3	645 = 3 · 5 · 43	13	4033 = 37 · 109	23	10261 = 31 · 331	33	16705 = 5 · 13 · 257	43	31417 = 89 · 353
4	1105 = 5 · 13 · 17	14	4369 = 17 · 257	24	10585 = 5 · 29 · 73	34	18705 = 3 · 5 · 29 · 43	44	31609 = 73 · 433
5	1387 = 19 · 73	15	4371 = 3 · 31 · 47	25	11305 = 5 · 7 · 17 · 19	35	18721 = 97 · 193	45	31621 = 103 · 307
6	1729 = 7 · 13 · 19	16	4681 = 31 · 151	26	12801 = 3 · 17 · 251	36	19951 = 71 · 281	46	33153 = 3 · 43 · 257
7	1905 = 3 · 5 · 127	17	5461 = 43 · 127	27	13741 = 7 · 13 · 151	37	23001 = 3 · 11 · 17 · 41	47	34945 = 5 · 29 · 241
8	2047 = 23 · 89	18	6601 = 7 · 23 · 41	28	13747 = 59 · 233	38	23377 = 97 · 241	48	35333 = 89 · 397
9	2465 = 5 · 17 · 29	19	7957 = 73 · 109	29	13981 = 11 · 31 · 41	39	25761 = 3 · 31 · 277	49	39865 = 5 · 7 · 17 · 67
10	2701 = 37 · 73	20	8321 = 53 · 157	30	14491 = 43 · 337	40	29341 = 13 · 37 · 61	50	41041 = 7 · 11 · 13 · 41

Pouletovo število za katerega za vse njegove delitelje d velja d | 2^d - 2 se imenuje super Pouletovo število. Za vsa ta števila velja μ(n) = 1 (SIDN A050217). Obstaja neštevno mnogo Pouletovih števil, ki niso super-Pouletova števila.

Prva najmanjša psevdopraštevila za druge baze a ≤ 200 so:

a	najmanjše pp	a	najmanjše pp	a	najmanjše pp	a	najmanjše pp
		51	65 = 5 · 13	101	175 = 52 · 7	151	175 = 52 · 7
2	341 =" 11" · 13	52	85 = 5 · 17	102	133 = 7 · 19	152	153 = 32 · 17
3	91 = 7 · 13	53	65 = 5 · 13	103	133 = 7 · 19	153	209 ="11 " · 19
4	15 = 3 · 5	54	55 =" 5 " · 11	104	105 = 3 · 5 · 7	154	155 =" 5 " · 31
5	124 = 22 · 31	55	63 = 32 · 7	105	451 ="11 " · 41	155	231 = 3 · 7 · 11
6	35 = 5 · 7	56	57 = 3 · 19	106	133 = 7 · 19	156	217 =" 7 " · 31
7	25	57	65 = 5 · 13	107	133 =" 7 " · 19	157	186 = 2 · 3 · 31
8	9	58	133 = 7 · 19	108	341 =" 11" · 31	158	159 = 3 · 53
9	28 = 22 · 7	59	87 = 3 · 29	109	117 = 32 · 13	159	247 =" 13" · 19
10	33 = 3 · 11	60	341 =" 11" · 31	110	111 = 3 · 37	160	161 = 7 · 23
11	15 = 3 · 5	61	91 =" 7 " · 13	111	190 = 2 · 5 · 19	161	190=2 · 5 · 19
12	65 =" 5 " · 13	62	63 = 32 · 7	112	121	162	481 ="13 " · 37
13	21 = 3 · 7	63	341 =" 11" · 31	113	133 = 7 · 19	163	186 = 2 · 3 · 31
14	15 = 3 · 5	64	65 = 5 · 13	114	115 = 5 · 23	164	165 = 3 · 5 · 11
15	341 =" 11" · 13	65	112 = 24 · 7	115	133 =" 7 " · 19	165	172 = 22 · 43
16	51 =" 3 " · 17	66	91 = 7 · 13	116	117 = 32 · 13	166	301 = 7 · 43
17	45 = 32 · 5	67	85 = 5 · 17	117	145 = 5 · 29	167	231 = 3 · 7 · 11
18	25	68	69 =" 3 " · 23	118	119 = 7 · 17	168	169
19	45 = 32 · 5	69	85 = 5 · 17	119	177 =" 3 " · 59	169	231 = 3 · 7 · 11
20	21 = 3 · 7	70	169	120	121	170	171 = 32 · 19
21	55 =" 5 " · 11	71	105 = 3 · 5 · 7	121	133 = 7 · 19	171	215 = 5 · 43
22	69 = 3 · 23	72	85 = 5 · 17	122	123 = 3 · 41	172	247 ="13 " · 19
23	33 = 3 · 11	73	111 = 3 · 37	123	217 = 7 · 31	173	205 = 5 · 41
24	25	74	75 = 3 · 52	124	125 = 33	174	175 = 52 · 7
25	28 = 22 · 7	75	91 =" 7 " · 13	125	133 = 7 · 19	175	319 =" 11" · 19
26	27 = 33	76	77 = 7 · 11	126	247 =" 13" · 19	176	177 = 3 · 59
27	65 = 5 · 13	77	247 =" 13" · 19	127	153 = 32 · 17	177	196 = 22 · 72
28	45 = 32 · 5	78	341 =" 11" · 31	128	129 =" 3 " · 43	178	247 ="13 " · 19
29	35 = 5 · 7	79	91 = 7 · 13	129	217 = 7 · 31	179	185 = 5 · 37
30	49	80	81 = 34	130	217 = 7 · 31	180	217 = 7 · 31
31	49	81	85 = 5 · 17	131	143 ="11 " · 13	181	195 = 3 · 5 · 13
32	33 = 3 · 11	82	91 = 7 · 13	132	133 = 7 · 19	182	183 = 3 · 61
33	85 = 5 · 17	83	105 = 3 · 5 · 7	133	145 =" 5 " · 29	183	221 =" 13" · 17
34	35 =" 5 " · 7	84	85 = 5 · 17	134	135 = 33 · 5	184	185 = 5 · 37
35	51 = 3 · 17	85	129 =" 3 " · 43	135	221 =" 13" · 17	185	217 = 7 · 31
36	91 = 7 · 13	86	87 =" 3 " · 29	136	265 = 5 · 53	186	187 =" 11" · 17
37	45 = 32 · 5	87	91 = 7 · 13	137	148 = 22 · 37	187	217 = 7 · 31
38	39 = 3 · 13	88	91 = 7 · 13	138	259 =" 7 " · 37	188	189 = 33 · 7
39	95 =" 5 " · 19	89	99 = 32 · 11	139	161 = 7 · 23	189	235 = 5 · 47
40	91 = 7 · 13	90	91 =" 7 " · 13	140	141 = 3 · 47	190	231 = 3 · 7 · 11
41	105 = 3 · 5 · 7	91	115 = 5 · 23	141	355 = 5 · 71	191	217 =" 7 " · 31
42	205 = 5 · 41	92	93 = 3 · 31	142	143 ="11 " · 13	192	217 = 7 · 31
43	77 = 7 · 11	93	301 = 7 · 43	143	213 = 3 · 71	193	276 = 22 · 3 · 23
44	45 = 32 · 5	94	95 = 5 · 19	144	145 = 5 · 29	194	195 = 3 · 5 · 13
45	76 = 22 · 19	95	141 = 3 · 47	145	153 = 32 · 17	195	259 =" 7 " · 37
46	133 = 7 · 19	96	133 = 7 · 19	146	147 = 3 · 72	196	205 = 5 · 41
47	65 =" 5 " · 13	97	105 = 3 · 5 · 7	147	169	197	231 = 3 · 7 · 11
48	49	98	99 = 32 · 11	148	231 = 3 · 7 · 11	198	247 =" 13" · 19
49	66 = 2 · 3 · 11	99	145 = 5 · 29	149	175 = 52 · 7	199	225 = 32 · 52
50	51 = 3 · 17	100	153 = 32 · 17	150	169	200	201 = 3 · 67

[uredi] Lastnosti psevdopraštevil

Števila 2^n-1 ne računamo. Na prvi pogled se zdi, da je za vsa najmanjša psevdopraštevila v katerikoli bazi a μ(n) enaka 0 ali 1, vendar, začudujoče, temu ni tako. Prvih baz a, za katere ima njihovo najmanjše psevdopraštevilo μ(n) = -1, pod 100 je samo pet:

a	najmanjše pp
41	105 = 3 · 5 · 7
49	66 = 2 · 3 · 11
71	105 = 3 · 5 · 7
83	105 = 3 · 5 · 7
97	105 = 3 · 5 · 7

To je še en slikovit primer kako je potrebno biti pazljiv z domnevami, ki temeljijo na izkustvenem dokazu v matematiki. Fermatov mali izrek nam za prva števila da:

n	an-1-1	an-1 - 1 mod n
1	0	0
2	1	1
3	3	0
4	7	3
5	15	0
6	31	1
7	63	0
8	127	7
9	255	3
10	511	1
11	1023	0
12	2047	7
13	4095	0
14	8191	1
15	16383	3
16	32767	15
17	65535	0
18	131071	13
19	262143	0
20	524287	7
21	1048575	3
22	2097151	1
23	4194303	0
24	8388607	7
25	16777215	15
26	33554431	1
27	67108863	12
28	134217727	7
29	268435455	0
30	536870911	1
31	1073741823	0
32	2147483647	31
33	4294967295	3

[uredi] Glej tudi

• Eulerjevo psevdopraštevilo
  • Eulerjeva praštevila za bazo 2 (SIDN A006970)
• Euler-Jacobijevo psevdopraštevilo
  • Euler-Jacobijeva psevdopraštevila za bazo 2 (SIDN A047713)
  • Euler-Jacobijeva psevdopraštevila za bazo 3 (SIDN A048950)
• Fibonaccijevo psevdopraštevilo
• Frobeniusovo psevdopraštevilo
• Lucasovo psevdopraštevilo
• močno Frobeniusovo psevdopraštevilo
• močno Lucasovo psevdopraštevilo
• močno psevdopraštevilo
  • močna psevdopraštevila za bazo 2 (SIDN A001262)
• Perrinovo psevdopraštevilo
• Somer-Lucasovo psevdopraštevilo
• zelo močno Lucasovo psevdopraštevilo