Re: Factoring integers on a classical computer

cafeinst_at_msn.com
Date: 03/14/05 

Date: 14 Mar 2005 13:23:18 -0800

Pubkeybreaker wrote:
> "Since PRIMES is in P, it would seem logical that FACTORING should
also
> be in P."
>
> Huh? Logical? By whose logic? Please explain this 'logic'.
>
>
>
> " Algorithms for determining whether a number is prime always
> work by indirectly or directly checking whether it has factors or
not"
>
> This is just a re-wording of the problem. A number is not prime if it
> has
> a prime factor less than itself. So what? How does this
demonstrate
> a
> relation between prime proving and factoring?
>
> " It would seem that there should be a way to fine-tune the poly-time
> AKS PRIMES algorithm"
>
> 'Seem"? Seem how? please explain your reasoning. It doesn't seem
so
> to
> me and I am an expert in this subject.
>
> Why do you think that AKS has anything to do with factoring? Explain
> your reasoning.

As I predicted, there would be some people who would strongly disagree.
All I was doing was stating an opinion that would seem to be correct
reasoning to an outsider. I never said it was correct reasoning nor do
I know whether it is correct.

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?

Craig

Relevant Pages

  • Re: Factoring integers on a classical computer
    ... If he had clearer reasoning, he'd probably be working on a factoring ... Find a factor of n in the interval [2, n-1]. ... AKS tells us that question 2 can indeed be answered efficiently in the ...
    (comp.theory)
  • Re: Factoring integers on a classical computer
    ... If he had clearer reasoning, he'd probably be working on a factoring ... Find a factor of n in the interval [2, n-1]. ... AKS tells us that question 2 can indeed be answered efficiently in the ...
    (sci.math)
  • Re: Factoring integers on a classical computer
    ... > "Since PRIMES is in P, it would seem logical that FACTORING should ... please explain your reasoning. ... I mean "If one can determine that a number is composite in poly-time, ...
    (comp.theory)
  • Re: I was right, surrogate factoring proof
    ... > factoring with a couple of quadratics and solutions for x and z, ... So there's one flaw in the reasoning. ... But, there's brute force, and there's analysis... ...
    (sci.math)
  • Re: why did you choose the programming language(s)you currently use?
    ... That's the factoring program (factor.exe from ... I don't know how to fix the bug nor how to bind ... The Python program, as it captures the StdOut, ... composite back to the beginning and start over. ...
    (comp.lang.python)