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 » Undergraduate
Loose connectivity, factoring and residues
Post new topic   Reply to topic Page 1 of 2 [27 Posts] View previous topic :: View next topic
Goto page:  1, 2 Next
Author Message
David Moran
science forum Guru Wannabe


Joined: 13 May 2005
Posts: 252

PostPosted: Mon Jul 17, 2006 12:14 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

Quote:
Look over my roadmap of discoveries. Why do you think your
mathematical insights are better than mine?

Because it's obvious that you don't know the first thing about the field of
mathematics. I learned how to write a proof in my freshman year of college
and your crap and useless drivel are not proofs. Your biggest problem is
your own ignorance; you have shown yourself to be ignorant about a lot of
things in our field. A degree in physics doesn't equal knowledge of how to
write a math proof.

Dave
Back to top
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

PostPosted: Sun Jul 16, 2006 11:47 pm    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

Tim Peters wrote:
Quote:
[added sci.math because there's some mathematical content here,
and I'm done with this method now]

...

[jstevh@msn.com]
Ah, so you tried to test it to the best of your ability,

[Tim Peters]
Yes.

and couldn't figure out a way to get it to work,

No. I can get it to work well by exploiting that I know the
factorization before I begin. Otherwise, no, it required more
gcds to find a factor than the random-gcd factoring method, under
a variety of different schemes for picking S and x_res values.

[jstevh@msn.com]
So you failed.

Not at all. My _goal_ was to try different strategies and see how they
behaved, and I was successful in meeting that goal. Showing that it worked
well was not a goal; showing that it didn't work well was not a goal;
showing that there was no possible way for it work well was not a goal;
"figuring out a way to get it to work" was not a goal ... /my/ goal was
simply to observe its behavior under a variety of plausible approaches.

Do you understand this? Because I don't have a stake in whether it works
well or not, "works well" and "doesn't work well" are the same to me. The
"doesn't work well" outcome is "failure" to you because you're emotionally
attached to a /different/ outcome. That's /why/ you call "doesn't work
well" failure. I'm not laboring under that burden.


The point is that YOU failed. Your inability to find a working
algorithm is not proof of the failure of the approach, but you keep
posting as if it is.

IN this post, I am going to explain mathematically why you are wrong,
and do it VERY quickly, hoping you will get a clue about how YOUR
ability or lack of it, is not a mathematical determinate.

Quote:
so you felt comfortable saying it couldn't work.

I'm 100% comfortable saying that no way I tried worked as well as
random-gcd. I'm also 100% comfortable saying that everything I observed
matched the mathematical statements I've made about it. In contrast,
_every_ observed behavior has caught you by surprise so far. Sucks to
be you here, I'm afraid.

I don't think so, as I like the mathematics, and I don't trust your
abilities over mine.

Obviously not. Indeed, that's why you spend days, weeks, and even months at
times trying to salvage methods after I've given up on them and explained
why. Sucks to be you here ;-)


I LIKE discovery. I like playing with ideas, even when they fail,
working out why they fail.

If you try hard enough, you will fail, a lot.

If you think that you gain some points by never failing publicly in a
big way, then fine, that's you.

But I still like the analogy of professional basball players, who go
up to the plate, swinging that bat, and most of the time--they fail.

Quote:

I just picked S=1 and x_res =1 because it was an obvious thing to do
with the initial idea, not thinking any serious researcher would think
that written in stone.

You are so full of s**t, James: a _serious_ researcher would implement
it himself, which leaves you out entirely. And, no, of course I didn't
limit my experiments to S = x_res = 1.

Then I don't know how you screwed up.

Easy cure: implement it yourself, and when it doesn't work well for you
either, you can figure out how /you/ screwed up instead.


I'll do as I like with this method, but YOU are the one publicly
downplaying it, putting YOUR judgement against it.

So I feel a need to show people that your judgement is flawed.

You put yourself in the position of attacking this approach, and I can
show you are wrong with theory, without ever needing to do my own
example.

I LIKE mathematics. It's logical.

Quote:
There are lots of reasons to think that S was too small, from the
outset.

I guess some may wonder if S can be too big then, so that maybe there
is this narrow ranger of S's that will work.

Think about it.

I already did, thank you.

Then there is something else you did wrong, or didn't think of.

Weren't you bitching just yesterday about unsupported assertions? You don't
have proof, and you don't have empirical evidence. Your only justification
for saying that is wishful thinking.


