Re: [Newbie] Prime factorization question

From: Fernando (ferrub09_at_telefonica.net)
Date: 10/07/03 

Date: Tue, 7 Oct 2003 17:46:34 +0200

Hi
The number of primes < x is greater than x/L(x)
so if x is n bits long the number of primes must be about

2^n/L(2^n) - ( (2^(n-1))/(L(n-1))

Regards
Fernando
"Mxsmanic" <mxsmanic@hotmail.com> wrote in message
news:3al5ovsfu24e5ire5brhsge55u4rn5cq89@4ax.com...
> Lorenzo Bolognini writes:
>
> > So they are known and sure they are prooven and certificated primes
> > (otherwise the cipher would be vulnerable to other attacks than plain
> > bruteforcing) and they are finite so the number of possible primes that
may
> > generate the cipher is very much restricted...
>
> PGP selects prime numbers at random from the set of all prime numbers
> with appropriate lengths (n/2, where n is the desired length of the
> modulus). The number of primes at any given length is indeed finite,
> but it is very, very large for any modulus of the common sizes used in
> PGP (384 bits and up), and so there is no real risk of the same primes
> being selected for two different keys.
>
> The primality of the selected random numbers is not conclusively
> verified, but it is tested with an algorithm that provides a very high
> degree of certainty with respect to their primality (additionally, if p
> and q are not both prime, typically the encryption will fail in a fairly
> obvious way quite quickly).
>
> > well how many are they?
>
> For a 1024-bit modulus, you need two 512-bit primes. If I remember
> correctly, there are probably about 4 x 10^151 primes of that length or
> less. So even with a 1024-bit modulus, we will never run out of unique
> primes, and the possibility of getting two identical primes is, for all
> practical purposes, zero.
>
> I do wonder how many primes there are of _exactly_ n bits, but I'm not
> sure how to calculate or estimate that. Also, it's important that the
> primes be selected entirely at random.
>
> --
> Transpose hotmail and mxsmanic in my e-mail address to reach me directly.

Relevant Pages

  • Re: [Newbie] Prime factorization question
    ... Should I interpret this to mean that the decision to develop the modulus ... that is the product of something other than exactly two primes) ... and with far greater susceptibility to cracking through factorization. ... RSA is not completely sound, because it can still fail if one of the ...
    (sci.crypt)
  • Re: special DH prime
    ... represent the modulus as a polynomial with *much smaller* coefficients ... Primes with low Hamming weight are, on average, easier than general ... algorithms will react on special form moduli, ... than modular integers (otherwise I would have gone for elliptic curves) ...
    (sci.crypt)
  • Re: RSA moduli sizes
    ... bit RSA modulus be 1 we are effectively turning it into an -bit ... Since the best known factoring ... The sentence about "forcing the complexity as high ... two primes, uniformly at random, from a specified interval. ...
    (sci.crypt)
  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... the product is indeed, say, 512 bits, for a 512-bit modulus. ... an N bits long product of two primes doesn't really contain N ... slightly more than 502.5 bits of entropy, so a 1024 bits long RSA ... the sieve of Eratosthenes or the sieve of Atkin. ...
    (sci.crypt)
  • Re: [Newbie] Prime factorization question
    ... > generate the cipher is very much restricted... ... The number of primes at any given length is indeed finite, ... very large for any modulus of the common sizes used in ... The primality of the selected random numbers is not conclusively ...
    (sci.crypt)
Quantcast