Witam, istnieje jakaś funkcja która sprawnie w sposób losowy wyznaczy mi liczbę pierwszą o długości co najmniej 1000 bitów?
0
0
Wybierasz losową liczbę o długości co najmniej 1000 bitów, wykonujesz http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test, powtarzasz aż znajdziesz. To taki dość klasyczny sposób (ofc miller-rabina możesz zamienić na coś innego zawsze).
Jako że , (gdzie Pi(x) to ilość liczb pierwszych poniżej x), masz spore szanse że szybko trafisz na jakąś liczbę pierwszą.
Ściślej, jeśli wybierzesz liczbę pierwszą z przedziału (1, 21000), szansa na to że będzie pierwsza wynosi blisko = 0.00144269. Po wybraniu 2000 (zaszalejemy) takich liczb, szansa na to że żadna z nich nie będzie pierwsza, wynosi = około 0.055716, czyli 5%.