Re: Factoring integers on a classical computer

cafeinst_at_msn.com
Date: 03/16/05 

Date: 16 Mar 2005 07:26:31 -0800

*** T. Winter wrote:
> In article <1110905557.170005.112500@l41g2000cwc.googlegroups.com>
cafeinst@msn.com writes:
> ...
> > > "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."
> ...
> > Obviously, I don't possess your superior intellect, which is why I
am
> > asking you or any of the other wise men and women of usenet to
explain
> > the fallacy in my argument.
>
> The fallacy is pretty simple. There are properties that composite
numbers
> have that prime numbers do not have (and the converse), aside from
having
> some specific factors. One of those is Fermat's little theorem: if p
> is prime: a^p = a (mod p). If you can show that there is an a such
that
> a^p != a (mod p) you know that p is not prime, but you have no idea
what
> the factors may be. And there are more such properties that are used
in
> primality testing.
> --
> *** t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland,
+31205924131
> home: bovenover 215, 1025 jn amsterdam, nederland;
http://www.cwi.nl/~***/

Does everyone out there agree with ***?

Craig

Quantcast