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 1 of 3 [37 Posts] View previous topic :: View next topic
Goto page:  1, 2, 3 Next
Author Message
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
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
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
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
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
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
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
Tim Peters
science forum Guru


Joined: 30 Apr 2005
Posts: 426

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

....

[Dik T. Winter]
Quote:
Yes, back to the drawing board, but I think it is a great idea. How
about:
Let T be the number to be factored
Set S1 = 4
Set S2 = 6
Loop
If(gcd(S1, T) != 1 you have found a factor, accumulate it
If(gcd(S2, T) != 1 you have found another factor, accumulate it
Set S1 = S1 * 3 + 1
Set S2 = S2 * 5 + 1
when done you simply go through the factors you have accumulated gcd-ing
on
occasion, and you will find the primes that are factors of T.

Yup, that's more like it! Although "when done" is a bit baffling, since
there's no way out of the loop ;-)

If anyone wants to test it (I won't explain why it works, and it sure seems
like Dik won't either Smile), note that you can change the last two lines to:

Set S1 = mod(S1 * 3 + 1, T)
Set S2 = mod(S2 * 5 + 1, T)

to bound the size of the integers needed without affecting when, or which,
factors are found.

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.

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
Back to top
Dik T. Winter
science forum Guru


Joined: 25 Mar 2005
Posts: 1359

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

In article <YLydndxa5KrXrSDZnZ2dnUVZ_vKdnZ2d@comcast.com> "Tim Peters" <tim.one@comcast.net> writes:
Quote:
[gjedwards@gmail.com]
Competition: A free beer for the best NEW factoring algorithm posted
today. Remember, efficiency doesn't matter.

[Dik T. Winter]
Set S = 11
Loop
If gcd(S, T) != 1 you have found a factor
Set S = S * 10 + 1

It is guaranteed that this will find all factors.

[Johannes Kloos]
Sadly, it seems that it cannot find a single factor of 128...

[Dik]
Sorry, yes, I missed the factor 2. Correction, it will find all
factors of odd numbers T.

It can't find factors of 5^i for any i>1 either (note that mod(S, 5) is
always 1).

Yes, back to the drawing board, but I think it is a great idea. How about:
Let T be the number to be factored
Set S1 = 4
Set S2 = 6
Loop
If(gcd(S1, T) != 1 you have found a factor, accumulate it
If(gcd(S2, T) != 1 you have found another factor, accumulate it
Set S1 = S1 * 3 + 1
Set S2 = S2 * 5 + 1
when done you simply go through the factors you have accumulated gcd-ing on
occasion, and you will find the primes that are factors of T.

Quote:
No beer for us today Wink

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?

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.
--
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
Frreita
science forum addict


Joined: 13 Jun 2005
Posts: 96

PostPosted: Wed Jul 19, 2006 12:28 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:
Justin wrote:
In sci.math jstevh@msn.com wrote:

: Ok, so now wasn't that fun! Several years of effort with lots of very
: crappy and even stupid ideas under the bridge but now there is a new
: factoring method.

Let me point something out to you. Discovering methods of factoring is
easy. Between now and lunchtime (it's 7:00am) I guarantee you that I
could come up with at least half a dozen. Most of them would be related
to yours in that they would involve the need to pick some other integers
with absolutely no guidance given whatsoever.


Well I've thought about factoring for over three years now,


And come up with NOTHING

Quote:
and come up
with various approaches along the lines of what I call surrogate
factoring,

Which does not work and cannot factro anything...........


Quote:
and also found proofs for almost every one but this latest
that showed that none could work efficiently.

you do not know what a proof is.........

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.

The problem is they would be inefficient. Now, of course you can argue
that it's the pure math which counts, not the actual workability, but in
truth nobody cares how many new factoring methods exist because they're
so
easy to create. What is important is how many of them are useful, and
yours, sir, is not useful.

Justin

snip crap


Quote:
As, why would you lie?

you asking yourself a question lier?


Quote:
James Harris
Back to top
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

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

Justin wrote:
Quote:
In sci.math jstevh@msn.com wrote:

: Ok, so now wasn't that fun! Several years of effort with lots of very
: crappy and even stupid ideas under the bridge but now there is a new
: factoring method.

Let me point something out to you. Discovering methods of factoring is
easy. Between now and lunchtime (it's 7:00am) I guarantee you that I
could come up with at least half a dozen. Most of them would be related
to yours in that they would involve the need to pick some other integers
with absolutely no guidance given whatsoever.


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.

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.

Quote:
The problem is they would be inefficient. Now, of course you can argue
that it's the pure math which counts, not the actual workability, but in
truth nobody cares how many new factoring methods exist because they're so
easy to create. What is important is how many of them are useful, and
yours, sir, is not useful.

Justin

I will admit that if factoring methods are easy to come up with then
I'd be very interested in seeing people do it.

The simple reply then is for anyone to reply with a NEW factoring
method, which means that it can't be related back to any of those
previously known.

The question is not an idle one, as if what you're saying is true, then
hey, yeah, I can see how mathematicians might claim that my new ideas
on factoring aren't that big of a deal, but if you're just saying
something, then that is troubling.

As, why would you lie?


James Harris
Back to top
Tim Peters
science forum Guru


Joined: 30 Apr 2005
Posts: 426

PostPosted: Tue Jul 18, 2006 10:53 pm    Post subject: Re: SF: Definitely a new factoring method Reply with quote

[jstevh@msn.com]
Quote:
...
The method is given a target composite T, you can search for x and y
such that

x^2 - y^2 = 0 mod T

by picking x_res and S, to solve for a variable k, where

k = S*(2*x)^{-1} mod T

and

x+k = sqrt(S+k^2 + y^2)

so finding x and y is just a matter of factoring S+k^2, so it is,
indeed, a surrogate factoring method.
...

[Rupert]
Quote:
Could you spell out exactly what the algorithm is, I'm a bit thick.
First you select x and y such that T divides x^2-y^2. Fine. Then you
select x_res and S. Will any positive integers x_res and S do? Or are
there some constraints? If so, what's the selection procedure?


[Chip Eastham]
Quote:
I'm sticking my neck out a bit here, but I think it's fair to
give JSH credit for realizing that finding x,y is the basic
goal.

Yup.

Quote:
If composite "target" T is odd (and we may as well assume so for
the purpose of integer factoring), then:

x^2 - y^2 = T

is tantamount to T = (x+y)*(x-y), and conversely any
factorization of T = A*B gives a solution:

x = (A+B)/2, y = (A-B)/2

Yup, and there's always a way to pick the free variables in James's
equations so that it ends up deducing those x and y (I spelled out specific
choices "that work" earlier today).

Quote:
On the other hand if 0 < x,y < T (x,y distinct) such that

x^2 = y^2 (mod T)

then there's a good chance gcd(x+y,T) will be nontrivial
(meaning not 1 or T).

If it's not true that

x = +/-y (modulo T)

the gcds do deliver non-trivial factors. If that congruence does hold, you
have to be lucky enough to pick x s.t. gcd(x, T) > 1 (in which case it must
also be that y shares a prime factor with T, for if p|T, p|(x+y)*(x-y), so
p|(x+y) or p|(x-y), and either of those imply p|x iff p|y).

Quote:
So if you want to understand JSH's "method", then I
think we have to ask the question, how does "picking
x_res and S, to solve for a variable k, where":

k = S*(2*x)^{-1} mod T

Note that almost all of James's writeups had

k = S*(2*x_res)^-1 mod T

instead, where x_res is what you picked. I don't know why he dropped that
in this writeup (although I encouraged him to Wink).

Quote:
x+k = sqrt(S+k^2 + y^2)

get us to values for x and y?

That's been answered fully, if you care to dig thru mountains of old posts
Wink. Briefly, let z = x+k. Then we're looking for integer z and y s.t.

z^2 = S + k^2 + y^2
or
z^2 - y^2 = (z+y)*(z-y) = S + k^2

Factor S+k^2 as the product of two integers, f1*f2, then solve

z+y = f1
z-y = f2

for y and z. Then you have y directly, and get x from x=z-k. Note that
it's possible for f1 and f2 to have different parity, in which case y and z
aren't integers; if that happens, you have to pick other values (for x_res,
S, f1 and/or f2) until f1 and f2 are both even or both odd That's not a
real hangup.

Quote:
It doesn't make much sense to me. Given S and x,
we can certainly compute k with modest effort from
the first relation. But is x "known"?

No, x is computed as above.

Quote:
Is it the same as the mysterious x_res that is picked and mentioned
no further?

x_res is supposed to be mod(x, T). James's original hope/belief was that
you could pick any x_res in [0, T) you liked, and that the x computed by the
method would satisfy

x = x_res (modulo T)

But the computations don't force that, and in fact it appears rare for that
to be true. The method might indeed be very interesting if it did have a
way to force that congruence to be true!

Quote:
Likewise given S, x, and k, there can be at most
one positive value y that satisfies the second
relationship, and if by great fortune it should occur
that (x+k)^2 - S - k^2 is an integer squared,

Note that the computation above forces y^2+S+k^2 to be a perfect square
whenever f1 and f2 have the same parity. It's not generally true that at
most one possible <x, y> pair exists for given S and k. For example, if
S=23 & k=3 then S+k^2 = 32 can be factored in 12 ways as the product of 2
integers (order matters, and +/- matters too). For example, here are two
ways:

S = 2 * 16 = f1*f2

leads to:

y = -7
z = 9
x = 0
x+k = 9
sqrt(S+k^2 + y^2) = sqrt(32 + (-7)^2) = sqrt(32 + 49) = sqrt(81) = 9


while:

S = 8 * 4 = f1*f2

leads to:

y = 2
z = 6
x = -3
x+k = 6
sqrt(S+k^2 + y^2) = sqrt(32 + 2^2) = sqrt(36) = 6

Quote:
then y is that root. [NB: For about a month JSH
was going on and on about how only he grasped
the deep significance of a (positive) integer square
having both a positive and a negative square root,
possibly imagining that everyone else in the world
has forgotten high school algebra.]

But what choice of S and x can possibly guarantee
this condition?

Pretty much any choice for x_res can be made to work, for a suitable
restricted meaning of "work".

Quote:
Even so, how would one prove that T | x^2 - y^2 ?

That's indeed the problem in practice: it's rarely true, and because

x = x_res (modulo T) [1]

is rarely true. If [1] /were/ true, then you picked S, x_res and k to
satisfy

S = 2 * x_res * k (modulo T) [2]

and found x and y such that

x^2 - y^2 = S - 2*x*k [3]

and [1] and [2] together imply that the RHS of [3] is divisible by T.

Quote:
Properly speaking, this is JSH's burden, yes?

Ya think Wink?

Quote:
But in quite typical backhanded fashion, he
acknowledges that Tim Peters showed this.

I showed a lot of things here, but the only "positive" thing from James's
POV was that there's always /some/ way to pick the free variables that work.

Quote:
Here's one approach:

x^2 - y^2 = x^2 - ((x+k)^2 - S - k^2)
= x^2 - (x+k)^2 + S + k^2
= S - 2xk

Recall that the first relation above gives:

2xk = S (mod T)

Thus we have immediately:

x^2 - y^2 = S - 2xk = 0 (mod T)

Exactly so. Alas, if you pick x first in

2xk = S (mod T)

then there's nothing to force the x computed at the /end/ to satisfy that
too.

Quote:
Hoo ha! and now the math is yours!!

And no refunds Smile
Back to top
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Tue Jul 18, 2006 8:49 pm    Post subject: Re: SF: Definitely a new factoring method Reply with quote

jstevh@msn.com wrote:

Quote:
Ok, so now wasn't that fun! Several years of effort with lots of very
crappy and even stupid ideas under the bridge but now there is a new
factoring method.

The method is given a target composite T, you can search for x and y
such that

x^2 - y^2 = 0 mod T

by picking x_res and S, to solve for a variable k, where

k = S*(2*x)^{-1} mod T

and

x+k = sqrt(S+k^2 + y^2)

so finding x and y is just a matter of factoring S+k^2, so it is,
indeed, a surrogate factoring method.
[snip]


Rupert wrote:

Quote:
Could you spell out exactly what the algorithm is, I'm a bit thick.
First you select x and y such that T divides x^2-y^2. Fine. Then you
select x_res and S. Will any positive integers x_res and S do? Or are
there some constraints? If so, what's the selection procedure?

I'm sticking my neck out a bit here, but I think it's fair to
give JSH credit for realizing that finding x,y is the basic
goal. If composite "target" T is odd (and we may as well
assume so for the purpose of integer factoring), then:

x^2 - y^2 = T

is tantamount to T = (x+y)*(x-y), and conversely any
factorization of T = A*B gives a solution:

x = (A+B)/2, y = (A-B)/2

On the other hand if 0 < x,y < T (x,y distinct) such that

x^2 = y^2 (mod T)

then there's a good chance gcd(x+y,T) will be nontrivial
(meaning not 1 or T).

So if you want to understand JSH's "method", then I
think we have to ask the question, how does "picking
x_res and S, to solve for a variable k, where":

k = S*(2*x)^{-1} mod T

x+k = sqrt(S+k^2 + y^2)

get us to values for x and y?

It doesn't make much sense to me. Given S and x,
we can certainly compute k with modest effort from
the first relation. But is x "known"? Is it the same as
the mysterious x_res that is picked and mentioned
no further?

Likewise given S, x, and k, there can be at most
one positive value y that satisfies the second
relationship, and if by great fortune it should occur
that (x+k)^2 - S - k^2 is an integer squared, then
y is that root. [NB: For about a month JSH
was going on and on about how only he grasped
the deep significance of a (positive) integer square
having both a positive and a negative square root,
possibly imagining that everyone else in the world
has forgotten high school algebra.]

But what choice of S and x can possibly guarantee
this condition?

Even so, how would one prove that T | x^2 - y^2 ?
Properly speaking, this is JSH's burden, yes?
But in quite typical backhanded fashion, he
acknowledges that Tim Peters showed this.

Here's one approach:

x^2 - y^2 = x^2 - ((x+k)^2 - S - k^2)
= x^2 - (x+k)^2 + S + k^2
= S - 2xk

Recall that the first relation above gives:

2xk = S (mod T)

Thus we have immediately:

x^2 - y^2 = S - 2xk = 0 (mod T)

Hoo ha! and now the math is yours!!

regards, chip
Back to top
gjedwards@gmail.com
science forum addict


Joined: 20 May 2006
Posts: 70

PostPosted: Tue Jul 18, 2006 7:34 pm    Post subject: Re: Definitely a new factoring method Reply with quote

Chip Eastham wrote:
Quote:
Tim Peters wrote:
[gjedwards@gmail.com]
Competition: A free beer for the best NEW factoring algorithm posted
today. Remember, efficiency doesn't matter.

[Dik T. Winter]
Set S = 11
Loop
If gcd(S, T) != 1 you have found a factor
Set S = S * 10 + 1

It is guaranteed that this will find all factors.

[Johannes Kloos]
Sadly, it seems that it cannot find a single factor of 128...

[Dik]
Sorry, yes, I missed the factor 2. Correction, it will find all
factors of odd numbers T.

It can't find factors of 5^i for any i>1 either (note that mod(S, 5) is
always 1). You're trying S of the form (10^i-1)/9, and integer k divides
that if and only if

(10^i - 1)/9 = 0 (modulo k)
iff
10^i = 1 (modulo 9*k)

for some i >= 2. k=2^x*5^y isn't coprime to 10 when x>0 or y>0, so no such i
exists in those cases (M has a multiplicative order to base B iff M and B
are coprime).

There's also a problem with:

If gcd(S, T) != 1 you have found a factor

since it's possible for the gcd to /be/ T. For example, that obviously
happens at T=111. Less obviously, at T=91.

So you might hope that that Winters-Peters Wink Conjectured Miracle Factoring
Algorithm is:

if mod(T, 2) == 0:
return 2
if mod(T, 5) == 0:
return 5
S = 11
loop:
g = gcd(S, T)
if 1 < g < T:
return g
S = S * 10 + 1

Alas, that's still not right, at least because it still fails to factor 111.
S modulo 3 and 37 cycle through these values:

mod(S, 3) mod(S, 37)
--------- ----------
2 11 so gcd(S, 111) = 1
0 0 so gcd(S, 111) = 111
1 1 so gcd(S, 111) = 1
2 11 and the cycle starts repeating here

Tim wrote:

No beer for us today ;-)

Bartender, a round of pints for my sci.math colleagues
to cry in!

-- chip

The beer, for the winner and the best loser will be served at your
nearest branch of 'Hooters' tonight. To claim the prize just explain
the above algorithms and subsequent analysis to the barmaid on duty.
Back to top
Chip Eastham
science forum Guru


Joined: 01 May 2005
Posts: 412

PostPosted: Tue Jul 18, 2006 7:26 pm    Post subject: Re: SF: Definitely a new factoring method Reply with quote

Aluminium Holocene Holodeck Zoroaster wrote:

Quote:
decimal representation of integers is a toy algebra,
so to say (x being ten and coeffiecients 0-9). so,
what is the method?

The Berlekamp-Hensel method applies to polynomial
factoring. JSH is dealing with the problem of integer

-- it takes some to jitterbug!

Not fully sure of your point, but if you can factor the
polynomial in indeterminate X with coefficients digits
of N, then yes, this gives integer factors of N.

The converse fails, but it would be worth investigating
(and surely someone has) how likely it is a near prime
N gives rise to an irreducible polynomial in this way.

Berlekamp-Hensel has exponential complexity, but
there are substantially more efficient algorithms for
factoring univariate polynomials. So I suspect the
drawback in such an approach is that even varying
the radix gives poor chances of discovering integer
factors.

regards, chip
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 3 [37 Posts] Goto page:  1, 2, 3 Next
View previous topic :: View next topic
The time now is Fri May 25, 2018 4:25 pm | 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.0289s ][ Queries: 16 (0.0024s) ][ GZIP on - Debug on ]