Search   Memberlist   Usergroups
 Page 1 of 2 [27 Posts] View previous topic :: View next topic Goto page:  1, 2 Next
Author Message
Mike1161

Joined: 14 Oct 2005
Posts: 50

Posted: Thu Jul 13, 2006 2:39 am    Post subject: Re: Loose connectivity, factoring and residues

 Quote: The factoring problem can be easily approached using simple algebra. .... For instance if T=35, and I use x_res=S=1, then k = 18 mod 35, and k=18 will suffice. Then y is found by factoring (1+18^2)/4 and then you have x as well. And how does one factor ( 1 + 18^2 ) / 4 = 81.25 ?

Mike
Tim Peters
science forum Guru

Joined: 30 Apr 2005
Posts: 426

Posted: Thu Jul 13, 2006 8:34 pm    Post subject: Re: Loose connectivity, factoring and residues

[jstevh@msn.com]
 Quote: The factoring problem can be easily approached using simple algebra. ... For instance if T=35, and I use x_res=S=1, then k = 18 mod 35, and k=18 will suffice. Then y is found by factoring (1+18^2)/4 and then you have x as well.

[Mike]
 Quote: And how does one factor ( 1 + 18^2 ) / 4 = 81.25 ?

Because James never tries his "factoring methods", he never tries to follow
his own instructions, so often says things that are incomprehensible.

However, because he repeats ideas, it's sometimes possible to guess what he
intended to say. Here the mysteries stem from his:

[JSH]
...
so

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

and finding y is just a matter of factoring (S+k^2)/4

