Re: Surrogate factoring, top to bottom
- From: sg552@xxxxxxxxxxxxx
- Date: 27 Mar 2007 10:49:36 -0700
James Harris wrote:
The best way to understand surrogate factoring may be to to start with
x^2 = y^2 mod T
where T is the target composite to be factored, so you just have the
familiar congruence of squares, also called the difference of squares,
where you MAY factor T non-trivially by checking for prime factors in
common between it and x-y or x+y.
Now for some solution set {x,y} let
k = 2x mod T
so
2x = k mod T, and you can multiply both sides by k, to get
2xk = k^2 mod T
and now you can add back to the original congruence of squares to get
x^2 + 2xk = y^2 + k^2 mod T
and, of course, you can complete the square and simplify to get
(x+k)^2 = y^2 + 2k^2 mod T
and that gives you most of surrogate factoring as you now know that
for ANY solutions with a difference of squares you have a solution to
that congruence.
So, trivially, every factorization of any given target composite T is
connected to a factorization of some other composite, as of course,
looking explicitly--introducing the integer omega--I have
(x+k)^2 = y^2 + 2k^2 + omega*T
and y is determined by the factorization of 2k^2 + omega*T, with
again, trivial algebra.
Note then that y is determined by two factorizations as also with the
original difference of squares, again going explicit, this time using
alpha, I have
x^2 = y^2 + alpha*T
and here y is defined by a factorization of T, and SIMULTANEOUSLY y is
defined by the factorization of omega*T, which means that at a very
fundamental level, factorizations of numbers are bound by some very
basic congruence relationships.
So it becomes a simple step to ask, what if I start with k, can I
factor T from the surrogate factorization of 2k^2 + omega*T?
And the answer is, yes, you can.
In terms of actually trying to factor, you have to pick k, which
forces the residue modulo T of x, and you also have to pick omega, and
that is it.
You can only pick k and omega.
This is all well and good, but I can't see why this method is supposed
to be an improvement on that of Fermat's. Can you (or anyone else)
explain why you would expect to be able to factor a large number
faster with this method? I have never seen you present any kind of
analysis of how the expected number of trials increases with T. In
another recent thread you claimed that the theory says that your
method should be able to factor an RSA-sized composite in under 10
minutes on a desktop. How exactly does the theory say this?
And you know that for any x you can pick there is a k and omega that
have to work, but maybe the two don't match well somehow? Maybe your
pick of k and omega on your end is unlikely to find a welcoming x and
y on the other?
Well, good questions, and shouldn't there be answers? Shouldn't there
be some mathematics that would tell you if that were true?
I've checked. It's trivial algebra, and the mathematics does not say
that at all.
It says that for a given k and omega, outside of a narrow size range
where k is too small and the surrogate is too small to give factors,
you have a 50% chance of factoring T, with SOME combination of factors
of the surrogate 2k^2 + omega*T.
(If I am wrong, it'd be nice for someone to post a nice analysis of
the very trivial algebra that DOES show that it's hard to pick k and
omega.)
You seem to be under the impression that "I can't find a reason why
statement A is true" constitutes a proof that statement A is untrue.
It doesn't. I can't see why the Goldbach conjecture should be true,
but that doesn't mean it isn't.
So then if this idea might be worth something, why wouldn't it be a
big deal by now?
Well you have to factor SOMETHING. If you can't factor that well,
then you can't use surrogate factoring as you still need to factor
2k^2 + omega*T, and that's why this method could be a stealth one that
takes the world by surprise because to check it against really big
numbers, you need to be able to factor some really big numbers.
Easy math then that says that you can factor one number through
another, and on the "pure math" side, easy proof of a connection
between composites where otherwise it might not be clear that a
connection existed.
For the "pure math" fun of it, what if you play around with the
equations? Can you find more congruence relations?
Well, I've done that and you can do some other stuff, but it doesn't
seem to change much, like you can have
ak = 2x mod T
and get to
(x+k)^2 = y^2 + (a+1)k^2 mod T
which is a variable I like enough to add to my own main research page
on the subject, but that doesn't change much...hmmm...what about
something like
k^2 = 3xk mod T?
Well, that can be shown to be equivalent to what I already have (do
the math for yourself if you wish).
Ok then, what about something like
k^2 = 2xk + 3 mod T
or something else of that nature?
Well, that isn't always true, as it's not necessarily the case that
you have a solution for k, so I haven't played with anything like
that, and if you just go all out to add another variable, something
weird happens, like with
k^2 = 2xk + z mod T
you completely de-couple T from the equations anyway and it behaves
like random.
What do you mean "it behaves like random"? WHAT behaves like random?
Please be precise.
It's like some kind of quantum mechanics thing, where if you add
another variable, you blow up surrogate factoring as the mathematics
kind of throws up its hands and asks, how do I know what T is now?
You know, it's like you collapse the wave function or something, and
it doesn't work any more.
What does all this actually mean?
That is freaky if you see it, so I suggest you play with these
equations.
The other way to de-couple T, is, of course, to have k = 0, or have
omega = 0, as then you just get random.
Just get random what?
So yes, the mathematics here may relate back to how our very reality
works,
WHOAH THERE! How exactly may the mathematics here relate back to how
our reality works? All you've done is claim that something (you
haven't told us what) is random, and now we are expected to believe
that this could have something to do with QM? The arrangement of
crumbs of ash surrounding the ashtray next to me looks pretty random.
Perhaps they hold the secret to solving the measurement problem! Why
should people take your proposal any more seriously than mine? If you
have a quantitative theory which can make testable predictions about
how our world works, that might be worth people's time. But you don't.
By the way, do you still think that p mod 3 can be used to explain the
two-slit experiment?
You think they give a damn if somehow composites and factorizations
could be related to physics?
No more than they give a damn about the aforementioned ashtray, until
you give them a reason to.
If you were a Ph.D in mathematics with decades of living rather well,
would you really accept having to go find a new job, maybe working at
McDonald's or whatever you could get just to tell the truth about some
basic mathematics?
You seem to have a very warped idea of the kind of life that academics
lead. With my qualifications I could have become an accountant or
investment banker but instead I'm doing a physics PhD earning a
fraction of what most of my friends earn. Why do you think
mathematicians become mathematicians in the first place? I can assure
you it isn't for the standards of living.
-Rotwang
.
- References:
- Surrogate factoring, top to bottom
- From: jstevh
- Surrogate factoring, top to bottom
- Prev by Date: Re: World is complicated
- Next by Date: Re: Pentanomial better than trinomial
- Previous by thread: Re: Surrogate factoring, top to bottom
- Next by thread: Re: Surrogate factoring, top to bottom
- Index(es):
Relevant Pages
|
|
