Author 
Message 
The Last Danish Pastry science forum Guru Wannabe
Joined: 29 Apr 2005
Posts: 176

Posted: Wed Jul 19, 2006 9:42 am Post subject:
Re: SF: Definitely a new factoring method



<jstevh@msn.com> wrote in message
news:1153268510.758002.204450@p79g2000cwp.googlegroups.com...
Quote:  I will admit that if factoring methods are easy to come up with then
I'd be very interested in seeing people do it.

Here's one I came up with.
Suppose I want to factorize a number: A.
I choose two numbers p and q such that pq>A.
And I chose p and q so as to make pqA quite small.
Now, suppose
A = (px)*(qy)
then
A = pqpyqx+xy
so
qxxy = pqpyA
so
x(qy) = pqApy
so
x = (pqApy)/(qy)
Now, pqA is quite small, so it is just a question of finding y to
make (pqApy)/(qy) a whole number.

Clive Tooth
www.clivetooth.dk
Stock photos:
http://submit.shutterstock.com/?ref=61771 

Back to top 


Justin science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 204

Posted: Wed Jul 19, 2006 10:11 am Post subject:
Re: SF: Definitely a new factoring method



In sci.math jstevh@msn.com wrote:
: Well I've thought about factoring for over three years now, and come up
: with various approaches along the lines of what I call surrogate
: factoring, and also found proofs for almost every one but this latest
: that showed that none could work efficiently.
The fact that none of your methods has ever factored anything of any
consequence is proof enough that they're not efficient. This is not to
say that they've been mathematically proved to be inefficient, just that
nobody should feel the least bit pressured to prove anything about your
approaches given your track record.
: Just for my own curiosity then, as someone who plays with this stuff a
: lot, I'd like to see you come up with just one new factoring method.
Here's one I posted about three months ago but you ignored: Let T be the
target. Assume T is odd. Let S=2T. Pick x a factor of S other than 2.
Voila, a factor of T.
Now, you may say that this is stupidly trivial but I'd like to point out
that it has all the hallmarks of your approaches. It takes something hard
to factor, T, introduces a new variable x with no guidance as to how to
choose x, and then it goes on to show that if x can be found then I'm home
free.
Like you I could then go on to say that it's not up to me to implement it
(maybe Tim Peters can do it) and it's not up to me to prove it's
inefficient. It works, as you say, and I could therefore claim it's all
about the pure math.
Is it new? I challenge you to find one single reference to it in the
literature.
Justin 

Back to top 


Dik T. Winter science forum Guru
Joined: 25 Mar 2005
Posts: 1359

Posted: Wed Jul 19, 2006 11:28 am Post subject:
Re: Definitely a new factoring method



In article <e_ydnX4Clq9MAyDZnZ2dnUVZ_qednZ2d@comcast.com> "Tim Peters" <tim.one@comcast.net> writes:
Quote:  [Dik T. Winter]
Yes, back to the drawing board, but I think it is a great idea. How
about:
....
Yup, that's more like it! Although "when done" is a bit baffling, since
there's no way out of the loop

Oh, well, you must leave something out of the specification if you want
to follow the lead.
Quote:  No beer for us today ;)
Eh, no *free* beer (I write, lurking my pint; yes the glass comes from the
UK, where they have real pints). I am wondering how I would have received
my free beer. Paypal?
I suspect gjedwards was lying. Not surprising, since he seems to be one of
those math guys. We'll just have to see whether mensator gets the beer he
should win for Collatz factoring.

Ah, yes, another new method. So now there are already two new methods in
two days. If more work is done we could have thousands of methods by the
end of the year. And we should write the NSA about it. And all should
become rich and famous.
Quote:  BTW, about horribly complicated. I once wrote a C program that did all
operations on integers by implementing the Peano axioms. It did work,
and it was fun, but horribly slow.
Will, if the algorithm above is the slowest way to factor you can think of,
you need to get back in practice

Oh, no, I think that I can come up with slower methods.

dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/ 

Back to top 


Wayne Brown science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 143

Posted: Wed Jul 19, 2006 7:17 pm Post subject:
Re: SF: Definitely a new factoring method



In sci.math jstevh@msn.com wrote:
Quote: 
It has been shown to work by a Tim Peters, who has also been certain
that it can't be made practical, but that is irrelevant to the question
of it definitely being a new factoring method.

I've invented a new type of engine for my car. It's a sort of catapult
that sits in the driveway and throws boulders at the back of the car.
Each time it's hit by a boulder the car rolls forward a few feet.
It's slow, works only over a short distance, and the wear and tear on
the car is rather severe  but that is irrelevant to the question of
it definitely being a new method of propelling a car.
How long do you suppose it will be before the car manufacturers start
lying about it to suppress my "discovery?"

