Author 
Message 
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 


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 


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 


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 


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 


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 


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 


Tim Peters science forum Guru
Joined: 30 Apr 2005
Posts: 426

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



....
[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 gcding
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 ), 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 

Back to top 


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

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



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 gcding on
occasion, and you will find the primes that are factors of T.
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?
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

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



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


Back to top 


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

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



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

Posted: Tue Jul 18, 2006 10:53 pm Post subject:
Re: SF: Definitely a new factoring method



[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^2y^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)*(xy), and conversely any
factorization of T = A*B gives a solution:
x = (A+B)/2, y = (AB)/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 nontrivial 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 pT, p(x+y)*(xy), so
p(x+y) or p(xy), and either of those imply px iff py).
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 ).
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
. 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)*(zy) = S + k^2
Factor S+k^2 as the product of two integers, f1*f2, then solve
z+y = f1
zy = f2
for y and z. Then you have y directly, and get x from x=zk. 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 ?
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 

Back to top 


Chip Eastham science forum Guru
Joined: 01 May 2005
Posts: 412

Posted: Tue Jul 18, 2006 8:49 pm Post subject:
Re: SF: Definitely a new factoring method



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^2y^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)*(xy), and conversely any
factorization of T = A*B gives a solution:
x = (A+B)/2, y = (AB)/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

Posted: Tue Jul 18, 2006 7:34 pm Post subject:
Re: Definitely a new factoring method



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^i1)/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 WintersPeters 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

Posted: Tue Jul 18, 2006 7:26 pm Post subject:
Re: SF: Definitely a new factoring method



Aluminium Holocene Holodeck Zoroaster wrote:
Quote:  decimal representation of integers is a toy algebra,
so to say (x being ten and coeffiecients 09). so,
what is the method?
The BerlekampHensel 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.
BerlekampHensel 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 



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

