Factoring's back door
JSH
the problem directly, but by instead taking a back door approach,
where you start with two important relations:
z^2 = y^2 + T
and
x^2 = y^2 mod p
where T is the target composite to be factored and p is an odd prime
to be determined, where notice that for a non-trivial factorization,
there are an infinity of values for x, so at first blush this approach
may seem naive, until you start whittling that infinity down.
The most clever approach I've found is to use k=2ax mod p, as the two
new variables allow me to find that:
x^2 = y^2 + T - (1 + a^2)k^2 mod p
and now I have a way to narrow that infinity down!!! As let T -
(1+a^2)k^2 = 0 mod p, and I have a smaller set of solutions, and even
can have cases where no solutions exist, as:
k^2 = (1+a^2)^{-1}(T) mod p
so if (1+a^2)^{-1}(T) is not a quadratic residue modulo p, there is no
integer k.
Remarkably enough I can now actually solve for z and y mod p:
z = (2a)^{-1}(1 + 2a^2)k mod p
and
y = (2a)^{-1}k mod p
So when does all that work? Well, remember that there are an INFINITY
of solutions for x at first, but I narrowed that down with:
T - (1+a^2)k^2 = 0 mod
So if THAT relation holds then presumably you should have solutions,
EXCEPT notice that with the solutions for z and y, the variable k is
in both, and it can occur that k is a factor in both--which is a block
unless T has k as a factor!!! The situation is actually even more
complicated as with z and y, you can get solutions for factors f_1 and
f_2 where f_1*f_2 = T:
f_1 = ak mod p
and
f_2 = a^{-1}(1 + a^2)k mod p
and again k provides a possible block, as for instance with a=1, if k
is less than p, and z is less than p, then those relations would
require that f_1 and z have the same factor, which would force it into
f_2, and into T, as:
z = (f_1 + f_2)/2
And similar problems happen with y, as y = (f_1 - f_2)/2, and I call
the first situation the z constraint, while the second is the y
constraint.
But if none of the 4 constraining equations, the z, y, f_1 and f_2
equations give a conflict, and T - (1+a^2)k^2 = 0 mod p, then this
approach MUST give solutions.
But then, how do you use it?
Here's a quick example of a factorization using all of the machinery
above:
Let T=341. Then p=17 is the greatest prime less than sqrt(341) and
starting with a=1, gives
k^2 = (2)^{-1}(341) mod 17 = 9(1) mod 17 = 9 mod 17.
so it does exist and k=3 or k=14 are possible, but with the first f_1
= ak = 3 is not a factor and 14 is not either.
So next check f_2, f_2 = a^{-1}(1 + a^2)k = 2(3) = 6 which is not a
factor but 17-6=11, and 11 is a factor. Success!
And you have a non-trivial factorization, as 341 = 11(31).
Notice that z=(11+31)/2 = 21, so no conflict, y = (31-11)/2 = 10, so
no conflict.
And the equations escape conflict with the f's by going to the
negative residues, so checking p - f_1 and p - f_2 is a necessity.
So there HAD to be a solution in this case. So once k existed,
without conflict from any of the 4 constraints, a factorization had to
be found.
The method represents a back door into factoring which allows you to
leverage an infinity to factor a composite. Your factoring engine is
infinity itself. And infinity is a powerful tool!!!
You can scan through p's to find a large one, though notice you can't
just pick too huge a p, as then you're likely to get a conflict with
one of the 4 constraints, and you can choose the variable 'a' to try
and adjust around the constraints as well, as notice if a=1, like with
my example and k is even, then with:
y = (2a)^{-1}k mod p, you have y = k/2 mod p, so if k is close to p,
so k/2 < p, then you conflict with f_1 = ak = k, with a=1
So when k is even you already know that a=1 will probably not work
well, but then you can use a=2, or a=3, or a=6, or some other.
So what is the Big O time complexity of this approach?
It cannot be calculated, as if none of the 4 constraints conflict, and
k exists it is 100% success rate, but if one of the constraints blocks
it just doesn't work. AND you have to solve for k, so finding a
quadratic residue is important!
But some of you may know this approach leads to a method for solving
quadratic residues as well, simply by reversing it, as importantly you
have:
k^2 = (1+a^2)^{-1}(T) mod p and z = (2a)^{-1}(1 + 2a^2)k mod p
but z = (f_1 + f_2)/2, so you have
f_1 + f_2 = (a)^{-1}(1 + 2a^2)k mod p
So if you have a quadratic residue q, you can just let T = (1+a^2)q
mod p, and factor T, to get f_1 and f_2, which gives you k, from:
k = a(1 + 2a^2)^{-1}(f_1 + f_2) mod p
So you can use this approach in the opposite direction to solve for
quadratic residues! And again, if none of the 4 constraints block it
MUST work. It must work. Perfection.
How do you know? Because given an integer y, x^2 = y^2 mod p has an
INFINITY of solutions. I narrowed that infinity down with the
critical relation:
T - (1+a^2)k^2 = 0 mod p
Trying to factor T, you have to find a p for which k exists, but going
the other way to find a quadratic residues you BUILD T, so you know k
exists if q is a quadratic residue modulo p, so if none of the 4
constraints are in the way, there is no way for a subset of that
infinity not to work. Infinity has no choice, it has to solve the
quadratic residue for you then.
So you have mathematically knowledge of a perfect method for factoring
and for finding quadratic residues which reveals itself by going at
factoring indirectly.
It is a perfect method.
James Harris
Enrico
=======================================================
Far as I can see, it should work fine for factors, and quadratic
residues.
Try it on T with slightly bigger prime factors, spaced farther apart.
See if you can find any trends, or links to the forms of one or both
of the factors. I've seen stuff about dependecies on factors of the
forms 8N+1, 8N+3, 8N+5, and 8N+7.
You should be able to get a rough idea of the Big O time complexity.
Enrico
rossum
wrote:
>Oddly enough a simple approach to factoring comes from not attacking
>the problem directly, but by instead taking a back door approach,
>where you start with two important relations:
>
>z^2 = y^2 + T
Am I correct to assume that z and x are both positive integers?
>
>and
>
>x^2 = y^2 mod p
>
>where T is the target composite to be factored and p is an odd prime
>to be determined,
I will return to how to determine p below.
>where notice that for a non-trivial factorization,
>there are an infinity of values for x, so at first blush this approach
>may seem naive, until you start whittling that infinity down.
>
>The most clever approach I've found is to use k=2ax mod p, as the two
>new variables allow me to find that:
Am I correct to assume that these two new variables, k and a are both
positive integers?
>
>x^2 = y^2 + T - (1 + a^2)k^2 mod p
>
>and now I have a way to narrow that infinity down!!! As let T -
>(1+a^2)k^2 = 0 mod p, and I have a smaller set of solutions, and even
>can have cases where no solutions exist, as:
>
>k^2 = (1+a^2)^{-1}(T) mod p
>
>so if (1+a^2)^{-1}(T) is not a quadratic residue modulo p, there is no
>integer k.
>
>Remarkably enough I can now actually solve for z and y mod p:
>
>z = (2a)^{-1}(1 + 2a^2)k mod p
>
>and
>
>y = (2a)^{-1}k mod p
>
>So when does all that work? Well, remember that there are an INFINITY
>of solutions for x at first, but I narrowed that down with:
>
>T - (1+a^2)k^2 = 0 mod
I assume that should have been "mod p".
>
>So if THAT relation holds then presumably you should have solutions,
>EXCEPT notice that with the solutions for z and y, the variable k is
>in both, and it can occur that k is a factor in both--which is a block
>unless T has k as a factor!!! The situation is actually even more
>complicated as with z and y, you can get solutions for factors f_1 and
>f_2
I assume that f_1 and f_2 are both positive integers.
>where f_1*f_2 = T:
>
>f_1 = ak mod p
>
>and
>
>f_2 = a^{-1}(1 + a^2)k mod p
>
>and again k provides a possible block, as for instance with a=1, if k
>is less than p, and z is less than p, then those relations would
>require that f_1 and z have the same factor, which would force it into
>f_2, and into T, as:
>
>z = (f_1 + f_2)/2
>
>And similar problems happen with y, as y = (f_1 - f_2)/2, and I call
>the first situation the z constraint, while the second is the y
>constraint.
>
>But if none of the 4 constraining equations, the z, y, f_1 and f_2
>equations give a conflict, and T - (1+a^2)k^2 = 0 mod p, then this
>approach MUST give solutions.
>
>But then, how do you use it?
>
>Here's a quick example of a factorization using all of the machinery
>above:
>
>Let T=341. Then p=17 is the greatest prime less than sqrt(341)
I cannot see anywhere above where you state how to pick the correct
value of p. Am I right to assume that you pick p using the largest
odd prime smaller than sqrt(T)?
>and starting with a=1, gives
>
>k^2 = (2)^{-1}(341) mod 17 = 9(1) mod 17 = 9 mod 17.
>
>so it does exist and k=3 or k=14 are possible, but with the first f_1
>= ak = 3 is not a factor and 14 is not either.
>So next check f_2, f_2 = a^{-1}(1 + a^2)k = 2(3) = 6 which is not a
>factor but 17-6=11, and 11 is a factor. Success!
>
>And you have a non-trivial factorization, as 341 = 11(31).
>
>Notice that z=(11+31)/2 = 21, so no conflict, y = (31-11)/2 = 10, so
>no conflict.
>
>And the equations escape conflict with the f's by going to the
>negative residues, so checking p - f_1 and p - f_2 is a necessity.
>
>So there HAD to be a solution in this case. So once k existed,
>without conflict from any of the 4 constraints, a factorization had to
>be found.
>
>The method represents a back door into factoring which allows you to
>leverage an infinity to factor a composite. Your factoring engine is
>infinity itself. And infinity is a powerful tool!!!
>
>You can scan through p's to find a large one,
This confuses me. In your example above you picked a single value of
p. Now you are talking about scanning through multiple p's. Is p
then not fixed, and what value to you pick if the initial one fails?
>though notice you can't
>just pick too huge a p, as then you're likely to get a conflict with
>one of the 4 constraints, and you can choose the variable 'a'
What criteria do we use to chose the initial value of a and the
subsequent values? How many a's do we pick before we decide that the
current p is not going to work and we have to move on to the next
value of p?
The more variables you have to pick the slower your method is going to
be. A slow method will not make any impact on the factoring problem.
>to try
>and adjust around the constraints as well, as notice if a=1, like with
>my example and k is even, then with:
>
>y = (2a)^{-1}k mod p, you have y = k/2 mod p, so if k is close to p,
>so k/2 < p, then you conflict with f_1 = ak = k, with a=1
>
>So when k is even you already know that a=1 will probably not work
>well, but then you can use a=2, or a=3, or a=6, or some other.
What formula are you using to decide these values of a?
>
>So what is the Big O time complexity of this approach?
>
>It cannot be calculated,
This I doubt. Just calculate the average number of p's and a's you
need to try before finding factors. That will allow you to calculate
the Big-O. For example if you need to try 2 p's and six a's on
average then just count operations for one p and one a, multiply and
add. You can find averages by running an instrumented implementation
of your algorithm on a reasonable sample of targets.
rossum
JSH
Probably mirages. If k exists then there are 4 constraints which can
block a solution:
z = (2a)^{-1}(1 + 2a^2)k mod p
y = (2a)^{-1}k mod p
f_1 = ak mod p
and
f_2 = a^{-1}(1 + a^2)k mod p
Because k is in each, if despite the "mod" prime factors of k end up
being factors of ANY TWO of the 4 constraints then a solution is
blocked.
To see blocking in place try T = 133, with p=11, and note that with
a=2, you have k, but are blocked by the y constraint because it'd
share a factor with f_1, because y=6.
So you can get very complex behavior which hampered my research for
years I think, as I'd see approaches that seemed to work miraculously,
only to then repeatedly fail when I thought they should still work, as
I was thinking linearly. The method is a non-linear approach.
> You should be able to get a rough idea of the Big O time complexity.
>
> Enrico
The method can conceivably factor a composite T = p_1*p_2 in a single
iteration no matter how large the primes p are, if a=1 will work, and
none of the constraints blocks, yet can take much longer for a rather
small composite T, simply because one of the constraints blocks.
The Big O methodology wasn't thought up for something like this
method.
The method could conceivably factor the largest composite human beings
can generate in milliseconds, while struggling more with a relatively
small composite (though there are techniques to get around the
blocking so it could still be FAST).
It changes the way you approach these problem entirely as it's an
indirect factoring approach.
Big O works best for direct approaches where the size of T and its
factors is important. For this method the size of T and its factors
is mostly irrelevant, though at best you can remove the z constraint
by using a p that is roughly sqrt(T), but that's the only size
concession you get, and it really only matters with a=1.
James Harris
Enrico
>
> - Show quoted text -
==================================================
>
> The method could conceivably factor the largest composite human beings
> can generate in milliseconds, while struggling more with a relatively
> small composite (though there are techniques to get around the
> blocking so it could still be FAST).
>
Then it looks like you're gonna have to develop those techniques to
get
around the blocking.
Enrico
JSH
Not me. If this factoring approach pans out then people using
anything else are already in the Dark Ages, way behind. So it's like
you're a primitive if you stay with the NFS, when everybody else
starts running rings around it with this thing.
If that is true, don't worry, it'll take over the world.
Sure, there will be primitives. There will be "computer scientists"
and cryptologists who will stay with what's comfortable. But there
are always such people. And the world will leave them as it moves
rapidly past them.
I don't have to do anything, but that doesn't mean I don't puzzle over
it here and there as it's interesting. So I do my little musings here
and there and talk about what I notice. It's a vast and new
territory, showing mathematics where infinity is your friend. It's
like the math talks to you in a conversation and is this genie that
will do things other people thought impossible or required special
things like quantum computers. They were wrong.
Nope mathematics is just as powerful as ever and that means it will be
used.
And it's my math.
James Harris
JSH
Hey I replied once but maybe I shouldn't be so dismissive about trying
to get the Big O time complexity, but I'm not going to try it, if
others wish they can make the attempt, but I think the effort is a
waste of time.
But hey, it's basic research. Posters get confused on how long I've
been doing my own amateur research and the correct answer is 14 years.
I had the basic idea for solving for quadratic residues LAST YEAR
about this time. Research to me is usually about years. I finally
figured out there is no Hollywood reality. It's made up. Writers
come up with that stuff who probably don't even known any math or any
real research.
Real research takes so long it won't fit into a Hollywood script.
I'm tying down some loose ends though, which is good feeling. I like
finally understanding better when and how this thing works!
Soon enough I'll move on, and maybe I'll think about it next year for
the next anniversary when it'll be two years old.
Or maybe not. I have a huge field of my own research to look over at
any given time, including research outside of mathematics. There are
results that I do not re-visit within a years time (I think as it's
hard to keep up).
It's hard for me to keep up with my math. Wow that's kind of wild.
But hey, 14 years of research results. The things pile up.
James Harris
JSH
That's wrong!!! Another possibility is that the factor IS a factor of
them all, and is a factor of T as well.
A great example is q=2, with p = 31. Then T = 4 mod 31, and you get a
solution with T = 128.
There f_1 = 8, f_2 = 16, and k = 8. 8^2 = 2 mod 31.
> To see blocking in place try T = 133, with p=11, and note that with
> a=2, you have k, but are blocked by the y constraint because it'd
> share a factor with f_1, because y=6.
That is correct. I get messed up on the even case as I'm so used to
NOT letting T be even that I forget at times that's a possibility when
you're reversing the equations to solve for quadratic residues.
Fascinating mathematics. You can spend lots of time just doodling
with it, looking at interesting things.
James Harris
Patrick Karl
> Or maybe not. I have a huge field of my own research to look over at
> any given time, including research outside of mathematics. There are
> results that I do not re-visit within a years time (I think as it's
> hard to keep up).
>
> It's hard for me to keep up with my math. Wow that's kind of wild.
> But hey, 14 years of research results. The things pile up.
Wow! Fourteen years of research results. In what peer-reviewed
journals can I find some of your research, mathematical or otherwise?
JSH
You COULD have found a pivotal paper in the now defunct journal
SWJPAM:
http://www.emis.de/journals/SWJPAM/vol2-03.html
Usenet posters like yourself mounted an effective email campaign
against the paper when they heard I'd been published (howls of Usenet
rage were elicited on the sci.math newsgroup), conspiring IN POSTS on
the newsgroup for that campaign.
They spooked the editors who pulled my paper and the journal managed
one more edition then quietly shut-down. Its hosting university
SCRUBBED ALL MENTION of the journal from its websites though the
journal had been around for about 10 years.
EMIS, a European agency (those crazy Europeans believing in academic
freedom and the pursuit of knowledge!!!), have kept up the archives,
and give a brief history:
http://www.emis.de/journals/SWJPAM/
They also put my paper back up! (Again, those CRAZY Europeans,
believing in the value of knowledge!!!) but I don't link to it as I've
vastly simplified the argument. Google (has to be Google): algebraic
integer entanglement
Your system is broken.
You proudly trotted out the publication argument because you thought
it was a barrier to people like me.
Your prejudices are about ignorance.
Oh yeah, a correction though, I have 13 years of research results, but
starting doing my own amateur research 14 years ago. I credit my own
solution to the spherical packing problem as my first major find.
Now journals won't touch my papers. I send them things and I often
get replies from the chief editor (anyone below the chief won't do!)
telling my paper is "not suitable" for the journal.
I'm a much bigger figure in your world than you are, but you can make
fun of me because academics refuse to properly acknowledge my
research.
So I just talk about it like I'm doing on Usenet, and put it out on
the web. If correct it'll take over anyway, and then when I crush the
funding out of the system, no one will be able to make me feel
guilty. No one.
You took time from me. I'll take your funding. All of it.
James Harris
rossum
wrote:
>That is correct. I get messed up on the even case as I'm so used to
>NOT letting T be even that I forget at times that's a possibility when
>you're reversing the equations to solve for quadratic residues.
>
>Fascinating mathematics. You can spend lots of time just doodling
>with it, looking at interesting things.
So James, since you are still "just doodling" and are still getting
"messed up" on the details I will hold off testing your current mrthod
as you obviously haven't finished it yet and are still in the
brainstorming stage.
rossum
Noob
> Fascinating mathematics. You can spend lots of time just doodling
> with it, looking at interesting things.
And you often do doodle, don't you?
Mark Murray
"Doodling" and "Brainstorming" are the excuses James uses to cover up
what happens when folks find the errors in his so-called "math".
M
--
mm
Jerryfox
Get your [url=http://www.flashpapers.com]Term Papers[/url] done - FlashPapers.com