Wayne Brown <fwbrown@bellsouth.net> (HPCC #1104)
Þæs oferéode, ðisses swá mæg. ("That passed away, this also can.")
 Deor, from the Exeter Book (folios 100r100v) 

Back to top 


jstevh@msn.com science forum Guru
Joined: 21 Jan 2006
Posts: 951

Posted: Thu Jul 20, 2006 4:59 am Post subject:
Re: SF: Definitely a new factoring method



Justin wrote:
Quote:  In sci.math jstevh@msn.com wrote:
: Well I've thought about factoring for over three years now, and come up
: with various approaches along the lines of what I call surrogate
: factoring, and also found proofs for almost every one but this latest
: that showed that none could work efficiently.
The fact that none of your methods has ever factored anything of any
consequence is proof enough that they're not efficient. This is not to
say that they've been mathematically proved to be inefficient, just that
nobody should feel the least bit pressured to prove anything about your
approaches given your track record.

It turns out that I had other approaches which DID factor ok to some
extent.
But they weren't up to the standard I have of being able to factor an
RSA number in 10 minutes or less on a home pc, so I dropped them.
I've dumped factoring ideas which were not terribly bad because I knew
they wouldn't meet that standard.
Quote:  : Just for my own curiosity then, as someone who plays with this stuff a
: lot, I'd like to see you come up with just one new factoring method.
Here's one I posted about three months ago but you ignored: Let T be the
target. Assume T is odd. Let S=2T. Pick x a factor of S other than 2.
Voila, a factor of T.
Now, you may say that this is stupidly trivial but I'd like to point out
that it has all the hallmarks of your approaches. It takes something hard
to factor, T, introduces a new variable x with no guidance as to how to
choose x, and then it goes on to show that if x can be found then I'm home
free.

You have no idea what you're talking about. I've had implemented
algorithms that were not horrible, but they didn't excite me.
Your problem I think is that you want to believe something is true
which is not.
Again, the standard for me in factoring approaches is being able to
factor an RSA number in 10 minutes or less on a home pc.
Anything beneath that I drop.
I can do all kinds of things with mathematics, but I have to feel
really good about any approach before I keep it.
I've tossed more decent mathematical ideas than most people can ever
come close to finding, but they didn't meet my standards.
So as far as I'm concerned, they weren't worth my time.
After all, there are an infinity of other ideas out there, so why not
get EXACTLY what I want?
James Harris 

Back to top 


Felicis@gmail.com science forum beginner
Joined: 19 Jul 2006
Posts: 4

Posted: Thu Jul 20, 2006 6:17 am Post subject:
Re: SF: Definitely a new factoring method



Hi
Quote:  It turns out that I had other approaches which DID factor ok to some
extent.
But they weren't up to the standard I have of being able to factor an
RSA number in 10 minutes or less on a home pc, so I dropped them.
I've dumped factoring ideas which were not terribly bad because I knew
they wouldn't meet that standard.

Were they able to factor an RSA number in an hour? If so, could I have
a look? Heck  even if they factor an RSA number in a *year* on a PC,
I would love to see them!
Quote:  : Just for my own curiosity then, as someone who plays with this stuff a
: lot, I'd like to see you come up with just one new factoring method.

I have a couple (though I am *sure* they are not efficient) :)
1) The 'undoing multiplication' method:
Suppose I want to factor something small, like 91.
I know that the factors must be no more than two digits each (and more,
that one is only one digit):
x+y
* z
____
yz mod 10
10xz+yz(yzmod10)
____________
91
so: 1 = yz mod 10
That means I have the possibilities of: 1*1, 3*7, 7*3, or 9*9
if z=1, then I get the trivial 91 = 1*91
if z=7, then I get yz = 21, and 7x+2 = 9, so x=1, or 91 =7*13
(clearly z!=3, nor 9)
Of course it gets *much* more difficult as the numbers get larger (as
the number of possible cases grows very quickly). I think this method
is probably slower than trial factorization by a *lot*  can anyone
think of a more inefficient method? (Or am I wrong in my assumption of
how slow it is? I have not yet learned how to estimate algorithm
efficiencies (other than the minor bits of the error estimate for
series expansions in freshman calculus...).
2) my other method is (I think) about as fast as Fermat's factorization
method (and is what gave me the idea...
Start with your number to factor N (or T, if you prefer...)
Let's look at the parabola: y=x^2 + (N+1)x +N.
This parabola has zeros at 1 and N, and the interesting property that a
line through the origin that intersects the parabola will do so in such
a way that the xcoordinates of the point(s) of intersection will
multiply together to make N. Just start with the tangent (whose
intersection with the parabola will give you sqrt(N) (there are two,
one gives you sqrt(N) start with the other one!) Then just change
the slope of the line until you find a pair of x's that are both
integers. (Note  the slope will be integral too, so you only have to
try a finite number of cases, and it seems clear that (as with Fermat's
method), this works fastest when there are two factors near the square
root on N.
If anyone is really interested in this any further, I would be happy to
discuss some thoughts I have on limiting the choices for the slope of
that line, but I think of this as mainly a slightly interesting method
only because I came up with it on my own, and it helped me visualize
some aspects of factoring. Of course, this then led me to study more,
and then I saw how the quadratic sieve works and am now trying to get a
grip on the elliptic curve methods (which I expect to be able to
understand a little better after finishing the abstract algebra courses
I am going to be taking over the next year).
Anyways while novelty might be interesting, that does not guarantee
that it has any value.
cheers
Eric 

Back to top 


Justin science forum Guru Wannabe
Joined: 28 Apr 2005
Posts: 204

Posted: Thu Jul 20, 2006 10:16 am Post subject:
Re: SF: Definitely a new factoring method



In sci.math jstevh@msn.com wrote:
: It turns out that I had other approaches which DID factor ok to some
: extent.
I never said they didn't  I just said they weren't efficient and
efficiency is what it's all about.
: You have no idea what you're talking about. I've had implemented
: algorithms that were not horrible, but they didn't excite me.
Please explain. What's wrong with my factoring algorithm? If you can't
stick to the math then don't say anything at all.
: Again, the standard for me in factoring approaches is being able to
: factor an RSA number in 10 minutes or less on a home pc.
Sure, anyone else would love this, except neither you nor I have managed.
: After all, there are an infinity of other ideas out there, so why not
: get EXACTLY what I want?
But you haven't.
Justin 

Back to top 


Google


Back to top 



The time now is Tue Oct 23, 2018 1:10 am  All times are GMT

