Re: Surrogate factoring demonstrated
jstevh_at_msn.com
Date: 03/02/05
- Next message: robert j. kolker: "Re: Epistemology 201: The Science of Science"
- Previous message: Arturo Magidin: "Re: JSH: Deleted blog mathforprofit taken over"
- In reply to: Will Twentyman: "Re: Surrogate factoring demonstrated"
- Next in thread: Prai Jei: "Re: Surrogate factoring demonstrated"
- Messages sorted by: [ date ] [ thread ]
Date: 1 Mar 2005 16:40:09 -0800
Will Twentyman wrote:
> jstevh@msn.com wrote:
> > Will Twentyman wrote:
> >
> >>jstevh@msn.com wrote:
> >>
> >>
>
> >>Do you have any data on how it compares with other methods either
> >
> > speed
> >
> >>or success wise?
> >
> > Probably very badly. But I'd appreciate actual data nonetheless,
and
> > while some posters *have* put up data with other algorithms, I
haven't
> > seen much with the one that factors only T, which is the one I give
in
> > this thread.
> >
> > Here's another demonstration from my current test program which
tells a
> > lot of why I'm suspicious of negative bashing posters:
> >
> > ( 5^6 )( 11^6 )( 67^6 )( 1753^6 )( 137573^6 )( 214213^6 )(
292393^6 )(
> > 4197749^6 )
> >
> >
> > T=233658657807655786575865728865
> >
> > Iterations: 36384
> >
> > Number factored.
> > Initial Factorization:
> > f_1=15878593
> > f_2=54304241
> > Now checking its factors...
> > moving up a level
>
> This strikes me as very odd. Why would you start with those choices
for
> f_1 and f_2?
>
I just have a pile of primes that I try.
> >
> > Success!
> > Factors:
> > ( 15878593 )( 54304241 )
> > Product: 862274941012913
> >
> > In coming is 862274941012913
> > Number of digits: 15
> > bitLength=50
> >
> > I edit out information like time data (not good) as I'm wary of
giving
> > the negative politicos more data to spin, as well as some specifics
> > that relate to details of what the program is doing and what I'm
> > researching currently.
>
> The time data is one of the critical concerns. If it simply isn't
good,
> so be it. Also, are you using your method recursively to factor T?
If
> so, this could get very ugly as you generate T1, T2, T3, T4, ...
> attempting to factor your numbers. If the time complexity is not
good,
> you are compounding the problem.
Usually T factors easily enough, and I pick some of its factors anyway.
There's a lot of control over the value of T and its factors.
Here's a recent calculation.
M = 137760568244733982624147
T = 4447962667997622209474442602848431325089020265
and T^6 factors as
( 3^2 )( 5^2 )( 7^2 )( 81 )( 83^2 )( 625 )( 2401 )( 6561 )( 137573^2
)(214213^2 )( 390625 )( 5764801 )( 43046721 )( 47458321 )(
691803870101801^2 )( 25034085061379579^2 )
where hopefully the copy and paste went ok, and you can see something
different here, as it turns out you can use the factors to the 4th
without breaking them up. Like T^2 has 3^2 as a factor, so you iterate
through it where that means you'll break it up and use 3 at time, but
3^4 = 81, and that doesn't need to be broken up.
Integer factors of T, worked here
Iterations: 186470
Number factored.
Initial Factorization:
f_1=10161161
f_2=13557561802704827
In coming is 137760568244733982624147
Number of digits: 24
bitLength=77
One thing that's of interest is that f_2 is composite, as I'm finding
it's easier to factor numbers with more than 2 prime factors, so oddly
enough, you might factor a large number by multiplying it times a very
large prime, which I call a cracking prime.
The program failed to factor f_2, so with three prime factors, it
managed to pull one out.
The factorization is likely to pull out the smallest prime first.
Now get this, the more factors your M has, the more likely it will
factor!
And notice the number of iterations.
As you get bigger and bigger numbers, the number of iterations to
factor climbs more slowly than the number, so the method gets more
efficient as the size of the number increases--if it actually factors.
That is, if you get a factorization, the number of iterations necessary
to pull out the factor drop as a percentage of the number, but right
now there's the issue of always getting a factorization for a given j.
Here I tried one j, and it worked.
> > Sure it's only a 50 bit number, but it did factor. I forced in
factors
> > of 2, so the iterations max out at 8 times the number shown (though
I
> > think the real number is a lot less...I guess I should have the
> > computer count).
> >
> > Now I can do that with 50 bit numbers and 40 bit numbers but for
some
> > reason things usually crap out with larger numbers, but, you see, a
few
> > weeks ago, I couldn't do that with 50 bit numbers and 40 bit
numbers as
> > the programs would crap out...
>
> It might be worthwhile to look for patterns in number of iterations
to
> factor a number, number of bits, number of factors, and spread
between
> factors.
>
> > As I work out theory, the programs get better and faster.
>
> That would be reflected in changes in the algorithms used.
>
The algorithm so far is basically simple, which probably means that
little effort would make a far better and more complex algorithm, but
right now, I don't know if anyone knows how to do it.
It's all so new.
Like I can show that the current algorithm I'm using is a lot like just
taking
f_1 - f_2
and getting the gcd with M, where f_1 f_2 = T^6, and T = M^2 - j^2,
like before, which I thought about after the "Nora Baron" posts, so yes
that poster seems to be on to something.
Now I think that quadratic residues play a major role, and it's quite
likely that as time progresses algorithms will develop from this very
basic start.
The holy grail is an algorithm that guarantees a factorization for any
non-zero integer j, coprime to M.
> >
> > So functionally I know certain people aren't exactly making sense
with
> > their criticisms, as for instance, they should have reported a
sharp
> > increase in factoring efficiency with the latest algorithm that
only
> > factors T, where you need T^6, versus ALL the previous ones, with a
> > HUGE jump from algorithms where you factored T and j.
>
> Certainly they should have, but did you ever announce *how* you were
> getting the factorization of T^6? Also, if they didn't know there's
a
> new version, they wouldn't report that jump. Finally, there might
not
> be a sharp increase in factoring efficiency depending on what
algorithm
> is used to factor T^6. Not having looked at your code, I can't say
what
> happened. Did you notice such a jump in your experiments?
I've always used algorithms that use factorizations of T only, while I
talked about algorithms that used T and j as it was easier to explain
from some basic equations.
A couple of posters said they were implementing those algorithms and
talked of having to go through several j's to get an answer, while in
my research I rarely change j, as I'm looking for an algorithm that
will work for any non-zero integer j coprime to M.
I notice that no one talks about factoring T and j anymore so I surmise
those algorithms dropped to the side, as they should being much more
inefficient.
So there should have been a HUGE jump between the early algorithms
using factorizations of T and j, versus these ones from the more
advanced theory that use just T.
James Harris
- Next message: robert j. kolker: "Re: Epistemology 201: The Science of Science"
- Previous message: Arturo Magidin: "Re: JSH: Deleted blog mathforprofit taken over"
- In reply to: Will Twentyman: "Re: Surrogate factoring demonstrated"
- Next in thread: Prai Jei: "Re: Surrogate factoring demonstrated"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
