FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
SF: Definitely a new factoring method
Post new topic   Reply to topic 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

PostPosted: Wed Jul 19, 2006 9:42 am    Post subject: Re: SF: Definitely a new factoring method Reply with quote

<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 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
Back to top
Justin
science forum Guru Wannabe


Joined: 28 Apr 2005
Posts: 204

PostPosted: Wed Jul 19, 2006 10:11 am    Post subject: Re: SF: Definitely a new factoring method Reply with 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.

: 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

PostPosted: Wed Jul 19, 2006 11:28 am    Post subject: Re: Definitely a new factoring method Reply with quote

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 Wink

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 Smile

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

PostPosted: Wed Jul 19, 2006 7:17 pm    Post subject: Re: SF: Definitely a new factoring method Reply with quote

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 oferode, isses sw mg. ("That passed away, this also can.")
-- Deor, from the Exeter Book (folios 100r-100v)
Back to top
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

PostPosted: Thu Jul 20, 2006 4:59 am    Post subject: Re: SF: Definitely a new factoring method Reply with quote

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

PostPosted: Thu Jul 20, 2006 6:17 am    Post subject: Re: SF: Definitely a new factoring method Reply with quote

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 x-coordinates 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

PostPosted: Thu Jul 20, 2006 10:16 am    Post subject: Re: SF: Definitely a new factoring method Reply with quote

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
Display posts from previous:   
Post new topic   Reply to topic 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
Forum index » Science and Technology » Math
Jump to:  

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

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0166s ][ Queries: 16 (0.0024s) ][ GZIP on - Debug on ]