I've since supported the assertion mathematically, and will do so again
in this post.

Quote:
...
You claim you worked backwards, using your knowledge of factorizations
to see what would work.

How did S behave then?

If you don't know, then you screwed up.

Sorry, but you don't even begin to understand this, and again at least
because you don't /try/ anything yourself. I did the obvious thing to make
it work on the first try: given that I knew T = p*q, I picked:

x = (p-q)/2
y = (p+q)/2

Then:

x^2 - y^2 = -T = 0 (modulo T)
gcd(x+y, T) = gcd(p, T) = p
gcd(x-y, T) = gcd(-q, T) = q

follow. You can always work backward from that to find some S and x_res and
k and f_1 and f_2 (sheesh ...) "that work", but doing so gives no /usable/
insight into any of them. Your belief that it /must/ is based on nothing
but hope. Here's a complete "backwards" example illustrating exactly what
the snag is (and incidentally proving that it's possible to work backwards
deterministically and efficiently -- there's nothing special about the
specific numbers used here):


You picked a way that made sense TO YOU, but it doesn't consider the
important mathematical points.

Instead, consider a solution for x_res = 1 mod T, which is a PICKED
residue, not just some residue that just comes out of the blue. I
think you're kind of lazy here as well, as it takes a little more
effort to find a particular residue mod T.

Now then, if you find a solution

x^2 - y^2 = 0 mod T

where x = 1 mod T, then you will also find that

S = 2*x*k mod T

solves to give

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

so if you solve for k FIRST, with x_res = 1 mod T, then you get the
SAME ANSWER if k is a residue modulo T, understand?

That is an important point.

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

will give the same answer with x_res = 1 as you find when you go out
looking for an answer with x = 1 mod T.

So what does that leave for any variation?

It leaves S.

But the S you find works with your searched for solutions must equal
the residue modulo T for any residue that you picked!!!

So, for a picked S, versus your found S, which I'll now call S_found,
you have

S_found = S mod T

and that is crucial.

Do you understand it?

So you can pick an S that is too small, but you are still picking an S
that has the same residue as an S that MUST factor.

That means, mathematically, it must be the case that if you don't find
an answer with a particular S, then there must be an answer with a
multiple of T added or subtracted from that S.

Do you agree or disagree?

Look over my roadmap of discoveries. Why do you think your
mathematical insights are better than mine?

Just because you've seen a lot of my failures?

But could you have ANY of my successes?


James Harris
Back to top
Tim Peters
science forum Guru


Joined: 30 Apr 2005
Posts: 426

PostPosted: Sun Jul 16, 2006 10:06 pm    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

[added sci.math because there's some mathematical content here,
and I'm done with this method now]

....

[jstevh@msn.com]
Quote:
Ah, so you tried to test it to the best of your ability,

[Tim Peters]
Quote:
Yes.

and couldn't figure out a way to get it to work,

No. I can get it to work well by exploiting that I know the
factorization before I begin. Otherwise, no, it required more
gcds to find a factor than the random-gcd factoring method, under
a variety of different schemes for picking S and x_res values.

[jstevh@msn.com]
Quote:
So you failed.

Not at all. My _goal_ was to try different strategies and see how they
behaved, and I was successful in meeting that goal. Showing that it worked
well was not a goal; showing that it didn't work well was not a goal;
showing that there was no possible way for it work well was not a goal;
"figuring out a way to get it to work" was not a goal ... /my/ goal was
simply to observe its behavior under a variety of plausible approaches.

Do you understand this? Because I don't have a stake in whether it works
well or not, "works well" and "doesn't work well" are the same to me. The
"doesn't work well" outcome is "failure" to you because you're emotionally
attached to a /different/ outcome. That's /why/ you call "doesn't work
well" failure. I'm not laboring under that burden.

Quote:
so you felt comfortable saying it couldn't work.

I'm 100% comfortable saying that no way I tried worked as well as
random-gcd. I'm also 100% comfortable saying that everything I observed
matched the mathematical statements I've made about it. In contrast,
_every_ observed behavior has caught you by surprise so far. Sucks to
be you here, I'm afraid.

I don't think so, as I like the mathematics, and I don't trust your
abilities over mine.

Obviously not. Indeed, that's why you spend days, weeks, and even months at
times trying to salvage methods after I've given up on them and explained
why. Sucks to be you here ;-)

....

Quote:
I just picked S=1 and x_res =1 because it was an obvious thing to do
with the initial idea, not thinking any serious researcher would think
that written in stone.

