Re: Factoring integers on a classical computer

cafeinst_at_msn.com
Date: 03/14/05 

Date: 14 Mar 2005 13:39:27 -0800

Alec McKenzie wrote:
> cafeinst@msn.com wrote:
>
> > I mean "If one can determine that a number is composite in
poly-time,
> > one should also be able to determine its factors in poly-time,
since
> > the factors are what determine whether the number is composite or
not."
> >
> > Can anyone present a convincing argument, through perhaps a
> > counterexample, that this way of thinking is misguided?
>
> You are incorrect in stating "the factors are what determine
> whether the number is composite or not."
>
> It is whether or not any factors exist that determines it, not
> what the values of any such factors might be.
>
> --
> Alec McKenzie
> mckenzie@despammed.com

Yes, but the factors of the number are what determine whether any
nontrivial factors of the number exist, which is what determines
whether the number is prime or composite. I feel like a lawyer :-)

Craig

Relevant Pages