81:
71:
53:
22:
248:
The beginning of this article says, "For a fixed base a, it is unusual for a composite number to be a probable prime (that is, a pseudoprime) to that base. For example, there are only 21853 pseudoprimes base 2 that are less than 25*10^9 (see page 1005 of ) and 1091987405 primes less than 25*10^9."
227:
Surely a pseudoprime (for some criterion) is a composite number which passes the criterion. The word 'composite' is missing from this definition. My understanding is that "probable prime" menas a number that passes the criterion; it is very likely to be a prime, but if proved composite is then a
252:
The second sentence has nothing to do with the first: it compares pseudoprimes with primes, not with composites. The relevant comparison is the number of pseudoprimes compared to the number of composite numbers (say, up to 25*10^9). Even more relevant is the number of pseudoprimes compared to the
173:
over the input numbers (prime/composite), but over an additional sequence of "coin tosses" the algorithm does. Thus, a statement like "the algorithm is correct with probability 3/4" does not mean it will miss 1/4 of composites; it means that for any given composite, if you run the algorithm
274:
With n = 25*10^9, the result is that there are 11408012595 odd composite numbers up to 25*10^9, but only 21853 pseudoprimes base 2. So, only about .00019% of odd composites up to 25*10^9 are pseudoprimes base 2.
174:
independently multiple times, about 3/4 of the runs will detect the number as being composite. However, such algorithms often do use some notion of pseudoprimeness; typically, it works by choosing a random
385:
to specify page 1005. The same reference is used several times with different page numbers. Another time, please describe the alleged problem from the beginning. I spent time checking everything.
133:
300:
434:
127:
429:
103:
400:
362:
326:
94:
58:
304:
165:
The paragraph on cryptography is misguided. Typical probabilistic primality testing algorithms (e.g. Rabin-Miller) detect
33:
191:
21:
404:
366:
330:
390:
345:
39:
80:
280:
224:
The main article has: "A strong probable prime to base a is called a strong pseudoprime to base a."
234:
102:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
86:
70:
52:
386:
357:
341:
320:
169:
composites, including all sort of pseudoprimes. The probability distribution in question is
354:
Because I read ":1005" at the exponent. I suppose that it is the corruption of a reference.
276:
264:
Floor - 1 = number of odd integers <= n, excluding 1 (1 is neither prime nor composite)
423:
199:
399:
Thanks again. Excuse me, but I am too aged to remain updated with these conventions.
257:
composites because it's easy to determine whether or not an even number is prime.
379:
195:
99:
76:
325:
there should be a misprint soon after "21,853 pseudoprimes base 2". thanks.
408:
394:
370:
349:
334:
308:
284:
237:
210:
183:
290:
Seeing no comments, I put this into the first part of the article.
15:
270:
Floor - 1 - (PrimePi - 1) = number of odd composites <= n
295:
Johasouerp to coumiila Agreed banikcoumilla johasouerport
198:). I would, but I'm not sure how to reword everything.
98:, a collaborative effort to improve the coverage of
244:
Comparing pseudoprime counts with composite numbers
340:It looks right to me. What do you think is wrong?
132:This article has not yet received a rating on the
194:. Feel free to edit the article to fit (and also
220:Is definition of string pseudoprime correct ?
209:OK. I hope the wording is more clear now. --
8:
19:
267:PrimePi - 1 = number of odd primes <= n
47:
178:, and testing the input for being base-
49:
435:Unknown-priority mathematics articles
7:
92:This article is within the scope of
38:It is of interest to the following
14:
301:2400:C600:338A:90CB:1:0:4DE4:E106
112:Knowledge:WikiProject Mathematics
430:Start-Class mathematics articles
228:pseudoprime for that criterion.
115:Template:WikiProject Mathematics
79:
69:
51:
20:
375:It's a correct reference using
1:
409:07:30, 19 February 2024 (UTC)
395:00:07, 19 February 2024 (UTC)
371:23:27, 18 February 2024 (UTC)
350:21:39, 18 February 2024 (UTC)
335:20:09, 18 February 2024 (UTC)
106:and see a list of open tasks.
192:Miller-Rabin primality test
451:
285:21:06, 30 March 2017 (UTC)
238:12:16, 18 April 2007 (UTC)
299:Jouwelrana 0200019508794
260:In Mathematica notation,
186:09:56, 24 Aug 2004 (UTC)
131:
64:
46:
202:19:55, 2004 Aug 30 (UTC)
134:project's priority scale
309:18:38, 3 May 2023 (UTC)
213:15:19, 1 Sep 2004 (UTC)
190:I've added the link to
95:WikiProject Mathematics
28:This article is rated
118:mathematics articles
87:Mathematics portal
34:content assessment
314:probable misprint
148:
147:
144:
143:
140:
139:
442:
384:
378:
361:
324:
162:
161:
157:
120:
119:
116:
113:
110:
89:
84:
83:
73:
66:
65:
55:
48:
31:
25:
24:
16:
450:
449:
445:
444:
443:
441:
440:
439:
420:
419:
382:
376:
355:
318:
316:
297:
246:
222:
163:
159:
155:
153:
152:
117:
114:
111:
108:
107:
85:
78:
32:on Knowledge's
29:
12:
11:
5:
448:
446:
438:
437:
432:
422:
421:
418:
417:
416:
415:
414:
413:
412:
411:
315:
312:
296:
293:
292:
291:
272:
271:
268:
265:
245:
242:
221:
218:
217:
216:
215:
214:
204:
203:
151:
149:
146:
145:
142:
141:
138:
137:
130:
124:
123:
121:
104:the discussion
91:
90:
74:
62:
61:
56:
44:
43:
37:
26:
13:
10:
9:
6:
4:
3:
2:
447:
436:
433:
431:
428:
427:
425:
410:
406:
402:
401:151.29.149.29
398:
397:
396:
392:
388:
381:
374:
373:
372:
368:
364:
363:151.29.149.29
359:
353:
352:
351:
347:
343:
339:
338:
337:
336:
332:
328:
327:151.29.149.29
322:
313:
311:
310:
306:
302:
294:
289:
288:
287:
286:
282:
278:
269:
266:
263:
262:
261:
258:
256:
250:
243:
241:
239:
236:
232:
229:
225:
219:
212:
208:
207:
206:
205:
201:
197:
193:
189:
188:
187:
185:
182:pseudoprime.
181:
177:
172:
168:
158:
150:
135:
129:
126:
125:
122:
105:
101:
97:
96:
88:
82:
77:
75:
72:
68:
67:
63:
60:
57:
54:
50:
45:
41:
35:
27:
23:
18:
17:
317:
298:
273:
259:
254:
251:
247:
233:
230:
226:
223:
179:
175:
170:
166:
164:
93:
40:WikiProjects
387:PrimeHunter
358:PrimeHunter
342:PrimeHunter
321:PrimeHunter
196:pseudoprime
109:Mathematics
100:mathematics
59:Mathematics
30:Start-class
424:Categories
277:MathPerson
253:number of
240:jsryork
200:Elektron
235:Jsryork
154:": -->
36:scale.
405:talk
391:talk
367:talk
346:talk
331:talk
305:talk
281:talk
156:edit
255:odd
171:not
167:all
128:???
426::
407:)
393:)
383:}}
380:rp
377:{{
369:)
348:)
333:)
307:)
283:)
231:.
211:EJ
184:EJ
403:(
389:(
365:(
360::
356:@
344:(
329:(
323::
319:@
303:(
279:(
180:a
176:a
160:]
136:.
42::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
