Re: Factoring integers on a classical computer

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 03/18/05 

Date: 18 Mar 2005 11:13:54 -0800

cafeinst@msn.com wrote:
> 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

Thinking about this more, Alec is correct. Existence of nontrivial
factors alone determines whether a number is prime. My comments were
just a result of wishful thinking :-)

Craig

Relevant Pages