How to print all expressions that match a regular expression

hzhuo1 at hzhuo1 at
Sun Feb 7 22:57:14 CET 2010

That is a method called brute force. According to my computation,

which is a very large number.

There are some other algorithms for factoring integers, including
Generalized number field sieve. And in quantum computing, there is an
algorithm called Shor, which is claimed to be a polynomial algorithm
if run under quantum computers. But seems that kind of computers
haven't been successfully built, or else RSA and many other security
mechanisms based on computation complexity cannot be used any longer.

What I need in my application is just to list all expressions that
match a particular regex, which I believe will be more efficient to
deal with if there is a general function for this purpose.
Unfortunately there is not such a function, so I will write my own
function to deal with my particular regex, which can be enumerated.



On Feb 7, 10:38 am, Steve Holden <st... at> wrote:
> hzh... 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?
> regards
>  Steve
> --
> 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