Re: Surrogate Factoring Theorem

jstevh_at_msn.com
Date: 04/05/05 

Date: 4 Apr 2005 16:32:23 -0700

Matt Gutting wrote:
> jstevh@msn.com wrote:

<deleted>

> > Consider, you have b_1 and b_2, where
> >
> > b_1 b_2 = M^2
> >
> > and the set of rational solutions for b_1 and b_2.
> >
> > Posters are basically arguing that given b_1 and b_2, such that
> >
> > b_1 b_2 = M^2
> >
> > over the rationals, that the size of M^2 will indicate the
probability
> > that b_1 or b_2 is a non-trivial factors of M^2, as in, the gcd of
the
> > numerator of b_1 or b_2 with M^2 is a non-trivial factor.
> >
> > Now it seems to me that without regard to the size of the factors
of
> > M^2, if you randomly pick factors b_1 and b_2 from the rationals,
you
> > will find you non-trivially factor M^2, at least 50% of the time.
> >
> >
> > James Harris
> >
>
> To quote the stereotypical math exam:
>
> Show your work.

Well, I've abstracted out the position of posters like yourself and
"Nora Baron", as you can, instead, consider the position that given a
rational

b_2

where b_1 b_2 = M^2

and M is a natural number that is the product of two primes p_1 and
p_2, b_1 or b_2 if randomly selected will give a non-trivial factor a
percentage of the time that depends on the size of p_1 and p_2.

That is, stepping away from the theorem itself, I can consider the
position you and other posters have taken by considering that position
in and of itself.

My own counter to you, or "Nora Baron" might be, prove your assertions
here.

I say that b_1 and b_2 will, if randomly selected such that you are
certain to have factors of M^2, give a non-trivial factorization at
least 50% of the time.

At issue here is how you select, as I think some of you believe you can
just randomly select some number for b_1--without regard to it being a
factor of M^2.

That is, given the task of selecting a rational b_2, where b_1 b_2 =
M^2, you seem to think that means, pick a rational, any rational.

Yes, there are an infinity of rationals that are coprime to M, but
there are an infinity that are not.

You pick one infinity, without giving a proof, when you have social
reasons for wanting one infinity over others.

I say there are 4 basic infinite sets:

1. One with M as a factor.
2. One with p_2 as a factor, coprime to p_1.
3. One with p_1 as a factor, coprime to p_2.

Oh, there are three.

Now for each of those possibilities, you have an infinite set of
numbers.

How do you choose which set?

James Harris

Relevant Pages

  • Re: infinitely many nns = infinite nns?
    ... There are never two or more reals "in ... I meant that there must be a sequence of irrationals -- without ... Let a, b, c and d be naturals such that a/b < c/d as rationals, then ... point out that this proof uses the assumptions of potential infinity, ...
    (sci.logic)
  • Re: Cantor and the binary tree
    ... According to Cantor ... > well-ordered and simultaneously ordered set < of all rationals, ... What you are doing is defining some sort of sequence of infinite sets. ... carried away and use sloppy wordings like 'at infinity' or 'after ...
    (sci.math)
  • Re: Side channels in theorems
    ... So why would doing these 4 operations an infinity ... the rationals are. ... If the assumption leads to a contradiction, then the assumption must be wrong, namely that I can order and enumerate all reals. ... "there is an algorithm that allows me to compute every digit" or, equivalently "as precise as I wish". ...
    (comp.compression)
  • Re: Side channels in theorems
    ... So why would doing these 4 operations an infinity ... rationals, just as happy for the reals. ... I have an algorithm that given n gives you the ...
    (comp.compression)
  • Re: Cantor Confusion
    ... the corresponding distinction between rationals and reals is ... Perhaps it is most helpful to declare the reals just ... Infinity is in some sense the opposite of being infinite. ... The very nil between 0+ and 0-. ...
    (sci.math)