You are so full of s**t, James: a _serious_ researcher would implement
it himself, which leaves you out entirely. And, no, of course I didn't
limit my experiments to S = x_res = 1.

Then I don't know how you screwed up.

Easy cure: implement it yourself, and when it doesn't work well for you
either, you can figure out how /you/ screwed up instead.

Quote:
There are lots of reasons to think that S was too small, from the
outset.

I guess some may wonder if S can be too big then, so that maybe there
is this narrow ranger of S's that will work.

Think about it.

I already did, thank you.

Then there is something else you did wrong, or didn't think of.

Weren't you bitching just yesterday about unsupported assertions? You don't
have proof, and you don't have empirical evidence. Your only justification
for saying that is wishful thinking.

Quote:
...
You claim you worked backwards, using your knowledge of factorizations
to see what would work.

How did S behave then?

If you don't know, then you screwed up.

Sorry, but you don't even begin to understand this, and again at least
because you don't /try/ anything yourself. I did the obvious thing to make
it work on the first try: given that I knew T = p*q, I picked:

x = (p-q)/2
y = (p+q)/2

Then:

x^2 - y^2 = -T = 0 (modulo T)
gcd(x+y, T) = gcd(p, T) = p
gcd(x-y, T) = gcd(-q, T) = q

follow. You can always work backward from that to find some S and x_res and
k and f_1 and f_2 (sheesh ...) "that work", but doing so gives no /usable/
insight into any of them. Your belief that it /must/ is based on nothing
but hope. Here's a complete "backwards" example illustrating exactly what
the snag is (and incidentally proving that it's possible to work backwards
deterministically and efficiently -- there's nothing special about the
specific numbers used here):

T = 8023 = 113 * 71 = p*q

From that it follows that these /must/ work:

x = x_res = 21
y = 92

Then the requirement:

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

reduces to:

S = 42*k - 8023 [1]

We also need:

2*S*k = x_res (modulo T)

which reduces to:

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

Plugging [1] into [2] to eliminate S, and simplifying modulo T (note that in
general the RHS of [1] is of the form i*k - T, so is congruent to i*k):

4*k^2 = 1 (modulo T)

which is the same as (multiplying both sides by 4's inverse modulo 8023):

k^2 = 4012 (modulo T) [3]

As I told you yesterday (but didn't bother to demonstrate), solving [3] /is/
the modular square root problem. Nobody knows how to solve that efficiently
when T is composite without knowing T's factorization, but I know how to
solve it efficiently when T's factors are known (and that's long-winded, so
I won't explain it here -- read a book -- or read my earlier posts, where I
did explain much of it).

The four solutions to [3], along with their associated S values from [1],
are (and you can easily /check/ that these satisfy all the congruences from
which I derived them);

k S
---- ------
2065 78707
3698 147293
4325 173627
5958 242213

Almost done. Picking any <k, S> pair from that list "works" in the forward
direction too (do you see why?), although:

a) It required solving a modular square problem to find them; and,

b) You still _also_ need to pick a factorization of S+k^2 as f_1*f_2
that doesn't screw up. Most ways do screw up. This way always
works (and remember that I know x, y, and k in advance here, so
doing this part is completely trivial):

f_1 = x+y+k
f_2 = x-y+k

So, as advertised, that's how to find S, x_res, k, f_1 and f_2 that work on
the first try -- provided you know T's factorization before you start.

Quote:
Was it random in size with respect to the size of T? (Absolute values
here.)

If you don't know, then you need to go back and check.

See above. For this way of picking x and y,

S = 2*x*k - T

where:

x = (p-q)/2

and little useful can be said about k's magnitude beyond that some k that
works always exists in 1 .. floor(T/2).

Quote:
If you find what I think you'll find, take a deep breath, do nothing
rash, and remember, time is the healer of all wounds.

Is that what you thought would happen Wink ?
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sun Jul 16, 2006 4:56 pm    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

Tim Peters wrote:
Quote:
[Tim Peters]
[...]
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/. [...]

[Proginoskes]
Actually, it isn't too hard. Choose x and A to be arbitrary integers,
and let
y = A T - x.

Then y^2 = (A T - x) = A T^2 - 2 A T x + x^2 = x^2 (mod T).

Thank you Smile Of course the hard problem is finding integer x and y
satisfying [2] when T is given and fixed /and composite/, and where it's
_not_ true that:

x = +/- y (modulo T) [3]

Cases where [2] and [3] hold are indeed trivial to find, but are _usually_
of no use for factoring via [2]. For if

x = y (modulo T) [4]

then

x-y = 0 (modulo T)

so gcd(x-y, T) = T. Similarly, if

x = -y (modulo T)

then

x+y = 0 (modulo T)

so gcd(x+y, T) = T. So at least one of {x-y, x+y} is certain to be useless
when [4] holds. Of course "deeper" analysis is possible, and I'll just
sketch one case here (the other is very much alike): suppose [4] holds. We
already showed that x-y is useless in this case, but what about x+y? Well,

x = y (modulo T)
implies
x+y = 2*x (modulo T)
so
gcd(x+y, T) =
gcd(2*x, T)

so x+y is useless too unless you were lucky in picking x. In particular, if
T is odd, then

gcd(2*x, T) = gcd(x, T) = gcd(mod(x, T), T)

so "you're lucky" means you have to be lucky enough so that mod(x, T) isn't
1 and divides T. Because that's very unlikely when T has no small prime
factors, cases where [3] holds are usually considered to be wholly
uninteresting.

OTOH, if [2] holds but [3] doesn't, taking gcds of T with x+y and x-y _do_
reveal non-trivial factors of T. Exercise for the reader :-)

BTW, note that in your example, there was no need to expand (A T -x)^2,

Yes, there is, you liar. 8-)

Actually, I was parodying the unnecessary complexities that JSH will
throw into his posts, so that he's confused into thinking there's
something to them.

--- Christopher Heckman

Quote:
since:

A T - x = -x (modulo T)

implies:

(A T -x)^2 = (-x)^2 = x^2 (modulo T)
Back to top
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

PostPosted: Sun Jul 16, 2006 2:40 pm    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

Tim Peters wrote:
Quote:
...

[Tim Peters]
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.

[jstevh@msn.com]
Ah, so you tried to test it to the best of your ability,

Yes.

and couldn't figure out a way to get it to work,

No. I can get it to work well by exploiting that I know the factorization
before I begin. Otherwise, no, it required more gcds to find a factor than
the random-gcd factoring method, under a variety of different schemes for
picking S and x_res values.


So you failed.

Quote:
so you felt comfortable saying it couldn't work.

I'm 100% comfortable saying that no way I tried worked as well as
random-gcd. I'm also 100% comfortable saying that everything I observed
matched the mathematical statements I've made about it. In contrast,
_every_ observed behavior has caught you by surprise so far. Sucks to be
you here, I'm afraid.


I don't think so, as I like the mathematics, and I don't trust your
abilities over mine.

Quote:
But if you're wrong, billions of dollars can be the weight that falls
partly on your head.

And I bet you are wrong.

How much?


That's an expression.

Quote:
I just picked S=1 and x_res =1 because it was an obvious thing to do
with the initial idea, not thinking any serious researcher would think
that written in stone.

You are so full of s**t, James: a _serious_ researcher would implement it
himself, which leaves you out entirely. And, no, of course I didn't limit
my experiments to S = x_res = 1.


Then I don't know how you screwed up.

Quote:
There are lots of reasons to think that S was too small, from the
outset.

I guess some may wonder if S can be too big then, so that maybe there
is this narrow ranger of S's that will work.

Think about it.

I already did, thank you.


Then there is something else you did wrong, or didn't think of.


Quote:
If you figure out that you were sadly mistaken in attacking this
method, be smart, take a deep breath, and just come back and reply that
you were wrong, or do NOTHING.

Enough with the counterfactual hypotheticals, please.


You claim you worked backwards, using your knowledge of factorizations
to see what would work.

How did S behave then?

If you don't know, then you screwed up.

Was it random in size with respect to the size of T? (Absolute values
here.)

If you don't know, then you need to go back and check.

If you find what I think you'll find, take a deep breath, do nothing
rash, and remember, time is the healer of all wounds.


James Harris
Back to top
Tim Peters
science forum Guru


Joined: 30 Apr 2005
Posts: 426

PostPosted: Sun Jul 16, 2006 6:10 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

[Tim Peters]
Quote:
[...]
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/. [...]

[Proginoskes]
Quote:
Actually, it isn't too hard. Choose x and A to be arbitrary integers,
and let
y = A T - x.

Then y^2 = (A T - x) = A T^2 - 2 A T x + x^2 = x^2 (mod T).

