Did I find a new way to factor or not?
If I did, then no matter what your personal feelings about me, then you
probably figure that mathematicians have a *duty* to report a new way
to factor.
If I did not, then if you're a reasonable person you should require
that someone PROVE I did not.
If you wish to add in some other possibility, please go ahead, as I
think this needs to be talked out.
There are only so many factoring methods known.
Do mathematicians or do they not have a duty to acknowledge and report
a new way to factor?
No matter what you believe on the subject, I can assure you that
professional mathematicians believe they do not.
And they will ignore my recent research, like they're already doing as
I've been talking about this for a while, and I contacted
mathematicians in the field by email, and they will not be able to give
you a reasonable answer why.
Should a find of a new way to factor be acknowledged by mainstream
mathematicians?
If not, do you honestly believe that just anybody can figure out a new
way to factor?
Think factoring algorithms are popping up all over the place?
Do you really think just *anybody* can find a new way to factor?
Could you?
James Harris
You seem to have found a way to factor. I don't
know whether it is a new way or not.
But, you know, a new *inefficient* way to factor
simply isn't interesting. What you haven't done is
demonstrate your repeated claim that it is
polynomial time. Since it can only increase the
size of the surrogate target, you have to end up
factoring something with a different method, and
the only known different methods are more than
polynomial time. Therefore I conclude that your
method cannot be polynomial time. Now, if it's
subexponential, it could still be interesting, but
you haven't argued for that, either.
It seems to me that it all boils down to just how
easy it is to factor a random large number, or
more precisely, given many large numbers in a
given range (spread out just below M^2), what is
the chance that at least one of them will be
completely factorizable by trial division. This
is, by the way, called "smoothness" and underlies
methods like the quadratic sieve. Which is why I'm
not sure if your method is new, or not... it might
just be a special case of the quadratic sieve. I'm
not expert enough to comment on that.
>If I did not, then if you're a reasonable person you should require
>that someone PROVE I did not.
I disagree. Why should I or anyone else have to
prove you wrong, when it's your job to prove that
you're right? That's what "burden of proof" is all
about.
[snip]
>And they will ignore my recent research, like they're already doing as
>I've been talking about this for a while, and I contacted
>mathematicians in the field by email, and they will not be able to give
>you a reasonable answer why.
I can tell you why. It's because professionals get
paid to do what they do, and you're asking them
for free work. Try getting your backyard
landscaped that way, and see what happens. (I just
tried. They laughed at me. :-)
>Should a find of a new way to factor be acknowledged by mainstream
>mathematicians?
That depends. There are two criteria: newness and
"interestingness". If you present them with a
valid proof that the method works (which you may
have done, but I haven't seen it), you then need
to go on and show that it's interesting. This
requires proving a polynomial or good
subexponential running time. You certainly haven't
done that.
Until you show that the method is interesting, why
is anyone obligated to spend any of their precious
time doing anything at all with it?
Here's an example of what I mean. I once invented
a new (to me) factoring algorithm. It turns out
that efficient methods of factoring polynomials
exist. So, take the number to be factored M, and a
small integer x, and express M = P(x). Factor P(x)
using the polynomial factoring algorithm,
P(x)=a(x).b(x). Now a(x), evaluated with the
actual small integer used, must be a factor of M.
This algorithm works, and is trivial to prove.
However, what I missed was the fact that P(x) is
almost always irreducible. You have no good way of
choosing an x that will work. (To this day, I
still don't even know that such an "x" exists for
for an arbitrary composite M.) What I do know is
that the probability of hitting on such an x is so
low that the method is too slow to be of
interest, once you try out lots of values for x.
Do you acknowledge my new factoring method? Should
other mathematicians? I don't expect them to.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au
How fast was congruence of squares when discovered?
Do you even know who discovered it?
>What you haven't done is
> demonstrate your repeated claim that it is
> polynomial time. Since it can only increase the
That's easily done and has to do with the number of combinations
generated at each level of calculation, where I mean recursion level.
It's just not worth going into more detail than that now.
> size of the surrogate target, you have to end up
> factoring something with a different method, and
> the only known different methods are more than
> polynomial time. Therefore I conclude that your
That's not exactly true.
Besides, I don't have to use different methods to factor T, as in fact,
my prototype program recursively calls itself--shrinking numbers all
the way--until it gets to something under 200, at which point is uses a
prime list.
So I know you're not paying attention, already, or you'd have known
that without me having to repeat it here.
Now, factoring is in general hard, with *certain* types of numbers,
while not necessarily so with others.
My surrogate T, is offset from M, the target by the formula
T = M^2 - j^2
which factors somewhat, immediately into
T = (M-j)(M+j)
where for positive j, M-j is necessarily less than M, and M+j can be
*given* whatever factor you wish by picking j appropriately, so that
you can factor it immediately to shrink the number.
There are any number of smart things you can do when you can have as
much control as my method gives.
Now I don't see posters talking about that, as you're not interested in
the mathematics or what's possible, but only in trying to dismiss my
discovery.
But you're wasting your time, as mainstream mathematicians will try to
ignore it anyway, no matter what you do, so your effort is pointless.
> method cannot be polynomial time. Now, if it's
> subexponential, it could still be interesting, but
> you haven't argued for that, either.
>
There are only so many factoring methods known, even inefficient ones,
while certain key features of my discovery make it very exciting, and
make it definite that an inefficiency claim at this point is
short-sighted.
That you jump to a conclusion isn't a surprise to me.
You just have something you wish to believe and can't pause for even a
moment to let facts gather before you jump in with your opinion, even
when it defies the mathematics.
I, on the other hand, have worked out a lot of the theory, and the
theory says that this factoring method is in fact a solution to the
factoring problem.
That is a statement of mathematical fact. If you don't believe it's
mathematical fact then you have the route of proving your disbelief
mathematically.
There are a LOT of little proofs that I've ran through at this point in
order to come to my conclusion, many of them extraordinary in terms of
what the mathematics shows MUST be true.
For that reason, I can confidently state--before there's an
implementation that I know of which shows this--that the factoring
problem has been solved and it's now just a matter of time before the
implementation demonstrating that is out there.
You can debate about it all you want, but like I said earlier today,
I'm just goofing off, as the hard theoretical work--I think--is done.
In the end, the real world will determine the truth as factoring is
important in the real world, and your opinions, thoughts or feelings
have no impact here.
In the meantime, sure, chattering about it can be fun, but it's not
substantive.
James Harris
Not fast. It was invented when people did math by hand. It was faster
than trial division which was a "big speedup" then.
> Do you even know who discovered it?
Fermat. It's cited in TAOCP and most elementary number theory texts.
It's commonly known as a the "factoring sieve" and Fermat showed that
you can speed over many "invalid potential squares" by using a properly
constructed sieve.
For the benefit of others... In "The Art of Computer Programming"
volume 2, pp. 386 descries Fermat method. It is listed as "algorithm
C" [pp.387]
Algorithm C. Given an odd number N this algorithm determines the
largest factor of N less than or equal to \sqrt{N}.
1. x = 2\sqrt{N}, y = 1, r = \lfloor \sqrt{n} \rfloor ^2 - N
2. if r == 0 then we terminate as N = ((x-y)/2)((x + y - 2)/2) and
(x-y)/2 is the largest factor.
3. r = r + x, x = x + 2
4. r = r - y, y = y + 2
5. if r > 0 goto 4, otherwise goto 2
At first this seems slow as it takes exponential time (in practice it's
equal to the distance from \sqrt{N}).
So this seems a bit slow.. . Fermat then refined this method, from
pp.387, "...It is not quite correct to call Algorithm C Fermats Method,
since fermat used a somewhat streamlined approach..."
The change was to not maintain y but instead look at x^2 - N and guess
whether or not the value was square. This was by using a sieve. E.g.
there are 3 Q.Rs modulo 7. So reduce x^2 - N modulo 7. If the result
is not a quadratic residue then you know that you're not on a possible
factor.
He explains the sieve more on pp.387-388 even citing the factorization
of 8616460799 as "done by hand". Next he describes algorithm D.
"factoring with sieves" on pp.389.
Just so you know ... ;-)
> >What you haven't done is
> > demonstrate your repeated claim that it is
> > polynomial time. Since it can only increase the
>
> That's easily done and has to do with the number of combinations
> generated at each level of calculation, where I mean recursion level.
>
> It's just not worth going into more detail than that now.
Well I'd say it is as you're going on about being persecuted. Maybe
you should actually take the time to present your results. Also just
because it's recursive doesn't mean it's polynomial time. What if you
have to recurse a sub-exponential number of times?
> > size of the surrogate target, you have to end up
> > factoring something with a different method, and
> > the only known different methods are more than
> > polynomial time. Therefore I conclude that your
>
> That's not exactly true.
>
> Besides, I don't have to use different methods to factor T, as in
fact,
> my prototype program recursively calls itself--shrinking numbers all
> the way--until it gets to something under 200, at which point is uses
a
> prime list.
>
> So I know you're not paying attention, already, or you'd have known
> that without me having to repeat it here.
You haven't shown that your algorithm works, is efficient or even
terminates. I'd say Greg has valid reason to disagree with your
polynomial time claim.
> Now, factoring is in general hard, with *certain* types of numbers,
> while not necessarily so with others.
The GNFS would disagree. It can factor ANY number in sub-exponential
time. There are no "harder than average" numbers. Now specially
constructed [e.g. smooth or narrow DoS] composites can be factored in
quick average time those same algorithms (like Fermats) have a large
theta function and their big-oh is nasty.
> My surrogate T, is offset from M, the target by the formula
>
> T = M^2 - j^2
>
> which factors somewhat, immediately into
>
> T = (M-j)(M+j)
>
> where for positive j, M-j is necessarily less than M, and M+j can be
> *given* whatever factor you wish by picking j appropriately, so that
> you can factor it immediately to shrink the number.
You have yet to show how you pick M and j efficiently. If you could
show it then people would be out breaking RSA left right and center.
> There are any number of smart things you can do when you can have as
> much control as my method gives.
But your description is not complete. And what we DO know about it so
far is not new.
> Now I don't see posters talking about that, as you're not interested
in
> the mathematics or what's possible, but only in trying to dismiss my
> discovery.
That's because so far you haven't shown anything that is new or worthy
of the attention you are craving.
People aren't just telling you to factor RSA challenges to shut you up.
They're doing it to show to you that you're wrong. If your method
worked was well as you claimed you'd be factoring RSA sized composites
and getting a lot of attention.
> But you're wasting your time, as mainstream mathematicians will try
to
> ignore it anyway, no matter what you do, so your effort is pointless.
I suspect Greg doesn't have a lot of time, thought or otherwise
invested in this thread. [Nor do many others].
> > method cannot be polynomial time. Now, if it's
> > subexponential, it could still be interesting, but
> > you haven't argued for that, either.
> >
>
> There are only so many factoring methods known, even inefficient
ones,
> while certain key features of my discovery make it very exciting, and
> make it definite that an inefficiency claim at this point is
> short-sighted.
>
> That you jump to a conclusion isn't a surprise to me.
Well given that you haven't shown otherwise what conclusion would you
have them "jump to"? Are you suggesting it's smarter to assume your
method works perfectly?
> You just have something you wish to believe and can't pause for even
a
> moment to let facts gather before you jump in with your opinion, even
> when it defies the mathematics.
Why would it defy mathematics? Either your algorithm works or it
doesn't. There is no magic here.
> I, on the other hand, have worked out a lot of the theory, and the
> theory says that this factoring method is in fact a solution to the
> factoring problem.
You have yet to demonstrate that you understand the principles of the
scientific process. So far I haven't seen a single theory written by
you. You say "I have theories" yet all you write in usenet is
self-serving accusations of persecution and random equations that
aren't "rational". equations are not theories!!!
The fact that you can't implement your algorithm [because you're lazy,
incapable or it just doesn't work] would tend to suggest otherwise.
> That is a statement of mathematical fact. If you don't believe it's
> mathematical fact then you have the route of proving your disbelief
> mathematically.
What is? You haven't written any proofs let alone theories to support
your claim that anything you're saying here has any shred of truth to
it.
> There are a LOT of little proofs that I've ran through at this point
in
> order to come to my conclusion, many of them extraordinary in terms
of
> what the mathematics shows MUST be true.
... psst why not share your "proofs" with the group?
> For that reason, I can confidently state--before there's an
> implementation that I know of which shows this--that the factoring
> problem has been solved and it's now just a matter of time before the
> implementation demonstrating that is out there.
What are you doing talking on usenet then? Get coding!
> You can debate about it all you want, but like I said earlier today,
> I'm just goofing off, as the hard theoretical work--I think--is done.
Then you're sadly mistaken.
If you want to raise yourself above crankdome [which I doubt you do]
then you would just shut up, write a proper paper, implement the
algorithm and get published. Instead you'll ramble on usenet, accuse
people of wild things and plague the earth.
> In the end, the real world will determine the truth as factoring is
> important in the real world, and your opinions, thoughts or feelings
> have no impact here.
Then why are you sharing them?
> In the meantime, sure, chattering about it can be fun, but it's not
> substantive.
Dude, nothing you produce [at least here] is impactful. If you stopped
posting for a week people would begin to forget you and after a month
you'd be a fading memory in many peoples minds.
People remember Fermat [in this case] because he was capable of
actually respecting others and writing cogent papers/ideas down for
others to read.
You think if Fermat wrote "I can factor, see m = t^2 -j^2 see see I can
factor in polynomial time!!!" that anyone would take him serious?
... posting because I wanted to read TAOCP for a bit ;-)
Tom
Wouldn't that depend on the size of his margin?
I must inform you that people here are meeting in the secret
crypto group and discussing ways to steal your discoveries.
They are ruthless and greedy. Do not disclose your discoveries
here. Take the RSA money now, and ask questions later. Good
luck.
Hmm, let me try that.
"Did I find a new way to turn seawater into beer, or not? If I did
not, then if you're a reasonable person you should require that
someone PROVE I did not."
Nope. Everyone wants free beer. If I claim I have a way to make it,
I think I'm the one who has to prove something.
Well, I'd say that's more false than true. Consider the
following recipe:
define Split(n):
Loop_Until_Return:
m = Choose_another_positive_integer
g = Greatest_common_divisor(n, m)
if g not in {1, n}:
return g
define Factor(n):
Comment: We assume n is an integer greater than one.
if is_prime(n):
return n
else:
m = Split(n)
return Factor(m), Factor(n / m)
The recipe provides a distinct factoring method for every
distinct Choose_another_positive_integer method.
> Do mathematicians or do they not have a duty to acknowledge and report
> a new way to factor?
Obviously not. By following the recipe, we can create a new way
to factor every few minutes. Methods have to show some
significant promise before they justify acknowledgement.
--
--Bryan
It seems that you did not. At least not nwe, and not better.
> If I did, then no matter what your personal feelings about me, then you
> probably figure that mathematicians have a *duty* to report a new way
> to factor.
Mathematicians have no such duty to report anything. They are free to focus
on thier area of interest.
> If I did not, then if you're a reasonable person you should require
> that someone PROVE I did not.
No. The onus is on you to prove it. You have not done that. Nobody else is
required to disprove it.
> Do mathematicians or do they not have a duty to acknowledge and report
> a new way to factor?
Of course not.
> Should a find of a new way to factor be acknowledged by mainstream
> mathematicians?
Only if yo provide a proof.
> Do you really think just *anybody* can find a new way to factor?
> Could you?
Could you? You have not done that yet.
Ha ha... Well, Fermat probably did fib a bit in his margin... once... But he
also did a bit more good stuff than James!
Phttttttt! Thanks a lot buster!!!!!
Funny. I'm kind of drifting for the moment, so I'm cruising along to
look at posts and see how creative you people got.
Somewhat creative I'd say.
I quit worrying about people stealing my discoveries a long time ago.
I talk out ideas. Yes, I know you people hate it when someone talks
out ideas, and you make excuses for hating free speech by claiming I'm
just immensely obnoxious or something creating all these threads.
But the reality of Usenet is that you can ignore those threads.
I talk out math ideas on Usenet, and people give me grief for it.
My claims are ones that I PROVE mathematically.
The reality about people who get upset about my posting is that they
are busybodies, worrying about another Usenet poster not following
rules they make up, when I'm just doing what you do on Usenet--post.
The reality is that you people are the ones who are weird, not me.
Sure, a burst of postings and threads from someone you don't like can
annoy you, but if you care more about the rules of the road of the
medium, than your personal feelings then you can just let it go, or
make posts that I can happily jump on as silly.
After all, eventually I just get bored with posting and wander off to
do something else, and replying to me with silly stuff doesn't shorten
that period.
People ordering me to stop posting don't shorten that period.
People making fun of my postings don't shorten that period.
I've been posting for years, and I've been rather consistent in posting
as I see fit.
So then, you can post as you see fit if you wish, and make posts that
will not have an impact, except maybe they'll satisfy my need to post
more as I step in to make a post like this one, trying to inform you
about the basics of Usenet, but other than that, you're just engaging
in futile behavior, if your intent is to influence whether or not I
post.
But, I understand that your intent is really to do what I'm
doing--post.
So, then, it is all in the spirit of Usenet, right?
James Harris
psst. I have a good way to make free beer. First you grow some hops
then you grow some barley then you add water and let ferment.
All you have to do is buy some land to grow hops and barley and work
really hard. Oh wait I guess it really isn't free.
Leslie 'Mack' McBride
remove text between _ marks to respond via e-mail
Greetings!
Volker
Exit strategy? I don't need an exit strategy.
Are you laboring under the misapprehension that I care what you people
think?
I talk out math problems on Usenet. And I'm getting ready to maybe
talk out some more as I may end my little break and try to figure out
the latest issues with my surrogate factoring method.
James Harris
What you need is a round red nose and big shoes. That's what clowns wear.
> Are you laboring under the misapprehension that I care what you people
> think?
Of course not! Why should you? You are a clown - clowns are supposed to
be laughed at.
...
>I talk out math ideas on Usenet, and people give me grief for it.
In general they are bad ideas.
>My claims are ones that I PROVE mathematically.
No, they are not. You have claimed that factoring in polynomial time is a solved
problem. You have not proven it.
Even if they were, so what?
It's Usenet.
I think some of you don't understand the concepts behind Usenet, like
free speech and talking out problems if you wish.
I'm in the subject area.
That's all that's needed.
> >My claims are ones that I PROVE mathematically.
>
> No, they are not. You have claimed that factoring in polynomial time
is a solved
> problem. You have not proven it.
Theory versus implementation.
I have theoretically solved the problem.
It's the implementation that's behind, but moving at light speed.
It's like if congruence of squares were discovered one month, and the
theory developed to the Number Field Sieve the next.
And an implementation coming soon thereafter.
Speed at this level is simply unheard of.
You people simply don't know enough to realize what you're witnessing.
You're too dumb about the real world of mathematical research and
development to understand that progress like this typically occurs over
decades, not days.
I'm moving from theory to implementation at an incredible
rate...sigh...why bother explaining? You won't believe me.
Small minds.
James Harris
> It's Usenet.
>
> I think some of you don't understand the concepts behind Usenet,
Sure he does. We all do know that even clowns, like you, have the right
to display their ignorance in front of everybody.
> You're too dumb about the real world of mathematical research and
> development to understand that progress like this typically occurs over
> decades, not days.
So, the clown can talk philosophy, right?
> I'm moving from theory to implementation at an incredible
> rate...sigh...why bother explaining? You won't believe me. Small minds.
You should know: yours is the smallest one.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
You have never heard of Einstein and the theory of relativity?
According to Einstein nothing can move faster than the speed of light
- - the speed your implementation is moving. Therefore it follows that
your theory must be moving slower and is perhaps yet to shine on us.
(it makes you wonder about relativity and the big bang too - if we
are looking back into deep space at the moment before the big-bang
then we must have moved faster than the speed of light)
-----BEGIN PGP SIGNATURE-----
Version: PGP 8.1
iQA/AwUBQfzbQJS9Fk5okqe7EQI/gQCfZdjr8UbpPaqF0wfEQIWd9WkExMMAoK3j
Pc4OmBMJ9jYrU/aL2SkTSjKB
=pKzl
-----END PGP SIGNATURE-----
> method. ... it's FINDING THE RELATION [the two squares] that consumes
> all of the time in current factoring methods. Once you have x^2 == y^2
> [x != y] you can factor trivially.
Minor typo: you mean x != +- y mod N.
Paul
--
Hanging on in quiet desperation is the English way.
The time is gone, the song is over.
Thought I'd something more to say.
Generally it's considered impolite to repeatedly suggest the same wrong
idea.
> It's Usenet.
>
> I think some of you don't understand the concepts behind Usenet, like
> free speech and talking out problems if you wish.
Actually this is where you are wrong. Usenet is a DISCUSSION tool not
a "telling it as it is" tool. You don't do anything that encourages
rational discussion of your play time ... cough ... work.
> I'm in the subject area.
Maybe on the surface. You certainly don't accept, acknowledge or make
use of any previously established, theory, practice, dogma or just
common curtesy.
> That's all that's needed.
So you're saying just because you hint at math you can say whatever you
want no matter how incorrect and it's "all that's needed". And then
you wonder why nobody takes you serious...
> > >My claims are ones that I PROVE mathematically.
> >
> > No, they are not. You have claimed that factoring in polynomial
time
> is a solved
> > problem. You have not proven it.
>
> Theory versus implementation.
WHAT THEORY??? You haven't even stated a complete [nor acceptable]
theorem yet. And an implementation of a theorem isn't always a proof.
> I have theoretically solved the problem.
You realize that this doesn't mean the problem is solved right? It
means that based on some theory you haven't proven the problem [which
you haven't stated] has been solved.
Of course if you attended elementary and high school science classes
you'd know how to at least approach the subject with a bit of
scientific finesse....
> It's the implementation that's behind, but moving at light speed.
Really? I haven't seen a working implementation yet. That's more like
James-Speed. Otherwise known as "speed of new usenet threads to get
attention".
> It's like if congruence of squares were discovered one month, and the
> theory developed to the Number Field Sieve the next.
... I know enough of the number field sieve to tell you it's not solely
based on the DoS factoring method (of how it sieves for relations). It
took a lot more theory than just that.
Also your ... um ... algorithm??? [... which you have yet to concretely
specify and analyze...] from all looks on usenet is just DoS related
method. ... it's FINDING THE RELATION [the two squares] that consumes
all of the time in current factoring methods. Once you have x^2 == y^2
[x != y] you can factor trivially.
> You're too dumb about the real world of mathematical research and
> development to understand that progress like this typically occurs
over
> decades, not days.
... and most people write proper papers in which they evolve their line
of thinking properly. A dozen or so equations pulled out your arse
make not a paper indeed.
... Feeding the troll so he'll post another day. ;-)
Tom
> I talk out math problems on Usenet.
And why not just in front of a mirror?
Greetings!
Volker
> > >My claims are ones that I PROVE mathematically.
> > No, they are not. You have claimed that factoring in polynomial time
> is a solved
> > problem. You have not proven it.
> Theory versus implementation.
> I have theoretically solved the problem.
You haven't published a proof that stands up to public scrutiny
and you haven't done a non-constructive proof by implementing
a prototype.
And before you go on about your proofs, something counts as proven
when the proof is accepted, not when you feel you've proven something.
Look up the history of the proof of fermats last theorem to see how the
real world works.
> It's the implementation that's behind, but moving at light speed.
Do you imply it can't be long before you have a functioning
implementation? If yes, how long?
>
> It's like if congruence of squares were discovered one month, and the
> theory developed to the Number Field Sieve the next.
> And an implementation coming soon thereafter.
> Speed at this level is simply unheard of.
That depends. If someone had discovered the congruence of squares,
saw a pressing need for the number sieve for a cryptographic implementation
and had a rough idea how this all hangs together (as you claim it for your
discovery as far as I understand it) it *would* have happened faster.
> You people simply don't know enough to realize what you're witnessing.
> You're too dumb about the real world of mathematical research and
> development to understand that progress like this typically occurs over
> decades, not days.
Programming a bunch of equations is definitely not hard. You seem to
not know enough about the world of scientific computing to understand
that getting an implementation of a mathematical construct isn't that hard
anymore. (In fact hasn't been since the invention of FORTRAN and has
become MUCH easier with the advent of Maple, MatLab etc..)
> I'm moving from theory to implementation at an incredible
> rate...sigh...why bother explaining?
Very good question. And your answer is?
>You won't believe me.
We will believe you as soon as you're finished.
Lots of Greetings!
Volker