SF: Infinity proof

jstevh_at_msn.com
Date: 04/17/05 

Date: 17 Apr 2005 10:47:40 -0700

The surrogate factoring theorem works over rationals, and from
discussions I've seen on Usenet in response to my posts on SFT, it
seems there's a good bit of confusion possible when it comes to
understanding factoring in rationals.

The set of rational is infinite, and because every member except 0 is a
factor of every other member, math students get taught that
factorizations in rationals are trivial.

But if you have

a_1 a_2 = N

where a_1 and a_2 are rationals, and N is a composite, and further

a_1 = x/y

where x and y are coprime non-zero integers, then you can check the gcd
of x or y with N to see if you have a non-trivial factor of N.

So the factorization, while in rationals, can still be considered
non-trivial, if you do get a non-trivial factor from x or y.

So how many of the factors of N in the set of rationals are
non-trivial?

Well that's easy--an infinite number of them are.

But as a percentage, how many of them are trivial?

Well, for every trivial factor, you can multiply it by a prime factor
of N and get a non-trivial factor.

For instance, if N is coprime to 2 and 3, then x = 2, y = 3, gives 2/3,
a trivial factor of N. But if N has p_1 as a factor, then multiplying
x by p_1, gives a non-trivial factor as then you have 2p_1/3.

So for every trivial solution in that infinity you have a non-trivial
solution found by multiplying by a single prime factor.

So, as a percentage, at most 50% of the solutions are trivial for the
composite N.

Understanding that is key to understanding the importance of the SFT.

James Harris

Relevant Pages

  • Re: SF: Areas of confusion, infinity
    ... > notably the set of rationals. ... choosing any integer is the same as the probability of any other ... That's what make the factoring problem interesting, i.e., not ... > is naive with the surrogate factoring theorem. ...
    (sci.crypt)
  • Re: surrogate factoring
    ... quality "SF time" than anyone other than James ... ... "surrogate factoring" doesn't really mean anything specific. ... since the set of all non-zero rationals constituted the search space ... pushing formulas around, and it may be a bona fide compulsion for him. ...
    (sci.math)
  • Re: surrogate factoring
    ... quality "SF time" than anyone other than James ... ... "surrogate factoring" doesn't really mean anything specific. ... since the set of all non-zero rationals constituted the search space ...
    (sci.math)
  • Re: JSH: Moving through it
    ... There are lots of good factoring methods that have problems with two ... Remember, x and y are rationals, so they can be fractions, and I've ... The solution is that for a given rational x the probability that it ... The mathematics proving every statement in this post is already worked ...
    (sci.math)
  • Re: Easy test of surrogate factoring
    ... Wondering whether a new and earthshattering factoring method ... can be used to factor numbers is not a fair test? ... >That proves that there are rules governing the value of the rationals ... >But mathematicians are NOT what they claim, and in this case they are ...
    (sci.math)
Quantcast