Thank you Smile Of course the hard problem is finding integer x and y
satisfying [2] when T is given and fixed /and composite/, and where it's
_not_ true that:

x = +/- y (modulo T) [3]

Cases where [2] and [3] hold are indeed trivial to find, but are _usually_
of no use for factoring via [2]. For if

x = y (modulo T) [4]

then

x-y = 0 (modulo T)

so gcd(x-y, T) = T. Similarly, if

x = -y (modulo T)

then

x+y = 0 (modulo T)

so gcd(x+y, T) = T. So at least one of {x-y, x+y} is certain to be useless
when [4] holds. Of course "deeper" analysis is possible, and I'll just
sketch one case here (the other is very much alike): suppose [4] holds. We
already showed that x-y is useless in this case, but what about x+y? Well,

x = y (modulo T)
implies
x+y = 2*x (modulo T)
so
gcd(x+y, T) =
gcd(2*x, T)

so x+y is useless too unless you were lucky in picking x. In particular, if
T is odd, then

gcd(2*x, T) = gcd(x, T) = gcd(mod(x, T), T)

so "you're lucky" means you have to be lucky enough so that mod(x, T) isn't
1 and divides T. Because that's very unlikely when T has no small prime
factors, cases where [3] holds are usually considered to be wholly
uninteresting.

OTOH, if [2] holds but [3] doesn't, taking gcds of T with x+y and x-y _do_
reveal non-trivial factors of T. Exercise for the reader :-)

BTW, note that in your example, there was no need to expand (A T -x)^2,
since:

A T - x = -x (modulo T)

implies:

(A T -x)^2 = (-x)^2 = x^2 (modulo T)
Back to top
Tim Peters
science forum Guru


Joined: 30 Apr 2005
Posts: 426

PostPosted: Sun Jul 16, 2006 5:11 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

....

[Tim Peters]
Quote:
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.

[jstevh@msn.com]
Quote:
Ah, so you tried to test it to the best of your ability,

Yes.

Quote:
and couldn't figure out a way to get it to work,

No. I can get it to work well by exploiting that I know the factorization
before I begin. Otherwise, no, it required more gcds to find a factor than
the random-gcd factoring method, under a variety of different schemes for
picking S and x_res values.

Quote:
so you felt comfortable saying it couldn't work.

I'm 100% comfortable saying that no way I tried worked as well as
random-gcd. I'm also 100% comfortable saying that everything I observed
matched the mathematical statements I've made about it. In contrast,
_every_ observed behavior has caught you by surprise so far. Sucks to be
you here, I'm afraid.

Quote:
But if you're wrong, billions of dollars can be the weight that falls
partly on your head.

And I bet you are wrong.

How much?

Quote:
I just picked S=1 and x_res =1 because it was an obvious thing to do
with the initial idea, not thinking any serious researcher would think
that written in stone.

You are so full of s**t, James: a _serious_ researcher would implement it
himself, which leaves you out entirely. And, no, of course I didn't limit
my experiments to S = x_res = 1.

Quote:
There are lots of reasons to think that S was too small, from the
outset.

I guess some may wonder if S can be too big then, so that maybe there
is this narrow ranger of S's that will work.

Think about it.

I already did, thank you.

Quote:
If you figure out that you were sadly mistaken in attacking this
method, be smart, take a deep breath, and just come back and reply that
you were wrong, or do NOTHING.

Enough with the counterfactual hypotheticals, please.

> [more blah blah blah]
Back to top
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

PostPosted: Sun Jul 16, 2006 4:29 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

Tim Peters wrote:
Quote:
[jstevh@msn.com]
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).


There are two congruences:

x^2 - y^2 = 0 mod T

and

S - 2*x_res*k = 0 mod T

and both have to be satisfied, where the method I've outlined involves
factoring

S + k^2

where there is no information about x_res and T, so the mathematics is
free to use any that fit with those two congruences.

That is mathematically significant.


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.


You are not as smart as you think you are.

I know the reason for your problems and I think I know the resolution.

You're not thinking about

x^2 - y^2 = k*T

as the general solution to the congruence, where because of the way I
solve the problem it's also true that

S - 2*x*k = k*T

so there must be a size limitation below which S can't fall or you just
can't solve the thing with a natural number k.

The research question is, what is the minimum size for S given the
absolute size of T?

Just guessing I'd say greater than sqrt(T)?

It probably can be less, but it wouldn't help for it to be more.

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


