707:
41:
in 1988. No algorithm is known that efficiently factors random numbers, so the straightforward method, namely generating a random number and then factoring it, is impractical.
323:
167:
88:
263:
364:
420:
447:
507:
487:
467:
384:
283:
230:
210:
187:
127:
781:
752:
776:
771:
667:
694:
745:
693:, MIT Press, 1984. Chapter 2, "Generation of Random Factorizations", part of which is available online
538:
288:
132:
51:
30:
738:
235:
328:
655:
389:
579:
726:
602:
559:
425:
8:
265:, according to a certain distribution. The algorithm then recursively generates a number
606:
510:
492:
472:
452:
369:
268:
215:
195:
172:
112:
663:
91:
610:
588:
547:
598:
555:
45:
23:
722:
718:
98:
593:
574:
765:
628:(Version 2 ed.). Cambridge, UK: Cambridge University Press. p. 305.
34:
190:
691:
Analytic methods in the
Analysis and Design of Number-Theoretic Algorithms
48:. A simpler, but less efficient algorithm (performing, in expectation,
714:
686:
533:
38:
26:
551:
16:
Algorithm for generating random numbers with their factorization
706:
97:
Bach's algorithm may be used as part of certain methods for
189:), along with its factorization. It does this by picking a
641:
626:
660:
Prime
Suspects: The Anatomy of Integers and Permutations
509:
with logarithmic distribution over the desired range;
643:(3rd ed.). Berlin: Springer Verlag. p. 226.
495:
475:
455:
428:
392:
372:
331:
291:
271:
238:
218:
198:
175:
135:
115:
54:
656:"Constructing integers with the probabilistic model"
536:(1988). "How to generate factored random numbers".
653:
501:
481:
461:
441:
414:
378:
358:
317:
277:
257:
224:
204:
181:
161:
121:
82:
44:The algorithm performs, in expectation, O(log n)
763:
662:. Princeton University Press. pp. 207–208.
654:Granville, Andrew; Granville, Jennifer (2019).
746:
575:"Generating random factored numbers, easily"
513:is then used to get a uniform distribution.
753:
739:
638:
592:
764:
528:
526:
623:
572:
782:Algorithms and data structures stubs
701:
532:
639:Delfs, Hans; Knebl, Helmut (2015).
523:
109:Bach's algorithm produces a number
13:
680:
366:, along with the factorization of
14:
793:
129:uniformly at random in the range
705:
469:to produce the factorization of
647:
632:
617:
566:
318:{\displaystyle M/2<y\leq M}
162:{\displaystyle N/2<x\leq N}
77:
58:
1:
516:
83:{\displaystyle O(\log ^{2}n)}
725:. You can help Knowledge by
90:primality tests), is due to
7:
258:{\displaystyle p^{a}\leq N}
104:
10:
798:
700:
594:10.1007/s00145-003-0051-5
539:SIAM Journal on Computing
359:{\displaystyle M=N/p^{a}}
31:generating random numbers
777:Random number generation
772:Cryptographic algorithms
449:to the factorization of
415:{\displaystyle x=p^{a}y}
721:-related article is a
624:Shoup, Victor (2008).
503:
483:
463:
443:
416:
380:
360:
319:
279:
259:
226:
206:
183:
163:
123:
84:
37:. It was published by
580:Journal of Cryptology
504:
484:
464:
444:
442:{\displaystyle p^{a}}
417:
381:
361:
320:
280:
260:
227:
207:
184:
164:
124:
85:
573:Kalai, Adam (2003).
493:
473:
453:
426:
390:
370:
329:
289:
269:
236:
216:
196:
173:
133:
113:
52:
169:(for a given input
22:is a probabilistic
511:rejection sampling
499:
479:
459:
439:
412:
376:
356:
315:
275:
255:
222:
202:
179:
159:
119:
80:
734:
733:
502:{\displaystyle x}
482:{\displaystyle x}
462:{\displaystyle y}
379:{\displaystyle y}
278:{\displaystyle y}
225:{\displaystyle a}
205:{\displaystyle p}
182:{\displaystyle N}
122:{\displaystyle x}
101:in cryptography.
33:along with their
789:
755:
748:
741:
709:
702:
674:
673:
651:
645:
644:
636:
630:
629:
621:
615:
614:
596:
570:
564:
563:
530:
508:
506:
505:
500:
488:
486:
485:
480:
468:
466:
465:
460:
448:
446:
445:
440:
438:
437:
421:
419:
418:
413:
408:
407:
385:
383:
382:
377:
365:
363:
362:
357:
355:
354:
345:
324:
322:
321:
316:
299:
284:
282:
281:
276:
264:
262:
261:
256:
248:
247:
231:
229:
228:
223:
212:and an exponent
211:
209:
208:
203:
188:
186:
185:
180:
168:
166:
165:
160:
143:
128:
126:
125:
120:
89:
87:
86:
81:
70:
69:
20:Bach's algorithm
797:
796:
792:
791:
790:
788:
787:
786:
762:
761:
760:
759:
719:data structures
683:
681:Further reading
678:
677:
670:
652:
648:
637:
633:
622:
618:
571:
567:
552:10.1137/0217012
531:
524:
519:
494:
491:
490:
474:
471:
470:
454:
451:
450:
433:
429:
427:
424:
423:
403:
399:
391:
388:
387:
386:. It then sets
371:
368:
367:
350:
346:
341:
330:
327:
326:
295:
290:
287:
286:
270:
267:
266:
243:
239:
237:
234:
233:
217:
214:
213:
197:
194:
193:
174:
171:
170:
139:
134:
131:
130:
114:
111:
110:
107:
65:
61:
53:
50:
49:
46:primality tests
24:polynomial time
17:
12:
11:
5:
795:
785:
784:
779:
774:
758:
757:
750:
743:
735:
732:
731:
710:
699:
698:
682:
679:
676:
675:
668:
646:
631:
616:
587:(4): 287–289.
565:
546:(2): 179–193.
521:
520:
518:
515:
498:
478:
458:
436:
432:
422:, and appends
411:
406:
402:
398:
395:
375:
353:
349:
344:
340:
337:
334:
314:
311:
308:
305:
302:
298:
294:
274:
254:
251:
246:
242:
221:
201:
178:
158:
155:
152:
149:
146:
142:
138:
118:
106:
103:
99:key generation
79:
76:
73:
68:
64:
60:
57:
35:factorizations
15:
9:
6:
4:
3:
2:
794:
783:
780:
778:
775:
773:
770:
769:
767:
756:
751:
749:
744:
742:
737:
736:
730:
728:
724:
720:
716:
711:
708:
704:
703:
696:
692:
688:
685:
684:
671:
669:9780691188737
665:
661:
657:
650:
642:
635:
627:
620:
612:
608:
604:
600:
595:
590:
586:
582:
581:
576:
569:
561:
557:
553:
549:
545:
541:
540:
535:
529:
527:
522:
514:
512:
496:
489:. This gives
476:
456:
434:
430:
409:
404:
400:
396:
393:
373:
351:
347:
342:
338:
335:
332:
312:
309:
306:
303:
300:
296:
292:
285:in the range
272:
252:
249:
244:
240:
219:
199:
192:
176:
156:
153:
150:
147:
144:
140:
136:
116:
102:
100:
95:
93:
74:
71:
66:
62:
55:
47:
42:
40:
36:
32:
28:
25:
21:
727:expanding it
712:
690:
659:
649:
640:
634:
625:
619:
584:
578:
568:
543:
537:
191:prime number
108:
96:
43:
19:
18:
766:Categories
715:algorithms
687:Bach, Eric
534:Bach, Eric
517:References
232:such that
92:Adam Kalai
310:≤
250:≤
154:≤
72:
39:Eric Bach
27:algorithm
611:17271671
325:, where
105:Overview
603:2002046
560:0935336
666:
609:
601:
558:
713:This
607:S2CID
723:stub
695:here
664:ISBN
304:<
148:<
29:for
717:or
589:doi
548:doi
63:log
768::
689:.
658:.
605:.
599:MR
597:.
585:16
583:.
577:.
556:MR
554:.
544:17
542:.
525:^
94:.
754:e
747:t
740:v
729:.
697:.
672:.
613:.
591::
562:.
550::
497:x
477:x
457:y
435:a
431:p
410:y
405:a
401:p
397:=
394:x
374:y
352:a
348:p
343:/
339:N
336:=
333:M
313:M
307:y
301:2
297:/
293:M
273:y
253:N
245:a
241:p
220:a
200:p
177:N
157:N
151:x
145:2
141:/
137:N
117:x
78:)
75:n
67:2
59:(
56:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.