# How to print all expressions that match a regular expression

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

```hzhuo1 at gmail.com 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?

regards
Steve
--
Steve Holden           +1 571 484 6266   +1 800 494 3119
PyCon is coming! Atlanta, Feb 2010  http://us.pycon.org/
Holden Web LLC                 http://www.holdenweb.com/
UPCOMING EVENTS:        http://holdenweb.eventbrite.com/

```