Search   Memberlist   Usergroups
 Page 3 of 3 [37 Posts] View previous topic :: View next topic Goto page:  Previous  1, 2, 3
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

 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 pq-A quite small.

Now, suppose

A = (p-x)*(q-y)

then

A = pq-py-qx+xy

so

qx-xy = pq-py-A

so

x(q-y) = pq-A-py

so

x = (pq-A-py)/(q-y)

Now, pq-A is quite small, so it is just a question of finding y to
make (pq-A-py)/(q-y) a whole number.

--
Clive Tooth
www.clivetooth.dk
Stock photos:
http://submit.shutterstock.com/?ref=61771
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
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

 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/
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 100r-100v)
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.

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
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...

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 x-coordinates of the point(s) of intersection will
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
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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 3 of 3 [37 Posts] Goto page:  Previous  1, 2, 3 View previous topic :: View next topic
 The time now is Tue Oct 23, 2018 1:10 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Crackpot factoring scheme? Dann Corbit Math 1 Thu Jul 20, 2006 10:56 pm Help in identifying a numerical method Don11135 num-analysis 2 Thu Jul 20, 2006 8:56 pm troubles in determination of specific surface area(air pe... eos Chem 0 Thu Jul 20, 2006 10:05 am troubles in determination of specific surface area(air pe... eos Chem 0 Thu Jul 20, 2006 10:02 am possible to use Generalized Method of Moments for this pr... comtech Math 1 Thu Jul 20, 2006 12:49 am