JSH: This factoring thing is scary
JSH
EASY. It's a technique to solve quadratic residues modulo N.
If you think it's not possible then use all of your mathematical
training to explain the second example:
So now let's do, k=9. So q = 11 mod 35, and T = 22 mod 35, so I can
try T = 57.
The trivial factorization didn't work here, so I'll just jump to, f_1
= 19, and f_2 = 3, so:
k = 3^{-1}(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35.
19^2 = 11 mod 35
so it worked! (It's so weird though watching it. Even though I know
the underlying mathematics it seems like magic.)
And that is a factoring example, as I know k=9 is a solution, so I
have
19^2 = 9^2 mod 35
so (19-9)(19+9) = 0 mod 35, so (10)(28) = 0 mod 35, and you pull 5 and
7 as factors with a gcd.
THAT is how you use a method for solving quadratic residues modulo N:
you find one quadratic residue and then go looking for another.
Factoring problem solved.
Happy one year birthday to the solution as it's a year old about now.
James Harris
Mark Murray
> Factoring problem solved.
Where is the complexity analysis?
M
--
Mark Murray
amzoti
>
> James Harris
I couldn't get passed the title of this thread.
You should stay away from scary things!
It is even scarier to think that you believe you have solved the
factoring problem.
You are still clueless after 15 years and counting.
Delusional narcissist!
bert
> JSH wrote:
> > Factoring problem solved.
>
> Where is the complexity analysis?
James seldom responds to replies which invite
him to do any more work. When he does, it is
usually with some woolly argument as to why
that extra work is unnecessary or inadvisable.
--
Jens Stuckelberger
> [What can he write but crap?]
The only scary thing here is that you have been posting for over
decade and you have learned absolutely nothing. Even a completely stupid
human being would have learned a bit by now.
Mark Murray
In a very recent post, he expressed the desire for others to do this extra
work. This was in the context of factoring large numbers.
M
--
Mark Murray
JSH
> EASY. It's a technique to solve quadratic residues modulo N.
>
> If you think it's not possible then use all of your mathematical
> training to explain the second example:
>
> So now let's do, k=9. So q = 11 mod 35, and T = 22 mod 35, so I can
> try T = 57.
>
> The trivial factorization didn't work here, so I'll just jump to, f_1
> = 19, and f_2 = 3, so:
>
> k = 3^{-1}(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35.
>
> 19^2 = 11 mod 35
>
> so it worked! (It's so weird though watching it. Even though I know
> the underlying mathematics it seems like magic.)
Often f_1 or f_2 will BE the answer as above, so one way short-hand to
beginning to understand the fundamental result is that given a
quadratic residue q modulo N, and f_1*f_2 = 2q mod N, where f_1*f_2
does not equal 2q, either f_1 or f_2 will tend to be a solution to the
quadratic residue. i.e. if k^2 = q mod N, then f_1 or f_2 will tend
to equal k.
What's interesting is that is a fundamental algebraic congruence
result, apparently previously unknown.
James Harris
Enrico
======================================================
I set up a routine to factor odd composites using the ideas you
listed.
The general idea is to get X^2 = Y^2 mod the target composite N.
X = 1, 2, 3, ...
Y is calculated from X^2 mod N using 3 ^ (-1) mod N and the sum of the
factors of the result are used - to keep things simple, I just used 1
as
the first factor. (Sloppy description - I assume you know your own
stuff)
The results seem to be periodic over intervals of N.
Example:
N = 299 = 13 * 23
A = 0, 1, 2, 3, ...
X = 299 * A + 12, 58, 116, 137, 162, 183, 241, 287
Y = 196, 150, 1, 254, 254, 1, 150, 196
X^2 mod N = Y^2 mod N = 144, 75, 1, 231, 231, 1, 75, 144
GCD (X+Y, N) divides N
GCD (X -Y, N) divides N
Works. Practical ? Dunno.
Enrico
JSH
I puzzled a bit over what you put down, but not a lot. Of course I
focused on the part where you say it works, but what puzzles me about
the reaction to my research is the lack of curiosity.
Turns out that mathematically just the result that you can connect one
factorization to another is the key thing in my opinion, and it kind
of follows that a lot of other interesting things would result from
that alone.
And hey I remind that math people destroyed an entire math journal
over some of my other research.
Denial here is willful. I see it as protecting turf and as a class
war.
There has been overwhelming evidence for YEARS in my favor.
It is easy math here. The mathematics is public. This group is
public and the research is on my math blog.
If this approach can lead to a viable factoring method, then
presumably SOMEONE will do it. If my other math research DOES show
P=NP, then some nation can potentially work through cracking all
asymmetric key methods.
If another year goes by and I'm posting in November 2010 about yet
another belated anniversary that hypothetical nation may be well on
its way to ruling your world, because of you.
History has turned on bigger things than recalcitrant academics
naively protecting their turf because they lack the imagination to see
that what seems small to them--protecting their status quo--can have
serious repercussions.
It is about time here, people.
If my research is valid, and you dilly-dally the answer you seek will
not be me factoring some large number, but watching the world order
change, as you find out that some nation has cracked ALL the security
on the planet because your PROTECTED "YOUR TURF".
Dumb freaking academic idiots.
James Harris
JSH
And I HATE ranting and posters just get on my case for ranting as they
ALREADY MADE UP THEIR MINDS!!!
But it's so frustrating when you have the math and it's so easy.
What do you people think they will do to you if I'm right, and "geeks"
really turned out in the end to be so clueless they let the world
security be compromised just because for all their abstruse knowledge
into stuff no one really cares about, they lacked the basic sense of
self-preservation to pay attention to the math that mattered?
Sure you LOVE the number field sieve but if the argument later is that
your love of overly complex STUFF kept you from accepting something
really simple, what do you think people will do to you?
Are they supposed to trust you again?
Geek gains will be reversed. You will just again be weird people no
one wants to be around any more, well, because a lot of you smell, and
you do STUPID INEXPLICABLE THINGS!
And I'm ranting again as this situation is incomprehensibly stupid.
James Harris
Mark Murray
> And I HATE ranting and posters just get on my case for ranting as they
> ALREADY MADE UP THEIR MINDS!!!
>
> But it's so frustrating when you have the math and it's so easy.
You're not so much ranting as whining. You're not getting your way, and
just like a petulant 4-year-old, you throw a tantrum.
With great inevitability you bring out SWJPAM and whine some more about
that.
Either do maths, or don't do maths. Either way, don't whine about it.
If you choose to do maths, FINISH it CHECK it THEN publish it. "Checking"
includes ensuring that it is correct, relevant and original (in more or
less that order). "Relevant" includes ensuring it somehow adds to maths
in a meaningful way and "Original" means it hasn't been done before.
Put heart-and-soul into avoiding writing essays about how great you are,
or whining about how the reception you got is not the mass adulation you
expected. Try to learn how real mathematicians do this.
M
--
Mark Murray
rossum
wrote:
You need to check that GCD(X, N) = 0 here. GCD > 0 gives you a factor
immediately. Trying to proceed will get you into all sorts of
trouble. 10^2 mod 35 = 30, but 30 is not a quadratic residue because
GCD(10, 35) = 5.
rossum
Arturo Magidin
> >I set up a routine to factor odd composites using the ideas you
> >listed.
> >The general idea is to get X^2 = Y^2 mod the target composite N.
>
> >X = 1, 2, 3, ...
>
> You need to check that GCD(X, N) = 0 here.
GCD(a,b) = 0 if and only if a=b=0, so no, he does not have to check
that.
> GCD > 0 gives you a factor
> immediately.
GCD(X,N) always gives you a factor of N; however, for it to be a
*nontrivial* factor, you ned to check 1 < GCD(X,N) < n.
--
ArturO Magidin
Enrico
> On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne...@aol.com>
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -
============================================
Remember, I'm testing James' method to see how it works.
I started with the ideal scene where:
GCD (X+Y, N) divides N
GCD (X -Y, N) divides N
With N a product of 2 primes, there seems to be 8 cases
repeating with period = N
There are also many cases where only one of the pair
of GCD's gives a factor - that works also.
For JSH's N = 35, (that's an upgrade from the 15 of old)
both GCD's fail 10 out of 35 times.
That means at least one of the GCD's will find a factor
25 out of 35 times -> 71 % of the time.
Trouble is, James stops there and celebrates. (Or rants)
As the size of the prime factors and the difference
between them increases, the odds of finding at least
one factor drops fast and seems to approach something
like trial division using GDC's.
Still, the method is interesting - seems to be a bit of
Pollard - Rho in there. Maybe. Its interesting to put
a prime in for N and see the pattern where it comes up.
Enrico
rossum
<mag...@member.ams.org> wrote:
>On Nov 6, 8:06 am, rossum <rossu...@coldmail.com> wrote:
>> On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne...@aol.com>
>> wrote:
>>
>>
>>
>
>> >I set up a routine to factor odd composites using the ideas you
>> >listed.
>> >The general idea is to get X^2 = Y^2 mod the target composite N.
>>
>> >X = 1, 2, 3, ...
>>
>> You need to check that GCD(X, N) = 0 here.
>
>GCD(a,b) = 0 if and only if a=b=0, so no, he does not have to check
>that.
Whoops.
1 Remove brain.
2 Wash brain.
3 Dry brain.
4 Reinsert brain.
Ahh, much better. Should have been GCD(X, N) = 1 of course.
Thanks for the correction.
>
>> GCD > 0 gives you a factor
>> immediately.
GCD > 1 and GCD < N
>
>GCD(X,N) always gives you a factor of N; however, for it to be a
>*nontrivial* factor, you ned to check 1 < GCD(X,N) < n.
Yes, that is what I meant to say, but my brain decided not to
cooperate. Naughty brain!
rossum
JSH
Nope. I stopped BEFORE using N=35, as I only did that recently to
demonstrate with a composite.
So I actually celebrated last year before I'd ever even done a
composite N, at all.
My original posting on this subject on my blog actually had an example
with N=19.
So then, what could possibly have made me so confident without having
worked a SINGLE composite example?
> As the size of the prime factors and the difference
> between them increases, the odds of finding at least
> one factor drops fast and seems to approach something
> like trial division using GDC's.
Then no worries!!!
> Still, the method is interesting - seems to be a bit of
> Pollard - Rho in there. Maybe. Its interesting to put
> a prime in for N and see the pattern where it comes up.
>
> Enrico
Nope, not Pollard - Rho. There's a linking between two
factorizations. You're leveraging one number to factor another.
You could say, the one number is helping you with information about
the other.
It can do that because it is intimately connected to the other number.
It's actually very beautiful mathematics.
Curiosity is a good thing, as without it you'll never understand the
result. It'll just be this weird mathematical mystery which you think
fails with increasing size of the number.
But why? What mathematical reason would there be beyond your
intuition that the bigger the number the harder to factor?
Any guesses?
James Harris
Enrico
>
> - Show quoted text -
===============================================
> But why? What mathematical reason would there be beyond your
> intuition that the bigger the number the harder to factor?
Direct observation of test results.
with N = 35, the factors 5 and 7 are swarming all over the page.
I have to look carefully to find cases where no factor is found.
If I increase the value of one factor, leaving the other one small,
the small one still occurs with the same density. The large one
is more thinly distributed and has to be searched for.
If I make both factors larger, both occur less frequently and have
to be fished for. The bigger I make them, the more thinly they are
distributed. The trend is obvious.
However, I'm not done yet - there are some more ways to tweak
this thing that I thought were impractical when I started.
Enrico
JSH
The algorithm has to work if:
T - f_1^2 is a quadratic residue modulo N.
But it will NOT work if that is not a quadratic residue modulo N.
With that information you should be able to fix your program as your
conclusions are wrong.
Size of N is irrelevant to the algorithm. It only cares at best about
the number of prime factors of N. Nothing else.
Notice that if the trivial factorization does NOT work on the first
try then it will not work for any T, as f_1 mod N will NOT change, so
the key relation will never hold.
James Harris
Mark Murray
> So then, what could possibly have made me so confident without having
> worked a SINGLE composite example?
Your usual arrogant hubris.
> It's actually very beautiful mathematics.
... like this.
M
--
Mark Murray
Enrico
================================================
Did a retake on T = 2q +jN
I've been using j = 1 only
With additional values of j things work alot better.
Enrico
JSH
Yeah I noticed that in your description, but if 2q - f_1^2 is NOT a
quadratic residue modulo N, then you won't get a solution so only one
trivial factorization need be checked.
> With additional values of j things work alot better.
>
> Enrico
Showing you the power of mathematical proof.
Examples can only do so much, though they can help clarify because I
only recently noticed that latest myself though it's in my research
results where it's been for over a year. I just didn't realize the
significance in this context until recently.
Surrogate factoring is already large enough that most of the answers
are buried somewhere in the equations.
But even I get lost often on the details.
IN any event, it's a beautiful little result. A fundamental
relationship between solutions to quadratic residues, and factoring.
James Harris
Mark Murray
> Showing you the power of mathematical proof.
Proof?
Where is the theorem?
M
--
Mark Murray
Enrico
=====================================================
> Yeah I noticed that in your description, but if 2q - f_1^2 is NOT a
> quadratic residue modulo N, then you won't get a solution so only one
> trivial factorization need be checked.
One thing bothers me here - how do you test if a number is a
quadratic
residue modulo a composite N without knowing its prime factors first?
As N gets larger than 35, the list of quadratic residues gets
unmanagably long.
Enrico
JSH
You don't. That result simply explains why you only need to check one
trivial factorization.
Though it also does tell you that you should only use any particular
residues for f_1 and f_2 once.
> As N gets larger than 35, the list of quadratic residues gets
> unmanagably long.
>
> Enrico
You decided to only check trivial factorizations so you had f_1 = 1.
YOU decided. Don't ask me why you decided to do that thing, but you
did.
Mathematically that runs into the reality that if a trivial
factorization will work, the very first one you check will work.
I simply corrected you.
The method is probabilistic. There is NO reason to ever check to see
if 2q - f_1^2 is a quadratic residue modulo N, except curiosity.
But that guarantee helps people to understand the power of this
method. It has an absolute check.
If 2q - f_1^2 is a quadratic residue modulo N, then it WILL work.
One thing that's important here is the reality of the denial in the
face of a fascinating method which actually has some extremely
intriguing mathematics associated with it!
My point is that many of you rip on and insult other people with the
absolute belief that they are worthless and their work is worthless in
a CLASS WAR. You feel some people are a second class in comparison to
yourselves.
So to you these peasants aren't capable of important work so you
decide their research isn't important and here you are foot-dragging
with a powerful method!
You are nothing more than wannabe royalty.
I'm simply proving it in a dramatic way. You're simply throwbacks to
a medieval age, who have your own dreams of ruling the world as a
dominant class with people like me beneath your feet.
Which is why you lie about math.
James Harris
Enrico
=====================================================
>
> Mathematically that runs into the reality that if a trivial
> factorization will work, the very first one you check will work.
>
This is not true.
A trivial factorization will always work on any odd composite N
coprime to 3. *** eventually ***, NEVER on the first one I check.
How do _you_ select "the very first one you check" ?
I start at x=1 and increment by 1 for each iteration.
I find R = X^2 mod N
2 * R + N factors as 1 and 2 * R + N, so
f1 + f2 = 1 + 2 * R + N
Multiply by 3^-1 mod N
(f1 + f2) * [3^-1 mod N]
Y = ((f1 + f2) * [3^-1 mod N]) mod N
then check Y^2 mod N to see if it equals X ^2 mod N
If they are equal, then the factors of N will split between
(X+Y) mod N and (X-Y) mod N
Enrico
JSH
Yes, it is. if 2q - f_1^2 is NOT a quadratic residue modulo N, then
you won't get the correct answer for k.
> A trivial factorization will always work on any odd composite N
No. It will not.
My guess is you're confused on the details.
If you're looking for q, such that q is a quadratic residue modulo N,
then you find f_1 and f_2 such that f_1*f_2 = 2q + jN, where j is a
nonzero integer.
With k^2 = q mod N, you will get k, from k = 3^{-1}(f_1 + f_2) iff 2q
- f_1^2 is a quadratic residue modulo N.
If you look only at f_1*f_2 where you have a trivial factorization,
then f_1 will not change, so if it doesn't work once, it will NEVER
work. (f_1 and f_2 are interchangeable)
> coprime to 3. *** eventually ***, NEVER on the first one I check.
I have given an example where the trivial factorization DID work on
the first one I checked.
> How do _you_ select "the very first one you check" ?
I use 2q + N. j=1.
I GAVE an example.
> I start at x=1 and increment by 1 for each iteration.
> I find R = X^2 mod N
> 2 * R + N factors as 1 and 2 * R + N, so
> f1 + f2 = 1 + 2 * R + N
> Multiply by 3^-1 mod N
> (f1 + f2) * [3^-1 mod N]
> Y = ((f1 + f2) * [3^-1 mod N]) mod N
> then check Y^2 mod N to see if it equals X ^2 mod N
>
> If they are equal, then the factors of N will split between
> (X+Y) mod N and (X-Y) mod N
>
> Enrico
I've explained the mathematics to you. It is a mathematical absolute--
unless I'm wrong--that 2q - f_1^2 MUST be a quadratic residue modulo N
for you to get the correct, such that k^2 = q mod N.
If that's wrong then my research is in serious trouble! If a
counterexample exists it should be easy for you to show one.
Oh, sorry but I have to add that I have seen cases where when faced
with absolute mathematics, people just kind of, make things up. It's
another way you can have mathematical proof and not get acceptance as
people claim problems that do not exist.
It is ANOTHER reason I went to the factoring problem, as with my other
research posters clearly understood that making things up could work
to prevent widespread knowledge of and acceptance of the research!
But it won't here. Yes, posters can deny the mathematics if they
wish, but it will not change anything.
It is your choice. If you all as a group wish to leave this
mathematics freely floating out there on the hopes no one will notice
then you are allowed to so act.
You've done so for a year. Maybe you wish another?
Remember your brain is what controls you. Reality is so much about
perception. You will tell yourselves whatever you need to hear, but
it does not mean that reality will not hold you accountable!
Fantasy cannot save you.
You are not royalty. You never were. You are not inherently better
than anyone else.
You are not noble blood. Let go of the fantasy!!! Let go.
James Harris
Enrico
================================================
Terrific.
How do you select the first q without using
the factors of N ?
(What you call q is what I call X^2 mod N)
Remember - I've got this whole thing on a speadsheet.
Conditional color coding to make the solutions
really obvious. I can type in any N and see the results
instantly. Most importantly - it duplicates your results
on the few examples you provided.
Experimental results trump theory unless the experiment
can be shown to be not a test of the theory. You'll want
that second option, which is why I gave you my algorithm.
Enrico
JSH
> On Nov 7, 9:19 pm, JSH <jst...@gmail.com> wrote:
<deleted>
That's trivial. Just pick a quadratic residue.
I like to use the first non-perfect square quadratic residue, but
check to be sure that it doesn't share prime factors with N.
Like with my example I used 8^2 = 29 mod 35 because while 7^2 = 14 mod
35, is a non-perfect square 14 is not coprime to 35.
> (What you call q is what I call X^2 mod N)
Yeah the quadratic residue. I got that part.
> Remember - I've got this whole thing on a speadsheet.
Ok.
> Conditional color coding to make the solutions
Sounds really funky, and the significance escapes me.
> really obvious. I can type in any N and see the results
> instantly. Most importantly - it duplicates your results
> on the few examples you provided.
Including k=9, with N=35, gives q = 11, as 81 = 11 mod 35? But the
trivial factorization didn't work, so I used the non-trivial
factorization.
From what I saw you're only using the trivial factorization, so how
would you replicate an example using a non-trivial one?
> Experimental results trump theory unless the experiment
But not mathematical proof.
The concept of mathematical proof seems to be escaping you.
It's not like just having a theory. A mathematical proof trumps all
else.
If an argument fails it was not a proof!!!
> can be shown to be not a test of the theory. You'll want
> that second option, which is why I gave you my algorithm.
>
> Enrico
I like getting notice of errors. If I yell "mathematical proof" and
you can show a counterexample then I don't have a proof. And in
finding out why, I learn something.
Here it's an easy process and you keep doing weird stuff, like only
doing trivial factorizations.
My take on what you think the argument is, is that you will keep
shifting q, the quadratic residue, and you're trying to say you always
can get to one that will work, with the trivial factorization.
So, you're trying to test this with only the trivial factorization,
which should only work with diminishing probability as the number of
quadratic residues rises, which would confirm a deep internal need you
may have for this to work less the larger N is.
So you gamed it. You put in your own arbitrary thing--not what I said
to do--which I can explain easily will give diminishing returns as N
increases in size.
Do you understand why? It's trivial to explain.
James Harris
Enrico
===========================================================
> > How do you select the first q without using
> > the factors of N ?
>
> That's trivial. Just pick a quadratic residue.
>
Oops. I've been doing that all along with X^2 mod n.
For some reason I had the idea that you were taking
a "random" number, testing it somehow to see if it's
a quadratic residue, then using it.
>
> Including k=9, with N=35, gives q = 11, as 81 = 11 mod 35? But the
> trivial factorization didn't work, so I used the non-trivial
> factorization.
>
> From what I saw you're only using the trivial factorization, so how
> would you replicate an example using a non-trivial one?
I put in a division check function when I was starting out so I could
make
sure I was getting the same numbers as you did. Putting in 3 as
the divisor gave me your numbers with k = 9, so I could be reasonably
sure my programming duplicated your method.
If I want to use the trivial factorization, I just type in 1 as the
divisor.
Crude and silly, dividing by 1, but simplest to program on the
spreadsheet, which is just a research tool to test out different
ideas.
>
> My take on what you think the argument is, is that you will keep
> shifting q, the quadratic residue, and you're trying to say you always
> can get to one that will work, with the trivial factorization.
>
This is correct, but turns out to be a very poor strategy as the
following example shows.
N = 187
q = 1, 2, 3, ...
Using trivial factorization, the first solution is at q = 43 giving
43 ^ 2 mod 187 = 166
111^2 mod 187 = 166
Using the strategy of trying all the factorizations gets
the first solution at q = 2 using the factorization of 195.
195 = 3 * 65 fails
195 = 5 * 39 fails
195 = 15*13 works, giving
2 ^ 2 mod 187 = 4
134 ^ 2 mod 187 = 4
and the GCD's produce both facors 11 and 17
Why did I keep on with the trivial factorization before?
I was hoping for an easy swindle on the math.
Didn't work, but was worth a try.
Enrico
JSH
If all residues are equally represented then the more residues you
have the less likely you are to get a particular residue, so that
approach would drop in success rate as N increases in size--getting
more residues.
> Didn't work, but was worth a try.
>
> Enrico
I don't see a problem with experimentation.
But I get really suspicious with an approach where I've explained why
it can't work well when it's thrown back at me, especially when I know
why that particular approach could play into a hidden bias against the
idea by leading to a drop in success with the increase in size of N.
Now being wrong is one thing, having people twist the data to their
ends is another, especially with the factoring problem.
And it's such a NEAT result!!! Who knew! This fundamental yet simple
relation connecting quadratic residues and factoring, and I'm just
using the most simple one.
There are an infinity of these relations that result from surrogate
factoring where I've just picked the first, which is probably the best
one anyway.
Dragging of the feet on this result proves my point that certain
people see themselves as part of a special society in a class war.
They don't care about the truth--they only care about "truths" that
support their class.
They are wannabe royalty living in their own version of a medieval
world with themselves as the nobility, pretending to be something
else.
Real researchers would be excited with the result, worried about the
consequences, and anxious to see how much more they could learn.
Those of you who are the fakes instead are wishing this thing would go
away, or that hopefully it's not true.
And then you are not real researchers. You simply got away with
playing pretend.
And you are parasites on the world.
James Harris