368:
381:
374:
317:
211:
246:
457:
452:
418:
217:). This result shows that the generalized Riemann hypothesis implies tight bounds for the necessary run-time of the deterministic version of the
472:
467:
257:
164:
447:
477:
437:
411:
147:
47:
462:
139:
131:
100:
78:
218:
404:
158:
325:
124:
280:
222:
154:
442:
51:
225:
where previous work relied on heuristic estimates and empirical data. He is the namesake of
221:. Bach also did some of the first work on pinning down the actual expected run-time of the
8:
226:
299:
120:
339:
35:
392:
334:
289:
85:
68:
278:
Bach, Eric (1990), "Explicit bounds for primality testing and related problems",
388:
431:
367:
380:
104:
143:
90:
303:
251:
294:
146:. He is currently a professor at the Computer Science Department,
135:
373:
206:{\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}
213:
is generated by its elements smaller than 2(log
167:
387:This article about an American mathematician is a
205:
153:Among other work, he gave explicit bounds for the
429:
130:Bach completed his undergraduate studies at the
254:Theoretical Computer Science genealogy database
412:
419:
405:
453:UC Berkeley College of Engineering alumni
338:
318:"Toward a theory of Pollard's rho method"
293:
188:
175:
229:for generating random factored numbers.
458:University of Wisconsin–Madison faculty
430:
157:, which imply that if one assumes the
361:
315:
277:
142:, in 1984 under the supervision of
48:University of California - Berkeley
13:
140:University of California, Berkeley
14:
489:
132:University of Michigan, Ann Arbor
79:University of Wisconsin - Madison
473:21st-century American scientists
468:20th-century American scientists
379:
372:
366:
148:University of Wisconsin–Madison
309:
271:
239:
159:generalized Riemann hypothesis
123:who has made contributions to
1:
448:University of Michigan alumni
232:
138:in computer science from the
478:American mathematician stubs
438:American computer scientists
391:. You can help Knowledge by
340:10.1016/0890-5401(91)90001-i
7:
326:Information and Computation
219:Miller–Rabin primality test
125:computational number theory
16:American computer scientist
10:
494:
360:
281:Mathematics of Computation
155:Chebotarev density theorem
463:American number theorists
110:
96:
84:
74:
64:
57:
43:
28:
21:
207:
52:University of Michigan
208:
260:on November 27, 2005
165:
316:Bach, Eric (1991).
223:Pollard rho method
203:
121:computer scientist
400:
399:
114:
113:
97:Doctoral students
59:Scientific career
36:Chicago, Illinois
485:
421:
414:
407:
383:
378:
377:
376:
370:
362:
352:
351:
349:
347:
342:
322:
313:
307:
306:
297:
288:(191): 355–380,
275:
269:
268:
266:
265:
256:. Archived from
243:
227:Bach's algorithm
212:
210:
209:
204:
202:
201:
196:
192:
191:
183:
178:
86:Doctoral advisor
69:Computer Science
19:
18:
493:
492:
488:
487:
486:
484:
483:
482:
428:
427:
426:
425:
371:
365:
358:
356:
355:
345:
343:
320:
314:
310:
295:10.2307/2008811
276:
272:
263:
261:
245:
244:
240:
235:
197:
187:
179:
174:
173:
169:
168:
166:
163:
162:
119:is an American
103:
50:
44:Alma mater
39:
33:
24:
17:
12:
11:
5:
491:
481:
480:
475:
470:
465:
460:
455:
450:
445:
440:
424:
423:
416:
409:
401:
398:
397:
384:
354:
353:
333:(2): 139–155.
308:
270:
237:
236:
234:
231:
200:
195:
190:
186:
182:
177:
172:
134:, and got his
112:
111:
108:
107:
98:
94:
93:
88:
82:
81:
76:
72:
71:
66:
62:
61:
55:
54:
45:
41:
40:
34:
30:
26:
25:
22:
15:
9:
6:
4:
3:
2:
490:
479:
476:
474:
471:
469:
466:
464:
461:
459:
456:
454:
451:
449:
446:
444:
443:Living people
441:
439:
436:
435:
433:
422:
417:
415:
410:
408:
403:
402:
396:
394:
390:
385:
382:
375:
369:
364:
363:
359:
341:
336:
332:
328:
327:
319:
312:
305:
301:
296:
291:
287:
283:
282:
274:
259:
255:
253:
248:
242:
238:
230:
228:
224:
220:
216:
198:
193:
184:
180:
170:
160:
156:
151:
149:
145:
141:
137:
133:
128:
126:
122:
118:
109:
106:
102:
99:
95:
92:
89:
87:
83:
80:
77:
73:
70:
67:
63:
60:
56:
53:
49:
46:
42:
37:
31:
27:
20:
393:expanding it
386:
357:
344:. Retrieved
330:
324:
311:
285:
279:
273:
262:. Retrieved
258:the original
250:
241:
214:
152:
129:
116:
115:
105:Victor Shoup
101:John Watrous
75:Institutions
58:
247:"Eric Bach"
144:Manuel Blum
91:Manuel Blum
432:Categories
264:2008-06-04
252:ACM SIGACT
233:References
199:∗
117:Eric Bach
32:November,
23:Eric Bach
346:March 4,
304:2008811
302:
161:then
65:Fields
38:, U.S.
321:(PDF)
300:JSTOR
136:Ph.D.
389:stub
348:2015
29:Born
335:doi
290:doi
434::
331:90
329:.
323:.
298:,
286:55
284:,
249:.
150:.
127:.
420:e
413:t
406:v
395:.
350:.
337::
292::
267:.
215:n
194:)
189:Z
185:n
181:/
176:Z
171:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.