|
|
Re: JSH: Upside down situation
Posted:
Mar 15, 2008 2:29 PM
|
|
On Mar 15, 5:49 am, Vend <ven...@virgilio.it> wrote:
> On 15 Mar, 02:01, JSH <jst...@gmail.com> wrote:
> <snip>
>
> > Oh, so why might you get "misfactors" searching k modulo p?
>
> What do you mean by "searching k modulo p"?
>
> <snip>
Given z^2 = y^2 + nT, where T is a target composite to factor, I've
shown that
z = (1 + 2a^2)k/(2a)
where
k^2 = (1 + a^2)^{-1}(nT) mod p
so you find k by finding 'a' such that k exists for a given odd prime
p, but there is a rule on p that it be less than the smaller factor of
nT--looking only at positive factors--or that p minus the smaller
factor be less than that factor.
So, say you pick a prime p approximately sqrt(nT) hoping that your
smaller factor isn't too small, and then you try some 'a', like a=1,
to see if k exists, if it doesn't you use another prime. If it does,
then you have k modulo p.
Further research shows that k is near a value I call k_0 which is
given by finding k_0 such that
abs(nT - (1+a^2)k_^2)
is a MINIMUM, so you have to find an integral quadratic minima.
Full surrogate factoring theory then says that k_0 is within k_0/2p
steps from a k that will factor your target i.e. give you z = (1 +
2a^2)k/(2a) such that
z^2 = y^2 + nT.
Since p increases in size as T increases in size, it is crucial to
search for k modulo p, as otherwise you have to get really lucky with
your k_0, and in fact, searching by just incrementing k by 1 means you
have approximately k steps, versus k/2p steps. A big difference.
To figure out how big, just run some examples, where you have a
factorization of T so you have z, and can calculate k, and then see
how many steps you'd have versus using a prime p approximately equal
to your smaller prime factor so that you can get k/2p.
Oh, so a big issue is guessing at how small p has to be versus your
wish to make p as large as possible, which is probably where most of
the problems with implementing this practically step in, as otherwise,
on paper, it is a solution to the factoring problem.
There is a preference for z divisible by 3, so n can be used to force
nT mod 3 = 2.
The subject of this thread is a gesture of my frustration at being
able to find cutting edge mathematics that is just ignored by the bulk
of math society which cheers its own, however.
Outsiders are just cut-off with no options but forcing the issue as
I'm attempting to do with the factoring problem, as mathematicians
ONLY will support each other, without regard to the research, which I
call an upside down situation where they fight for each other and give
"gold medals" to their colleagues but will simply ignore wins by
outsiders like myself.
James Harris
|
|
