How to print all expressions that match a regular expression

[hzhuo1 at gmail.com]

That is a method called brute force. According to my computation,
2^2048=
32317006071311007300714876688669951960444102669715484032130345427524655138867890
89319720141152291346368871796092189801949411955915049092109508815238644828312063
08773673009960917501977503896521067960576383840675682767922186426197561618380943
38476170470581645852036305042887575891541065808607552399123930385521914333389668
34242068497478656456949485617603532632205807780565933102619270846031415025859286
41771167259436037184618573575983511523016459044036976132332872312271256847108202
09725157101726931323469678542580656697935045997268352998638215525166389437335543
602135433229604645318478604952148193555853611059596230656L

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.

Sincerely,

Zhuo

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