OurBigBook
About
$
Donate
Sign in
+
Sign up
Ciro Santilli
@cirosantilli
36
Follow (9)
Message
Incoming links:
Primality test
Show body
Body
0
How large primes are found for RSA
Updated
2025-05-07
+
Created
1970-01-01
View more
crypto.stackexchange.com/questions/1970/how-are-primes-generated-for-rsa
crypto.stackexchange.com/questions/690/can-i-select-a-large-random-prime-using-this-procedure/693#693
Answers suggest hat you basically pick
a
random large odd
number
, and add
2
to it until your selected
primality test
passes.
The
prime number theorem
tells us that the
probability
that
a
number
between
1
and
N
is
a
prime number
is
1/
l
o
g
(
N
)
.
Therefore, for an
N
-
bit
integer
,
we
only have to run the
test
N
times
on
average
to find
a
prime.
Since say,
A
512-
bit
integer
is already humongous and sufficiently large,
we
would only need to search 512
times
on
average
even for such
sizes
, and therefore the procedure scales well.
Total
articles
:
1