RSA Weak?

[Alexander W. Janssen]

On 11/2/07, Robert J. Hansen <rjh at sixdemonbag.org> wrote:
> Alexander W. Janssen wrote:
> > A P-problem? Really?! Factoring primes is a polynomal problem nowadays?
> > Are you SURE about that?
>
> Factoring is known to be in NP.  Therefore, it is perfectly fair to say
> that it's a polynomial problem, as long as Sven is not claiming that
> it's deterministic polynomial, which he isn't.

We already sorted that out in that other posting.

> ... Incidentally, I'm assuming you meant 'factoring composites'.

That's what I meant initially.

> Factoring prime numbers is most definitely in P.

Hold on. Earlier you say "Factoring is known to be in NP". P is much
smaller. I'm not familiar to the latest outcomes. So what do you mean?

> It's also in NC and
> Context-Free, but probably not Regular; you need a pushdown automata to
> parse the number as you read it, which means a context-free language is
> required.

OK, there you got me. I only know the term context-free from languages.

Alex.


--
"I am tired of all this sort of thing called science here... We have spent
millions in that sort of thing for the last few years, and it is time it
should be stopped."
 -- Simon Cameron, U.S. Senator, on the Smithsonian Institution, 1901.


.


-- 
"I am tired of all this sort of thing called science here... We have spent
millions in that sort of thing for the last few years, and it is time it
should be stopped."
 -- Simon Cameron, U.S. Senator, on the Smithsonian Institution, 1901.


.