Wednesday, November 19, 2008
Deep variable factoring method
Remarkably the seemingly well-known quadratic equation
z^2 = y^2 + nT
can be analyzed rather thoroughly with a solution for z using some basic algebra. That solution for z is
z = (1 + 2a^2)k/(2a)
where with positive non-zero integers z, y, n and T, with z and y coprime, it is not necessarily the case that k and 'a' are themselves integers, and the result may seem trivial until it's noted that there must exist a prime number p such that
k^2 = (1 + a^2)^{-1}(nT) mod p
where p is what I call a helper prime as it is only relevant to the analysis in order to find z, which is done by finding k and 'a' when they are integers, which is why I call this a deep variable factoring method.
The result STILL may seem trivial until it's noted that for cases where k and 'a' are positive integers, it can be proven that the minimum value for k, which I call k_0 is given by finding k such that
abs(nT - (1 + a^2)k^2)
is a minimum, which is kind of remarkably odd, as given k, you have z, and a factorization of nT, but knowing the minimum k does not necessarily make solving for k easy as an even deeper result is that k will be within 2ap steps of floor(k_0/2p) which brings the helper prime p to the forefront of the question of the usefulness of this approach!
The desired number of steps is 0, and it can be shown that p near sqrt(T), as long as n is small should do the trick! So how do you find the "helper prime" with the appropriate size?
There are two more important equations relevant to that question. If you have positive integers f_1 and f_2 where
f_1*f_2 = nT
then it must be true that
f_1 = ak mod p and f_2 = a^{-1}(1 + a^2)k mod p
so this approach will GIVE f_1 directly if f_1 is less than p, which is great!!! But notice that if k is less than p as well, then you have that k must be a factor of nT, which is not so great, and in fact, that is a huge damper as if you already knew a factor of nT, you wouldn't be looking for a k to factor it!
(That result has deeper implications for what solutions can be available for a given k and 'a' which is of more "pure math" interest.)
So now finally limiting factors on the helper prime p are clear where it is primary that if f_1 is less than p then ak must be greater, and now finally I can reach the crucial equation which determines the efficacy of this method, as now the variable n proves its worth, as from before I have
k^2 = (1 + a^2)^{-1}(nT) mod p
so I can reverse things and solve for n to get
n = (1 + a^2)k^2(T)^{-1} mod p
where the BEST case is n=1, as then if p > sqrt(T), then I have a factorization from f_1 = ak, so ALL determination of the efficacy of this approach of deep variables rests on how easily one can find k and 'a' such that n is a minimum!
If z does not have integer solutions for k and 'a' when n=1, then that will preclude n=1 since
z = (1 + 2a^2)k/(2a)
but then how about n=2? Or some small n that will still factor? As if you can find a small enough n, then regardless of the size of the number all of the equations above will work and just GIVE you f_1 and a factorization of nT, if the helper prime p is greater than sqrt(nT).
So all issues with the potential of this method boil down to how easily k and 'a' can be picked such that
(1 + a^2)k^2 = m mod p
where m is some arbitrary residue, preferably very small where the best is m=1, when p is a very large prime.
And it took me YEARS to figure out this approach and MONTHS to boil down questions of its efficacy to just that equation which is what I only just accomplished today in terms of realizing its significance!
It is rather exciting to me to be able to add to the prior knowledge about such a seemingly simple equation as
z^2 = y^2 + nT
where it's also of "pure math" interest as you can actually still factor with k and 'a' when those are non-rationals and it is of number theoretic interest how residues behave with them as non-rationals as well.
And the helper prime p is just amazing as a deep variable that is only there for this purpose and vanishes like a ghost when you have an answer, as in actuality so do k and 'a', as once you have z the machinery needed to find it just disappears! Which reminds me of thoughts of deep or hidden variables in physics as this algebra may indicate that they could have a role in our physical reality, where phenomena is less easily explained by the surface variables alone, than by transient variables that briefly exist to help, and then just disappear.
z^2 = y^2 + nT
can be analyzed rather thoroughly with a solution for z using some basic algebra. That solution for z is
z = (1 + 2a^2)k/(2a)
where with positive non-zero integers z, y, n and T, with z and y coprime, it is not necessarily the case that k and 'a' are themselves integers, and the result may seem trivial until it's noted that there must exist a prime number p such that
k^2 = (1 + a^2)^{-1}(nT) mod p
where p is what I call a helper prime as it is only relevant to the analysis in order to find z, which is done by finding k and 'a' when they are integers, which is why I call this a deep variable factoring method.
The result STILL may seem trivial until it's noted that for cases where k and 'a' are positive integers, it can be proven that the minimum value for k, which I call k_0 is given by finding k such that
abs(nT - (1 + a^2)k^2)
is a minimum, which is kind of remarkably odd, as given k, you have z, and a factorization of nT, but knowing the minimum k does not necessarily make solving for k easy as an even deeper result is that k will be within 2ap steps of floor(k_0/2p) which brings the helper prime p to the forefront of the question of the usefulness of this approach!
The desired number of steps is 0, and it can be shown that p near sqrt(T), as long as n is small should do the trick! So how do you find the "helper prime" with the appropriate size?
There are two more important equations relevant to that question. If you have positive integers f_1 and f_2 where
f_1*f_2 = nT
then it must be true that
f_1 = ak mod p and f_2 = a^{-1}(1 + a^2)k mod p
so this approach will GIVE f_1 directly if f_1 is less than p, which is great!!! But notice that if k is less than p as well, then you have that k must be a factor of nT, which is not so great, and in fact, that is a huge damper as if you already knew a factor of nT, you wouldn't be looking for a k to factor it!
(That result has deeper implications for what solutions can be available for a given k and 'a' which is of more "pure math" interest.)
So now finally limiting factors on the helper prime p are clear where it is primary that if f_1 is less than p then ak must be greater, and now finally I can reach the crucial equation which determines the efficacy of this method, as now the variable n proves its worth, as from before I have
k^2 = (1 + a^2)^{-1}(nT) mod p
so I can reverse things and solve for n to get
n = (1 + a^2)k^2(T)^{-1} mod p
where the BEST case is n=1, as then if p > sqrt(T), then I have a factorization from f_1 = ak, so ALL determination of the efficacy of this approach of deep variables rests on how easily one can find k and 'a' such that n is a minimum!
If z does not have integer solutions for k and 'a' when n=1, then that will preclude n=1 since
z = (1 + 2a^2)k/(2a)
but then how about n=2? Or some small n that will still factor? As if you can find a small enough n, then regardless of the size of the number all of the equations above will work and just GIVE you f_1 and a factorization of nT, if the helper prime p is greater than sqrt(nT).
So all issues with the potential of this method boil down to how easily k and 'a' can be picked such that
(1 + a^2)k^2 = m mod p
where m is some arbitrary residue, preferably very small where the best is m=1, when p is a very large prime.
And it took me YEARS to figure out this approach and MONTHS to boil down questions of its efficacy to just that equation which is what I only just accomplished today in terms of realizing its significance!
It is rather exciting to me to be able to add to the prior knowledge about such a seemingly simple equation as
z^2 = y^2 + nT
where it's also of "pure math" interest as you can actually still factor with k and 'a' when those are non-rationals and it is of number theoretic interest how residues behave with them as non-rationals as well.
And the helper prime p is just amazing as a deep variable that is only there for this purpose and vanishes like a ghost when you have an answer, as in actuality so do k and 'a', as once you have z the machinery needed to find it just disappears! Which reminds me of thoughts of deep or hidden variables in physics as this algebra may indicate that they could have a role in our physical reality, where phenomena is less easily explained by the surface variables alone, than by transient variables that briefly exist to help, and then just disappear.
# posted by James Harris @ 21:25 
