Saturday, January 26, 2008
JSH: Generalizing to factors mod N
The recent research I've discussed with much frequency recently can be further generalized, so that you can calculate factors modulo N, where N can be a prime number or a composite. I will make one variable change from previous expositions going from 'n' to 'm' since I'm now using capital 'N' instead of 'p':
With z^2 = y^2 + mT, where T is the target composite to be factored, m is a non-zero integer of your choice, and N is a prime or composite of your choice, you may find the following to be true:
z = (2a)^{-1}(1 + 2a^2)k mod N
where
k^2 = (a^2+1)^{-1}(mT) mod N
and y can be calculated then from y^2 = z^2 - mT modulo N, and resolving the quadratic residue.
Then your factors f_1 and f_2 where f_1*f_2 = mT, can be found from
f_1 = z-y mod N, and f_2 = z+y mod N.
Notice that allowing composites with N versus primes with p, changes things slightly, in that you don't get a probability for success (at least not an easy one to calculate so I've left that for further research), and no congruence solution of y.
To get the more generalized relations you just loop through the derivation for the factors mod p, and substitute out 'N' for 'p' in all cases where N being prime is not part of the derivation.
It is my hope that moving from primes will help some of you to see the value of this research! Oddly enough my use of primes may have been very problematic as many of you are clearly very thoroughly trained that mod p is a trivial area, while conversely you should be just as well trained to think that mod N is a big deal.
When the irony is that with a proper approach to the factoring problem—relying on its two legs versus using just one—they are hardly different at all.
With z^2 = y^2 + mT, where T is the target composite to be factored, m is a non-zero integer of your choice, and N is a prime or composite of your choice, you may find the following to be true:
z = (2a)^{-1}(1 + 2a^2)k mod N
where
k^2 = (a^2+1)^{-1}(mT) mod N
and y can be calculated then from y^2 = z^2 - mT modulo N, and resolving the quadratic residue.
Then your factors f_1 and f_2 where f_1*f_2 = mT, can be found from
f_1 = z-y mod N, and f_2 = z+y mod N.
Notice that allowing composites with N versus primes with p, changes things slightly, in that you don't get a probability for success (at least not an easy one to calculate so I've left that for further research), and no congruence solution of y.
To get the more generalized relations you just loop through the derivation for the factors mod p, and substitute out 'N' for 'p' in all cases where N being prime is not part of the derivation.
It is my hope that moving from primes will help some of you to see the value of this research! Oddly enough my use of primes may have been very problematic as many of you are clearly very thoroughly trained that mod p is a trivial area, while conversely you should be just as well trained to think that mod N is a big deal.
When the irony is that with a proper approach to the factoring problem—relying on its two legs versus using just one—they are hardly different at all.
# posted by James Harris @ 13:28 
