RSA Weak?

[Robert J. Hansen]

Alexander W. Janssen wrote:
> A P-problem? Really?! Factoring primes is a polynomal problem nowadays?
> Are you SURE about that?

People who do not know what P stands for should not attempt to whap
other people around with it.

P is shorthand for deterministic polynomial time.  NP is
nondeterministic polynomial time.

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.

Nondeterministic polynomial time means it can be solved in polynomial
time by a nondeterministic Turing Machine--a machine that is capable of
making phenomenally lucky guesses.  Deterministic polynomial time means
it can be solved in polynomial time by a Turing Machine that cannot make
phenomenally lucky guesses.


... Incidentally, I'm assuming you meant 'factoring composites'.
Factoring prime numbers is most definitely in P.  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.