How to print all expressions that match a regular expression

Steve Holden steve at
Sun Feb 7 16:38:38 CET 2010

hzhuo1 at wrote:
>> And I really don't see how simple enumeration of range(2^2048) breaks
>> RSA-2048, since that problem requires you to find two factors which,
>> when multiplied together, give that specific value.
> I can tell you why is that. RSA-2048 has a composite of length less
> than 2^2048, which is a product of two large primes. So one of its
> factors cannot exceed 2^2047, and we can treat the multiplication as a
> computation with constant complexity. So the time complexity of
> enumerating 2^2048 strings is the same with factoring a composite with
> length 2^2048 which is the product of two primes.
> And obviously, whenever we successfully factor the composite, we can
> calculate the Euler function of it. So that given any public key
> (n,e), calculating the private key (n,d) is easy.
So all I have to do to break RSA is to count to 2^2048?

Steve Holden           +1 571 484 6266   +1 800 494 3119
PyCon is coming! Atlanta, Feb 2010
Holden Web LLC       

More information about the Python-list mailing list