Ah, so you tried to test it to the best of your ability, and couldn't
figure out a way to get it to work, so you felt comfortable saying it
couldn't work.

But if you're wrong, billions of dollars can be the weight that falls
partly on your head.

And I bet you are wrong. I just picked S=1 and x_res =1 because it was
an obvious thing to do with the initial idea, not thinking any serious
researcher would think that written in stone.

There are lots of reasons to think that S was too small, from the
outset.

I guess some may wonder if S can be too big then, so that maybe there
is this narrow ranger of S's that will work.

Think about it.

If you figure out that you were sadly mistaken in attacking this
method, be smart, take a deep breath, and just come back and reply that
you were wrong, or do NOTHING.

Do NOTHING RASH.

Time is the best healer. And in the heat of the moment, wrong
decisions can seem wise.

The situation is just far bigger than you realized. But even worldwide
attention is just a thing.


James Harris
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sun Jul 16, 2006 4:28 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

Tim Peters wrote:
Quote:
[...]
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/. [...]

Actually, it isn't too hard. Choose x and A to be arbitrary integers,
and let
y = A T - x.

Then y^2 = (A T - x) = A T^2 - 2 A T x + x^2 = x^2 (mod T).

--- Christopher Heckman
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sun Jul 16, 2006 4:25 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

jstevh@msn.com wrote:
Quote:
Patrick Hamlyn wrote:
jstevh@msn.com wrote:

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.

Doesn't sound like a mathematical statement to me.

It sounds like a political one.

Then you need to clean out your ears. It is _purely_ a mathematical
statement.

--- Christopher Heckman
Back to top
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

PostPosted: Sun Jul 16, 2006 4:13 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

Patrick Hamlyn wrote:
Quote:
jstevh@msn.com wrote:

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.

Doesn't sound like a mathematical statement to me.

It sounds like a political one.

Remember, part of my point is that yours is a political society, which
casually uses social forces rather than mathematical tools.

This time period while people attack this method is meant to show just
how dangerous politics can be.

In the big world you can have wars, like the U.S. war with Iraq, and in
the academic world, you can have wars as well, like the political
battles against my ideas.

Just like the U.S. was wrong with something so huge that thousands of
lies have been lost, mathematicians can be wrong with their politics
here.

Difference is, billions of dollars may be lost before this war is over,
and then some of you will begin to comprehend the costs of playing
politics.

I can win one way, or another. You people let the gap continue, and I
gain the momentum I need to quite simply, end the jobs of most
mathematicians worldwide.

I want to clear entire math departments at major universities, and so
you have some context, a university on my list is Princeton.

Before this is over, the Princeton math department will no longer
exist.

I need a lot of momentum to do that, and that takes time and your
refusal to acknowledge important mathematics in an area important to a
lot of people around the world.


James Harris
Back to top
Patrick Hamlyn
science forum beginner


Joined: 03 May 2005
Posts: 45

PostPosted: Sun Jul 16, 2006 3:23 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

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.
Back to top
Tim Peters
science forum Guru


Joined: 30 Apr 2005
Posts: 426

PostPosted: Sun Jul 16, 2006 3:17 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

[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]
rarely holds for the T you start with.

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
your first equation as:

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).
Back to top
jstevh@msn.com
science forum Guru


Joined: 21 Jan 2006
Posts: 951

PostPosted: Sat Jul 15, 2006 10:23 pm    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

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
Back to top
Tim Peters
science forum Guru


Joined: 30 Apr 2005
Posts: 426

PostPosted: Sat Jul 15, 2006 9:35 am    Post subject: Re: Loose connectivity, factoring and residues Reply with quote

[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
* factor 15 instead
*/
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.
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 2 [27 Posts] Goto page:  1, 2 Next
View previous topic :: View next topic
The time now is Wed Mar 12, 2014 7:01 pm | All times are GMT
Forum index » Science and Technology » Math » Undergraduate
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 Another look at triangle number factoring. Dan11 Math 2 Tue Jul 18, 2006 7:05 pm
No new posts Primality & Factoring Gerry num-analysis 3 Tue Jul 18, 2006 10:45 am
No new posts SF: Definitely a new factoring method jstevh@msn.com Math 36 Tue Jul 18, 2006 1:22 am
No new posts Simple factoring result, but what about lies? jstevh@msn.com Recreational 7 Fri Jul 14, 2006 12:52 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.1173s ][ Queries: 16 (0.0519s) ][ GZIP on - Debug on ]