As written, that's utterly senseless. What he probably intended is more
like this (because he's done "stuff like this" over & over before):

[not JSH, but probably intended]
...
so

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

Assume S and k are known (we'll get to those later). How can we
find integer y such that sqrt(y^2 + S + k^2) is also an integer?
Let z^2 = y^2 + S + k^2, so that:

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

Then try different ways of factoring S+k^2 as a product of two
integers, f1*f2. If the system of linear equations

z+y = f1
z-y = f2

has integer solutions for z and y, then all the equations are
satisfied with integers, and x+k = z is trivially solved for x
then.

Of course dividing by 4 has nothing to do with this, although factors of 2
show up in the denominators of the _solutions_ to that little system of
equations.

In the specific example, one way to factor 325 is as 25*13. Then solving:

z+y = 25
z-y = 13

gives z=19 and y=6, and, indeed, it's true that:

19 = sqrt(6^2 + 1 + 18^2) = sqrt(361)

Then solving x+18=19 gives x=1. Finally,

gcd(x+y, T) = gcd(1+6, 35) = 7
and
gcd(x-y, T) = gcd(1-6, 35) = 5

do reveal the factors of T.

James _hopes_ this will always be true. Of course it isn't. Now that you
know what he (probably) intended to say, you can figure out why for
yourself. James won't until he tries larger examples and discovers for
himself that he can't make it work without enormously increasing effort as T
gets larger (he can't see his own mistakes, and generally won't listen to,
or can't follow, explanations).

For a little example, pick T=187=11*17, S=1, x_res=1 (same as James picked
except for T), so that k=94. Oops. No way of factoring 1+94**2 leads to a
factor of T then.

If he ever gets to that stage, he'll start adding more searches ("OK, if
that fails, try another S ... or try another x_res ... or try adding
multiples of T to this, that, or the other ..."). But he won't _try_ any of
those either -- to judge from his consistent actions, he doesn't actually
care whether one of his methods works efficiently (anyone who cared would
try it! hell, you couldn't _stop_ them from trying it). Instead he's
downright eager to settle for just believing it does.
jstevh@msn.com
science forum Guru

Joined: 21 Jan 2006
Posts: 951

Posted: Fri Jul 14, 2006 12:46 am    Post subject: Re: Loose connectivity, factoring and residues

Mike wrote:
 Quote: In article <1152753182.312322.92010@m79g2000cwm.googlegroups.com>, jstevh@msn.com says... The factoring problem can be easily approached using simple algebra. ... For instance if T=35, and I use x_res=S=1, then k = 18 mod 35, and k=18 will suffice. Then y is found by factoring (1+18^2)/4 and then you have x as well. And how does one factor ( 1 + 18^2 ) / 4 = 81.25 ? Mike

The way it works is that if

f_1 * f_2 = (S + k^2)/4

you can trivially use

(f_1 + f_2)^2 = (f_1 - f_2)^2 + 4f_1*f_2

so you have then that

y = (f_1 - f_2)/2

which is the first part of the simple answer to your question.

In this case what you do is factor (1+18^2) = 325, and divide each
result by 2, so, for instance, you can have

f_1 = 65/2, then f_2 = 5/2

and y = (65 - 5)/2 = 30.

Make sense?

Notice then that 30^2 + 325 = 1225 = 35^2

so it works!!!

James Harris
Tim Peters
science forum Guru

Joined: 30 Apr 2005
Posts: 426

Posted: Fri Jul 14, 2006 1:43 am    Post subject: Re: Loose connectivity, factoring and residues

[jstevh@msn.com]
 Quote: The factoring problem can be easily approached using simple algebra. ... For instance if T=35, and I use x_res=S=1, then k = 18 mod 35, and k=18 will suffice. Then y is found by factoring (1+18^2)/4 and then you have x as well.

[Mike]
 Quote: And how does one factor ( 1 + 18^2 ) / 4 = 81.25 ?

[jstevh@msn.com]
 Quote: The way it works is that if f_1 * f_2 = (S + k^2)/4 you can trivially use (f_1 + f_2)^2 = (f_1 - f_2)^2 + 4f_1*f_2 so you have then that y = (f_1 - f_2)/2

Much easier to say

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

and then formally solve

z+y = f_1
z-y = f_2

for y and z. You get the same expression for y in the end, but no farting
around with artificial factors of 4 or 2 is needed. Either way, it's stuck
if f_1 and f_2 don't have the same parity.

 Quote: which is the first part of the simple answer to your question. In this case what you do is factor (1+18^2) = 325, and divide each result by 2, so, for instance, you can have f_1 = 65/2, then f_2 = 5/2 and y = (65 - 5)/2 = 30. Make sense? Notice then that 30^2 + 325 = 1225 = 35^2 so it works!!!

LOL -- you can't even finish factoring 35, James? See my other post in this
thread for how to do it _using your method_ (which is more than you've been
able to do with it, so don't complain).

The way you picked here doesn't work if you _finish_ it. After finding y =
30, you get x = 35-k = 35-18 = 17, and, just to check,

x^2 - y^2 = 17^2 - 30^2 = -611
S - 2*x*k = 1 - 2*17*18 = -611

So, yes, they are the same. But

gcd(x+y, T) = gcd(17+30, 35) = gcd(47, 35) = 1
and
gcd(x-y, T) = gcd(17-30, 35) = gcd(-13, 35) = 1

are both useless. Huh. Especially note that x=17 is _not_ congruent to
your x_res=1 modulo 35, and that x^2-y^2 = -611 = 19 modulo 35 is not
congruent to 0. But they're all numbers _you_ picked, so you can't accuse
me of cheating, and if you can do the simple integer arithmetic above you

Figure out _why_ all that's true, and you'll have a start at understanding
why this method isn't useful in general. It doesn't do what you _think_ it
does "even in theory". Try factoring p*q where p and q are large primes and
it's a bona fide miracle if it's lucky enough to find a factor. As you just
showed, you can't even factor 35 without some luck (well, you didn't show it
can factor 35 at all, but I did in a different message).
jstevh@msn.com
science forum Guru

Joined: 21 Jan 2006
Posts: 951

Posted: Fri Jul 14, 2006 3:58 am    Post subject: Re: Loose connectivity, factoring and residues

Tim Peters wrote:
 Quote: [jstevh@msn.com] The factoring problem can be easily approached using simple algebra. ... For instance if T=35, and I use x_res=S=1, then k = 18 mod 35, and k=18 will suffice. Then y is found by factoring (1+18^2)/4 and then you have x as well. [Mike] And how does one factor ( 1 + 18^2 ) / 4 = 81.25 ? [jstevh@msn.com] The way it works is that if f_1 * f_2 = (S + k^2)/4 you can trivially use (f_1 + f_2)^2 = (f_1 - f_2)^2 + 4f_1*f_2 so you have then that y = (f_1 - f_2)/2 Much easier to say z^2 - y^2 = (z+y)*(z-y) = S + k^2 = f_1 * f_2 and then formally solve z+y = f_1 z-y = f_2 for y and z. You get the same expression for y in the end, but no farting around with artificial factors of 4 or 2 is needed. Either way, it's stuck if f_1 and f_2 don't have the same parity. which is the first part of the simple answer to your question. In this case what you do is factor (1+18^2) = 325, and divide each result by 2, so, for instance, you can have f_1 = 65/2, then f_2 = 5/2 and y = (65 - 5)/2 = 30. Make sense? Notice then that 30^2 + 325 = 1225 = 35^2 so it works!!! LOL -- you can't even finish factoring 35, James? See my other post in this thread for how to do it _using your method_ (which is more than you've been able to do with it, so don't complain). The way you picked here doesn't work if you _finish_ it. After finding y = 30, you get x = 35-k = 35-18 = 17, and, just to check, x^2 - y^2 = 17^2 - 30^2 = -611 S - 2*x*k = 1 - 2*17*18 = -611

Neat! But of course! There is only one way that x^2 - y^2 cannot
equal 0 mod T, as notice that S - 2*x*k does not either.

Seems to be a contradiction, but of course there is none.

James Harris
jstevh@msn.com
science forum Guru

Joined: 21 Jan 2006
Posts: 951

Posted: Fri Jul 14, 2006 4:22 am    Post subject: Re: Loose connectivity, factoring and residues

jstevh@msn.com wrote:
 Quote: Tim Peters wrote: [jstevh@msn.com] The factoring problem can be easily approached using simple algebra. ... For instance if T=35, and I use x_res=S=1, then k = 18 mod 35, and k=18 will suffice. Then y is found by factoring (1+18^2)/4 and then you have x as well. [Mike] And how does one factor ( 1 + 18^2 ) / 4 = 81.25 ? [jstevh@msn.com] The way it works is that if f_1 * f_2 = (S + k^2)/4 you can trivially use (f_1 + f_2)^2 = (f_1 - f_2)^2 + 4f_1*f_2 so you have then that y = (f_1 - f_2)/2 Much easier to say z^2 - y^2 = (z+y)*(z-y) = S + k^2 = f_1 * f_2 and then formally solve z+y = f_1 z-y = f_2 for y and z. You get the same expression for y in the end, but no farting around with artificial factors of 4 or 2 is needed. Either way, it's stuck if f_1 and f_2 don't have the same parity. which is the first part of the simple answer to your question. In this case what you do is factor (1+18^2) = 325, and divide each result by 2, so, for instance, you can have f_1 = 65/2, then f_2 = 5/2 and y = (65 - 5)/2 = 30. Make sense? Notice then that 30^2 + 325 = 1225 = 35^2 so it works!!! LOL -- you can't even finish factoring 35, James? See my other post in this thread for how to do it _using your method_ (which is more than you've been able to do with it, so don't complain). The way you picked here doesn't work if you _finish_ it. After finding y = 30, you get x = 35-k = 35-18 = 17, and, just to check, x^2 - y^2 = 17^2 - 30^2 = -611 S - 2*x*k = 1 - 2*17*18 = -611 Neat! But of course! There is only one way that x^2 - y^2 cannot equal 0 mod T, as notice that S - 2*x*k does not either. Seems to be a contradiction, but of course there is none.

Um, it occurs to me that subtlety is not a good thing in this situation
as it's highly charged politically.

The answer is that if either x or y has prime factors in common with T,
then if

x^2 - y^2 = 0 mod T

then BOTH must have that same factor, which means that

S - 2*x*k = 0 mod T

would force S to have that same factor as well, but with my example, y
ended up having 5 as a factor while S is coprime to 5, so there was
some kind of push, which only occurs in this situation.

So in terms of a factoring algorithm, it's a non-issue as if you find
that you don't get

x^2 - y^2 = 0 mod T

then, of course, that means that y has factors in common with T, so you
just pull those factors out of y, but that's not what's interesting to
me!!!

I'm fascinated by this push--why don't the conditions simply prevent y
from having some factors in common with T? Is it some kind of modular
algebra equivalent to a divide by 0 situation?

How far does it go? Where are its boundaries? It gives me some neat
mathematical ideas to ponder. No impact on a factoring solution, but
MUCH impact possibly on further understanding number theoretic
properties.

Yeah!!!

James Harris
Tim Peters
science forum Guru

Joined: 30 Apr 2005
Posts: 426

Posted: Fri Jul 14, 2006 5:14 am    Post subject: Re: Loose connectivity, factoring and residues

[jstevh@msn.com]
 Quote: ... The answer is that if either x or y has prime factors in common with T, then if x^2 - y^2 = 0 mod T then BOTH must have that same factor, which means that S - 2*x*k = 0 mod T would force S to have that same factor as well, but with my example, y ended up having 5 as a factor while S is coprime to 5, so there was some kind of push, which only occurs in this situation. So in terms of a factoring algorithm, it's a non-issue as if you find that you don't get x^2 - y^2 = 0 mod T then, of course, that means that y has factors in common with T,

No. It's in fact rare to end up with x^2 - y^2 = 0 modulo T using this
method, and gets rarer the larger T's smallest prime factor. Whether y has
factors in common with T is irrelevant to this -- it just happened to be
true in the specific example you tried. Since that's the _only_ example
you've seen worked to the end, you latched on to an accidental property and
decided "oh, that must be the reason". Simply absurd.

Here, I'll make up another example on the fly (virtually _any_ non-trivial
example will do). Say:

T = 91 = 7 * 13

Pick:

x_res = 1
S = 1

Then:

k = 46
S + k^2 = 2117 = 29 * 73

Pick:

f_1 = 73
f_2 = 29

Deduce:

z = (f_1 + f_2)/2 = 51
y = (f_1 - f_2)/2 = 22
x = z-k = 51 - 46 = 5

Check:

gcd(y, T) = gcd(22, 91) = 1
gcd(x, T) = gcd(5, 91) = 1

So _that_ excuse went away.

More checks:

z = 51 = sqrt(y^2 + S + k^2) = sqrt(2601)

x^2 - y^2 = 5^2 - 22^2 = -459
S - 2*x*k = -459

So they're the same, but -459 is congruent to 87 modulo 91, not 0.

Finally:

gcd(x+y, T) = gcd(x-y, T) = 1

so again the exercise was useless.

 Quote: so you just pull those factors out of y, but that's not what's interesting to me!!! I'm fascinated by this push--why don't the conditions simply prevent y from having some factors in common with T? Is it some kind of modular algebra equivalent to a divide by 0 situation? How far does it go? Where are its boundaries? It gives me some neat mathematical ideas to ponder. No impact on a factoring solution, but MUCH impact possibly on further understanding number theoretic properties.

does, so best if you started over from scratch.

 Quote: Yeah!!!

Indeed.
jstevh@msn.com
science forum Guru

Joined: 21 Jan 2006
Posts: 951

Posted: Sat Jul 15, 2006 12:14 am    Post subject: Re: Loose connectivity, factoring and residues

Tim Peters wrote:
 Quote: [jstevh@msn.com] ... The answer is that if either x or y has prime factors in common with T, then if x^2 - y^2 = 0 mod T then BOTH must have that same factor, which means that S - 2*x*k = 0 mod T would force S to have that same factor as well, but with my example, y ended up having 5 as a factor while S is coprime to 5, so there was some kind of push, which only occurs in this situation. So in terms of a factoring algorithm, it's a non-issue as if you find that you don't get x^2 - y^2 = 0 mod T then, of course, that means that y has factors in common with T, No. It's in fact rare to end up with x^2 - y^2 = 0 modulo T using this method, and gets rarer the larger T's smallest prime factor. Whether y has factors in common with T is irrelevant to this -- it just happened to be true in the specific example you tried. Since that's the _only_ example you've seen worked to the end, you latched on to an accidental property and decided "oh, that must be the reason". Simply absurd. Here, I'll make up another example on the fly (virtually _any_ non-trivial example will do). Say:

Not really. You need to understand what's happening mathematically,
which I'll explain.

Then you'll know how to create examples easily, as then you'll now why.

 Quote: T = 91 = 7 * 13 Pick: x_res = 1 S = 1 Then: k = 46 S + k^2 = 2117 = 29 * 73 Pick: f_1 = 73 f_2 = 29 Deduce: z = (f_1 + f_2)/2 = 51 y = (f_1 - f_2)/2 = 22 x = z-k = 51 - 46 = 5 Check: gcd(y, T) = gcd(22, 91) = 1 gcd(x, T) = gcd(5, 91) = 1 So _that_ excuse went away.

It's not an excuse. Mathematically there has to be a reason, right?

In general you have

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

where I want x_res = 1, but given

k = 46 mod T

what exactly determines T? The mathematics only has S, so it can use a
range of solutions such that k = 46 mod T, with S=1.

The general equation for this example is

92*x_res = 1 mod T

so you can find T's that will work by using integers for x, and in this
case, not surprisingly, x=5, gives 92*5 - 1 = 459.

So mathematically there is no surprise here. The equations are LOOSELY
connected because of the mod, as I'm using congruences, so the
mathematics will use anything that fits.

Here there seems to be a size way to limit extra solution, and some may
notice that the pure math doesn't necessarily give a useful algorithm
immediately, but thanks to Tim Peters and some examples, progress is
being made towards a full powered solution.

I like the theory. It's just neat mathematics even in its pure form,
but hey, I'm not adverse to SLOWLY figuring out something practical, as
I still hope someone in the world has some sense, as otherwise, the
worst case can be rather bad.

And I'm reminded of my prime counting function where I love it in its
slow fully mathematicized form, while posters would make fun of the
pure math version because it is slow. I liked it, because of its
special properties. They made fun of it.

But it could be changed easily to speed it up.

Here, it looks like this factoring approach can be made ever more
practical, meaning a slow stepping towards a fully realized algorithm
possibly capable of taking down RSA--worked out slowly, over a period
of days, in Usenet posts!!!

James Harris
jstevh@msn.com
science forum Guru

Joined: 21 Jan 2006
Posts: 951

Posted: Sat Jul 15, 2006 12:29 am    Post subject: Re: Loose connectivity, factoring and residues

jstevh@msn.com wrote:
 Quote: The factoring problem can be easily approached using simple algebra. Start with x^2 - y^2 = S - 2*x*k where all are integers, as notice then you trivially have x^2 + 2*x*k + k^2 = y^2 + S + k^2 so x+k = sqrt(y^2 + S + k^2) and finding y is just a matter of factoring (S+k^2)/4. Now with just the explicit equation you end up with nothing but trivialities, but turning to congruences, you can now simply let x^2 - y^2 = 0 mod T which--this is important--now forces S - 2*x_res*k = 0 mod T where I put in x_res to emphasize that now it's congruences, so there is loose connectivity and an explicit value of x is not needed--just a residue. But now I can just solve for k, assuming 2, S and x are coprime to T: k = S*(2*x_res)^{-1} mod T where (2*x_res)^{-1} is the modular inverse of (2*x_res) mod T.

One thing that has come up in this thread in my discussion with Tim
Peters is that the mathematics will solve for any T that has the k and
S given, so you have the possibility that when you solve out for x and
y, you find that x^2 - y^2 is coprime to YOUR target T, because the
mathematics has solved for another that fits with those same equations
with a different x_res..

However that seems to occur mostly with relatively large y, so
minimizing y, is a practical result of that analysis, which is why
theory does not necessarily mean you immediately have a practical
solution.

I like the analogy of the atomic bomb.

Posters pestering me to immediately solve an RSA Challenge number are
like if people had pestered Einstein to explode a nuclear bomb before
they'd consider his theories.

 Quote: That the modular inverse makes an appearance is critical, but more importantly I now have a way to find all the variables!!! That can be done by simply picking a residue for x_res and then picking S, like x_res = 1, and S =1, to get k. For instance if T=35, and I use x_res=S=1, then k = 18 mod 35, and k=18 will suffice. Then y is found by factoring (1+18^2)/4 and then you have x as well.

Using the identity:

(f_1 + f_2)^2 = (f_1 - f_2)^2 + 4*f_1*f_2

 Quote: Of course there will exist and x and y such that x^2 - y^2 = 0 mod T for any x_res you choose, which is trivial to prove, as that is equivalent to x^2 - y^2 = kT where k can be any integer.

And that remains true. Clearly now one issue is to find a relatively
small y, as in the examples that Tim Peters emphasized, y was so much
larger than x, that x^2 - y^2 was negative.

 Quote: So an equation that is useless explicitly becomes quite powerful with modular algebra--introducing loose connectivity--leading to a general method for factoring.

And remember, part of my point with these ideas is that supposedly
"pure" mathematicians CAN ignore exciting and interesting research--for
political reasons--as these people are just liars.

They may know I have other major mathematical finds, where I couldn't
force the issue like with the factoring problem, where these twisted
people chose to sit quietly, or in some cases, claim my research was
wrong, like those sci.math people who petitioned the math journal that
published a paper of mine, and the paper got yanked, and later the damn
math journal died!

The proof here for those of you willing to accept it, is in the simple
mathematics, STILL being ignored by the mainstream mathematical
community to my knowledge, as they are corrupt, and don't actually give
a damn about mathematics, seeing it only as a political and economic
tool for their own benefit.

James Harris
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Sat Jul 15, 2006 2:40 am    Post subject: Re: Loose connectivity, factoring and residues

jstevh@msn.com wrote:
 Quote: Tim Peters wrote: [jstevh@msn.com] ... The answer is that if either x or y has prime factors in common with T, then if x^2 - y^2 = 0 mod T then BOTH must have that same factor, which means that S - 2*x*k = 0 mod T would force S to have that same factor as well, but with my example, y ended up having 5 as a factor while S is coprime to 5, so there was some kind of push, which only occurs in this situation. So in terms of a factoring algorithm, it's a non-issue as if you find that you don't get x^2 - y^2 = 0 mod T then, of course, that means that y has factors in common with T, No. It's in fact rare to end up with x^2 - y^2 = 0 modulo T using this method, and gets rarer the larger T's smallest prime factor. Whether y has factors in common with T is irrelevant to this -- it just happened to be true in the specific example you tried. Since that's the _only_ example you've seen worked to the end, you latched on to an accidental property and decided "oh, that must be the reason". Simply absurd. Here, I'll make up another example on the fly (virtually _any_ non-trivial example will do). Say: Not really. You need to understand what's happening mathematically, which I'll explain. Then you'll know how to create examples easily, as then you'll now why.

And how did that example with T = 35 go? Did you ever succeed with
that?

 Quote: T = 91 = 7 * 13 Pick: x_res = 1 S = 1 Then: k = 46 S + k^2 = 2117 = 29 * 73 Pick: f_1 = 73 f_2 = 29 Deduce: z = (f_1 + f_2)/2 = 51 y = (f_1 - f_2)/2 = 22 x = z-k = 51 - 46 = 5 Check: gcd(y, T) = gcd(22, 91) = 1 gcd(x, T) = gcd(5, 91) = 1 So _that_ excuse went away. It's not an excuse. Mathematically there has to be a reason, right?

Yes. Surrogate factoring is worthless.

Of course, JSH could then say, "Well, you chose x_res and S wrong",
which brings us back to _that_ issue. If you were allowed to choose
numbers that would work "in the end", then you could come up with a
much simpler factoring algorithm:

(1) Pick an integer N between 2 and T-1 such that T mod N = 0, if one
exists.

And it has the virtue of working 100% of the time and being much
simpler than SF.

 Quote: In general you have k = S*(2x_res)^{-1) mod T where I want x_res = 1, but given k = 46 mod T what exactly determines T?

Good question. What is T? Is it the number you're trying to factor? If
so, that means that k is determined, not T; in fact,

k = 46 + A * 91, for some integer A.

 Quote: The mathematics only has S, so it can use a range of solutions such that k = 46 mod T, with S=1. The general equation for this example is 92*x_res = 1 mod T so you can find T's that will work by using integers for x, and in this case, not surprisingly, x=5, gives 92*5 - 1 = 459. So mathematically there is no surprise here. The equations are LOOSELY connected because of the mod, as I'm using congruences, so the mathematics will use anything that fits. Here there seems to be a size way to limit extra solution, and some may notice that the pure math doesn't necessarily give a useful algorithm immediately, but thanks to Tim Peters and some examples, progress is being made towards a full powered solution. I like the theory. It's just neat mathematics even in its pure form, but hey, I'm not adverse to SLOWLY figuring out something practical, as I still hope someone in the world has some sense, as otherwise, the worst case can be rather bad. And I'm reminded of my prime counting function

_formula_. Don't you bother to read any responses any more?

Here's just as good of a prime counting formula, off the top of my

P(1) = 0
P(n) = P(n-1) + ceiling(product(n/k - floor(n/k), k=2,..,n-1))

Here's how it works: If n is composite, then n/k - floor(n/k) = 0 for
some k between 2 and n-1, so the product is 0, and the ceiling of 0 is
0, so
P(n) = P(n-1), which is as it should be.

If n is prime, then n/k - floor(n/k) is between 1/k and (k-1)/k, for
all k between 2 and n-1. Thus the product is positive. Each factor of
the product is strictly less than 1, so the product will be between 0
and 1. The ceiling will be 1, so
P(n) = P(n-1) + 1, which is as it should be.

Now where's my Fields Medal?

 Quote: where I love it in its slow fully mathematicized form, while posters would make fun of the pure math version because it is slow. I liked it, because of its special properties. They made fun of it.

There are others as well; another one involves only finite sums, floor
and ceiling functions, and the four arithmetic operations, and is in
similar spirit to the formula I gave above.

 Quote: But it could be changed easily to speed it up.

JSH doesn't know how though.

 Quote: Here, it looks like this factoring approach can be made ever more practical,

I doubt it. You should know that a practical factoring algorithm is (1)
an algorithm (i.e., an explicit procedure; no "guess a value of *"
statements are allowed), and (2) a program which runs in time at most
C*(log T)^k, for some constants C and k.

 Quote: meaning a slow stepping towards a fully realized algorithm possibly capable of taking down RSA--worked out slowly, over a period of days, in Usenet posts!!!

At the rate that Surrogate Factoring is proceeding, I doubt it will be
days. Methinks it will be on the order of millennia.

--- Christopher Heckman
Tim Peters
science forum Guru

Joined: 30 Apr 2005
Posts: 426

Posted: Sat Jul 15, 2006 4:36 am    Post subject: Re: Loose connectivity, factoring and residues

[jstevh@msn.com]
 Quote: One thing that has come up in this thread in my discussion with Tim Peters is that the mathematics will solve for any T that has the k and S given, so you have the possibility that when you solve out for x and y, you find that x^2 - y^2 is coprime to YOUR target T, because the mathematics has solved for another that fits with those same equations with a different x_res..

A more pertinent explanation is that you _rely_ on:

x = x_res (modulo T) [1]

holding in order to force the critical:

x^2 = y^2 (modulo T) [2]

But, in fact, the congruence class of the x computed by the method has
nothing non-accidental to do with the x_res you pick. As a result, as the
smallest prime factor of T gets larger, it becomes increasingly unlikely
that you'll manage to find an x_res, S, f_1 and f_2 such that [1] is
actually true, and then [2] is very unlikely to be true too. Then you may
as well pick x and y at random and rely on pure luck (well, that's not quite
accurate: you'd actually be better off picking them at random then).

 Quote: However that seems to occur mostly with relatively large y, so minimizing y, is a practical result of that analysis, which is why theory does not necessarily mean you immediately have a practical solution.

It's trivial to find T such that no choice of f_1 and f_2 leads to a
non-trivial factor of T. That becomes increasingly likely as the smallest
prime divisor of T gets larger. All you have to do to learn this is
implement it.

For example, pick T = 79 * 83, which is still tiny. Then at x_res = S = 1,
no factorization of S+k^2 as the product of two integers yields a factor of
T. At x_res=1 S=2, the same. At x_res=1 S=3, also the same.

I got bored then, and figured out a way that works but knowing the
factorization in advance: at x_res=2 S=3, 2 of the 16 possible ways of
factoring S+k^2 = 2689603 as a product of 2 integers lead to x and y that
find T's factors. The only ways that work then are f_1=1561 f_2=1723 and
f_1=1723 f_2=1561.

This is most like last year's methods, where you need to introduce search
after search to have a chance of factoring a non-trivial T.

 Quote: I like the analogy of the atomic bomb. Posters pestering me to immediately solve an RSA Challenge number are like if people had pestered Einstein to explode a nuclear bomb before they'd consider his theories.

I didn't pester you to do that. I pestered you to finish factoring 35, and
just look at all the problems that revealed. You'll find many more if you
try larger T.

 Quote: ... And that remains true. Clearly now one issue is to find a relatively small y, as in the examples that Tim Peters emphasized, y was so much larger than x, that x^2 - y^2 was negative.

Of course it was, but that had nothing to do with picking "large y" and/or
picking "small x". You set things up so that:

x^2 - y^2 = S - 2*x*k

must be true. Stare at that. When picking S=1 (as I did, and just because
you did), it's impossible for the RHS _not_ to be negative (you'd have to
have x=k=0 to have 1 - 2*x*k >= 0, but k=0 is impossible). Therefore it's
also impossible to have x^2 >= y^2 at S=1.

But whether x > y or y < x has nothing to do with whether a factor will be
found anyway. Why should the math "care" about that? If you care, rename
"x" to "y" everywhere, and vice versa, and then you'll always have x^2 > y^2
at S=1.

> ...
Tim Peters
science forum Guru

Joined: 30 Apr 2005
Posts: 426

Posted: Sat Jul 15, 2006 9:35 am    Post subject: Re: Loose connectivity, factoring and residues

[jstevh@msn.com]
 Quote: ... So in terms of a factoring algorithm, it's a non-issue as if you find that you don't get x^2 - y^2 = 0 mod T then, of course, that means that y has factors in common with T,

[Tim Peters]
 Quote: No. It's in fact rare to end up with x^2 - y^2 = 0 modulo T using this method, and gets rarer the larger T's smallest prime factor. Whether y has factors in common with T is irrelevant to this -- it just happened to be true in the specific example you tried. Since that's the _only_ example you've seen worked to the end, you latched on to an accidental property and decided "oh, that must be the reason". Simply absurd. Here, I'll make up another example on the fly (virtually _any_ non- trivial example will do). Say:

[jstevh@msn.com]
 Quote: Not really.

Yes, really. Look at what you said just above:

if you find that you don't get

x^2 - y^2 = 0 mod T

then, of course, that means that y has factors in common with T,

I was replying to that, and what you said /right there/ isn't true. The
example I gave demonstrated concretely that it isn't true. More, as I said,
trying to factor virtually any non-trivial T demonstrates the same thing:
you generally find that x^2 is not congruent to y^2 modulo T, _and_ that x
and y are coprime to T. Your "that means that y has factors in common with
T" is wrong in all such cases, because y has no non-unit factors in common
with T in all such cases.

 Quote: You need to understand what's happening mathematically,

I don't have a problem with that. What problem did you have understanding
the above? Its meaning seemed very clear to me.

 Quote: which I'll explain. Then you'll know how to create examples easily, as then you'll now why.

WTF? AFAIK, I'm the only person who has ever finished an example for this
method.

 Quote: T = 91 = 7 * 13 Pick: x_res = 1 S = 1 Then: k = 46 S + k^2 = 2117 = 29 * 73 Pick: f_1 = 73 f_2 = 29 Deduce: z = (f_1 + f_2)/2 = 51 y = (f_1 - f_2)/2 = 22 x = z-k = 51 - 46 = 5 Check: gcd(y, T) = gcd(22, 91) = 1 gcd(x, T) = gcd(5, 91) = 1 So _that_ excuse went away. It's not an excuse.

It was in context: your "that means that y has factors in common with T" is
false in this example. When you give a false "reason" for an observed
behavior, calling it "an excuse" is generous.

 Quote: Mathematically there has to be a reason, right?

Yes, and the fundamental reason here is that the method _requires_ that

x = x_res (modulo T) [1]

be true in order to force

x^2 = y^2 (modulo T)

to be true, but has no way to find an x such that [1] is true. [1] is in
fact rarely true, and rarer the larger T's smallest prime factor.

 Quote: In general you have k = S*(2x_res)^{-1) mod T where I want x_res = 1, but given k = 46 mod T what exactly determines T?

I did: T is the integer I'm trying to factor. Of what use is a method that
can't factor the integer you _want_ to factor? If I get to pick an integer
I'd _rather_ factor instead, then here's a simpler method:

function factor(T):
/* factoring T might be hard; so ignore T and
*/
return "15 = 3*5"

 Quote: The mathematics only has S, so it can use a range of solutions such that k = 46 mod T, with S=1. The general equation for this example is 92*x_res = 1 mod T

You don't need to be so cryptic. You're trying to say that you need:

2*x*k = S (modulo T)

to be true, and given that S=1 and k=46 are fixed, that becomes:

92*x = 1 (modulo T)

It doesn't really help to replace "x" with "x_res", BTW, and especially not
since I picked x_res=1 in this example, and now you're (mis)using "x_res" to
mean something unrelated to the meaning it already had. Given that you're
_also_ fixing x at 5 now, the true requirement is exactly that:

92*5 = 1 (modulo T)

 Quote: so you can find T's that will work by using integers for x, and in this case, not surprisingly, x=5, gives 92*5 - 1 = 459.

What use is this? Given T=91 at the start, you now have a method that finds
the factors 17 and 3^3 of 459. If that's what someone _wants_, there are
much easier ways to do that.

In effect, all you're doing is picking x and y, and then finding T such
that:

x^2 = y^2 (modulo T)

If you think that's interesting, there are much simpler ways to do that.
Indeed, if you said from the start that you wanted to find T such that:

x^2 = y^2 (modulo T)

when x=5 and y=22, then all it really takes is to note that:

22^2 - 5^2 = 459 = 0 (modulo T)

needs to true. Bingo: all positive solutions are then found just by
listing 459's positive integer divisors; T must be one of:

1
3
9
17
27
51
153
459

The _hard_ problem, and the one that's useful for factoring, is finding
distinct x and y such that:

x^2 = y^2 (modulo T) [2]

when T is given and /fixed/. If instead you fix x and y, and want to find T
satisfying [2], as above that's plain trivial: just list the positive
integer divisors of x^2-y^2.

 Quote: So mathematically there is no surprise here.

I agree with that. But I wasn't saying it's a surprise that the method
rarely factors the integer you give it, I was saying that your

if you find that you don't get

x^2 - y^2 = 0 mod T

then, of course, that means that y has factors in common with T,

was incorrect.

 Quote: The equations are LOOSELY connected because of the mod, as I'm using congruences, so the mathematics will use anything that fits.

And that might be useful for factoring because _____?

 Quote: Here there seems to be a size way to limit extra solution, and some may notice that the pure math doesn't necessarily give a useful algorithm immediately, but thanks to Tim Peters and some examples, progress is being made towards a full powered solution.

Write an implementation. Really. You need more examples, and, sorry, but I
don't see enough promise here to justify doing more myself.

 Quote: I like the theory. It's just neat mathematics even in its pure form, but hey, I'm not adverse to SLOWLY figuring out something practical, as I still hope someone in the world has some sense, as otherwise, the worst case can be rather bad. And I'm reminded of my prime counting function where I love it in its slow fully mathematicized form, while posters would make fun of the pure math version because it is slow. I liked it, because of its special properties. They made fun of it.

I like your prime-counting formula too, as I've often said (although, no, I
don't agree it's of theoretical importance -- it's just "neat" to me).

 Quote: But it could be changed easily to speed it up. Here, it looks like this factoring approach can be made ever more practical, meaning a slow stepping towards a fully realized algorithm possibly capable of taking down RSA--worked out slowly, over a period of days, in Usenet posts!!!

Good luck.
jstevh@msn.com
science forum Guru

Joined: 21 Jan 2006
Posts: 951

Posted: Sat Jul 15, 2006 10:23 pm    Post subject: Re: Loose connectivity, factoring and residues

Tim Peters wrote:
 Quote: [jstevh@msn.com] ... So in terms of a factoring algorithm, it's a non-issue as if you find that you don't get x^2 - y^2 = 0 mod T then, of course, that means that y has factors in common with T, [Tim Peters] No. It's in fact rare to end up with x^2 - y^2 = 0 modulo T using this method, and gets rarer the larger T's smallest prime factor. Whether y has factors in common with T is irrelevant to this -- it just happened to be true in the specific example you tried. Since that's the _only_ example you've seen worked to the end, you latched on to an accidental property and decided "oh, that must be the reason". Simply absurd. Here, I'll make up another example on the fly (virtually _any_ non- trivial example will do). Say: [jstevh@msn.com] Not really. Yes, really. Look at what you said just above: if you find that you don't get x^2 - y^2 = 0 mod T then, of course, that means that y has factors in common with T, I was replying to that, and what you said /right there/ isn't true. The example I gave demonstrated concretely that it isn't true. More, as I said, trying to factor virtually any non-trivial T demonstrates the same thing: you generally find that x^2 is not congruent to y^2 modulo T, _and_ that x and y are coprime to T. Your "that means that y has factors in common with T" is wrong in all such cases, because y has no non-unit factors in common with T in all such cases.

It is correct that I was wrong on that point, and I didn't notice it
when replying or I would have noted it.

My original view was that S and k mapped to just one x_res for a
particular T, which is the correct view, but I assumed that the
congruences actually locked you to a particular T, when they lock you
to a range of T's, so I made a mistake.

However, knowing exactly what is happening, it's possible to consider
ways to make it more likely than not that the congruences are applying
to the T you want.

 Quote: You need to understand what's happening mathematically, I don't have a problem with that. What problem did you have understanding the above? Its meaning seemed very clear to me. which I'll explain. Then you'll know how to create examples easily, as then you'll now why. WTF? AFAIK, I'm the only person who has ever finished an example for this method.

I like the theory. It's fascinating mathematics to me.

I like its purity.

Your giving examples is not a bad thing. Feel free to keep it up.

But your consistency in always ending with the position that this can't
work is so far always a huge leap from anything you've shown or proven
mathematically.

 Quote: T = 91 = 7 * 13 Pick: x_res = 1 S = 1 Then: k = 46 S + k^2 = 2117 = 29 * 73 Pick: f_1 = 73 f_2 = 29 Deduce: z = (f_1 + f_2)/2 = 51 y = (f_1 - f_2)/2 = 22 x = z-k = 51 - 46 = 5 Check: gcd(y, T) = gcd(22, 91) = 1 gcd(x, T) = gcd(5, 91) = 1 So _that_ excuse went away. It's not an excuse. It was in context: your "that means that y has factors in common with T" is false in this example. When you give a false "reason" for an observed behavior, calling it "an excuse" is generous.

But I was considering a highly specific case where because y has
factors in common with T, you end up with the congruences not holding.

So it wasn't an excuse. I was mistaken on some points, that's all.

I make mistakes.

 Quote: Mathematically there has to be a reason, right? Yes, and the fundamental reason here is that the method _requires_ that x = x_res (modulo T) [1] be true in order to force x^2 = y^2 (modulo T) to be true, but has no way to find an x such that [1] is true. [1] is in fact rarely true, and rarer the larger T's smallest prime factor.

That's not correct.

Actually, x = x_res mod T, is required as you will find with any of
your examples, but your choice of x_res is not necessarily the x_res
that the congruences are following, and neither is your T.

The actual requirements are

S - 2*x_res*k = 0 mod T

and

x^2 - y^2 = 0 mod T

so given S and k, the mathematics has the option of ANY T and x_res
that will fit into BOTH equations, which is what's wrong with your
claim above, where you try to focus on x_res alone.

 Quote: In general you have k = S*(2x_res)^{-1) mod T where I want x_res = 1, but given k = 46 mod T what exactly determines T? I did: T is the integer I'm trying to factor. Of what use is a method that can't factor the integer you _want_ to factor? If I get to pick an integer I'd _rather_ factor instead, then here's a simpler method:

But you are the one who is making the point that your choice for T is
not necessarily the T the congruences are using.

The mathematics is simple enough: you have two main congruence
equations and way to solve for an S and k that will work with a given
residue modulo your target T, however, there are other values that will
also work with them as well.

Next question then is obvious, how do you make the odds high that your
T is the one that is chosen?

James Harris
Tim Peters
science forum Guru

Joined: 30 Apr 2005
Posts: 426

Posted: Sun Jul 16, 2006 3:17 am    Post subject: Re: Loose connectivity, factoring and residues

[jstevh@msn.com]
 Quote: ... However, knowing exactly what is happening, it's possible to consider ways to make it more likely than not that the congruences are applying to the T you want.

It's possible to consider that, yes. In the end I _expect_ you'll find it's
as hard as (because is strongly related to) solving the modular square root
problem.

....

 Quote: But your consistency in always ending with the position that this can't work is so far always a huge leap from anything you've shown or proven mathematically.

The only thing I cared about was whether the method factored the T given to
it. It rarely does, and more rarely the larger T's smallest prime factor.
Anyone can confirm or refute that by implementing the method and trying it.
I already did. I expect most people can see why it's unlikely to factor
from the mathematical exposition already given (much more so on sci.math
than here, though).

....

[jstevh@msn.com]
 Quote: Mathematically there has to be a reason, right?

[Tim Peters]
 Quote: Yes, and the fundamental reason here is that the method _requires_ that x = x_res (modulo T) [1] be true in order to force x^2 = y^2 (modulo T) to be true, but has no way to find an x such that [1] is true. [1] is in fact rarely true, and rarer the larger T's smallest prime factor. That's not correct.

It is correct if you take, as I took, x_res, T, S, and k to be _fixed_ after
they're first chosen. It actually requires all of:

x = x_res (modulo T) [2]
and
k = S*(2*x_res)^-1 (modulo T) [3]
and
x^2 - y^2 = S - 2*x*k (modulo T) [4]

to conclude:

x^2 = y^2 (modulo T) [5]

Your method does satisfy [3] and [4], so I didn't mention them above. It
rarely satisifies [2] (taking x_res, T, s, and k as fixed), which is why [5]

 Quote: Actually, x = x_res mod T, is required as you will find with any of your examples, but your choice of x_res is not necessarily the x_res that the congruences are following, and neither is your T.

And, in fact, they rarely are.

 Quote: The actual requirements are S - 2*x_res*k = 0 mod T and x^2 - y^2 = 0 mod T

See above for a careful statement of the actual requirements. You're
missing [2] and [4] in this statement. You don't need [2] _if_ you rewrite

S - 2 * mod(x, T) * k = 0 (modulo T) [3']

or even as simply:

S - 2*x*k = 0 (modulo T) [3'']

You got in trouble to _begin_ with in this method by implicitly assuming
that:

x_res
and
mod(x, T)

always mean the same thing. But they don't, which is exactly why the value
picked for x_res in the method may have nothing to do with the actual value
of mod(x, T) for the x computed by the method. You'd be better off dropping
the "x_res" notation entirely (use "mod(x, T)" or plain "x") instead --
"x_res" is systematically confusing because it isn't necessarily x's residue
modulo T.

 Quote: so given S and k, the mathematics has the option of ANY T and x_res that will fit into BOTH equations, which is what's wrong with your claim above, where you try to focus on x_res alone.

Again, there was nothing wrong with my claim if if you take, as I took,
x_res, T, S, and k to be fixed after they're first chosen. I didn't focus
in x_res in particular there, I considered _all_ of x_res, T, S and k to be
fixed.

 Quote: ... But you are the one who is making the point that your choice for T is not necessarily the T the congruences are using.

Yes. That point has to be made, since you didn't make it in any of your
original claims. It's important to be up-front about that this method may
not factor the T it's given.

 Quote: The mathematics is simple enough: you have two main congruence equations and way to solve for an S and k that will work with a given residue modulo your target T, however, there are other values that will also work with them as well.

A key difference is that the method _can_ factor those other values, but can
rarely factor the target T given.

 Quote: Next question then is obvious, how do you make the odds high that your T is the one that is chosen?

See my first reply above; I don't _expect_ this is any easier than finding a
way to solve the modular square root problem, and there aren't any efficient
deterministic or probabilistic methods known for that when the modulus is
composite (which isn't surprising, since solving the modular square root
problem for a given modulus is provably as hard as factoring the modulus).
Patrick Hamlyn
science forum beginner

Joined: 03 May 2005
Posts: 45

Posted: Sun Jul 16, 2006 3:23 am    Post subject: Re: Loose connectivity, factoring and residues

jstevh@msn.com wrote:

 Quote: Next question then is obvious, how do you make the odds high that your T is the one that is chosen?

This is the equivalent of asking:
How do you factor large numbers easily?
And you're no closer to answering that than before you 'discovered' your
magnificent 'so obvious nobody else saw it before' method.

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 2 [27 Posts] Goto page:  1, 2 Next View previous topic :: View next topic
 The time now is Thu Aug 16, 2018 10:54 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 Another look at triangle number factoring. Dan11 Math 2 Tue Jul 18, 2006 7:05 pm Primality & Factoring Gerry num-analysis 3 Tue Jul 18, 2006 10:45 am SF: Definitely a new factoring method jstevh@msn.com Math 36 Tue Jul 18, 2006 1:22 am Simple factoring result, but what about lies? jstevh@msn.com Recreational 7 Fri Jul 14, 2006 12:52 am