 |
|
| Science Forum Index » Cryptography Forum » Factoring to solve quadratic residues... |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| JSH... |
 Posted: Mon Nov 02, 2009 3:19 pm |
|
|
|
Guest
|
There is another relation between factoring and quadratic residues
using simple congruences.
Given a quadratic residue q modulo N, where N is a non-unit odd
natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find T = 2q mod N
where T = 2q + jN, and j is a non-zero integer.
You next check each factorization of T to find positive f_1 and f_2
where f_1*f_2 = T and then you get k from
k = 3^{-1}(f_1 + f_2) mod N
where for roughly 50% of cases you will get a k that will work.
So let's try it. Let N = 35, as that's simple enough, and q=29 (I'll
explain how I picked it later). Then, T = 2(29) mod 35, which is T =
23 mod 35.
The first possible T is T = 93, and it does work with f_1 = 93, and
f_2 = 1 (so yes, trivial factorizations can work), as I get:
k = 3^{-1}(93 + 1) mod 35 = 12(94) mod 35 = 1128 mod 35 = 8 mod 35.
And k = 8 mod 35 is a correct answer.
And now you can see how I picked that example as knowing that 35 has 5
and 7 as factors I picked the first k that would not give a perfect
square:
8^2 = 29 mod 35
Result follows from linking factorizations together.
James Harris |
|
|
| Back to top |
|
|
|
| Mark Murray... |
| Posted: Tue Nov 03, 2009 4:45 am |
|
|
|
Guest
|
JSH wrote:
[quote]Result follows from linking factorizations together.
[/quote]
....and therefore you are an unrecognised great discoverer with an army
of enemies yadda yadda yadda SWJPAM yadda yadda ...
Get on with it.
M
--
Mark Murray |
|
|
| Back to top |
|
|
|
| rossum... |
| Posted: Tue Nov 03, 2009 7:33 am |
|
|
|
Guest
|
On Mon, 2 Nov 2009 17:19:44 -0800 (PST), JSH <jstevh at (no spam) gmail.com> wrote:
[quote]There is another relation between factoring and quadratic residues
using simple congruences.
Given a quadratic residue q modulo N, where N is a non-unit odd
natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find T = 2q mod N
where T = 2q + jN, and j is a non-zero integer.
Yup, I follow that. I will come back to this equation below.[/quote]
[quote]
You next check each factorization of T to find positive f_1 and f_2
where f_1*f_2 = T and then you get k from
k = 3^{-1}(f_1 + f_2) mod N
where for roughly 50% of cases you will get a k that will work.
So let's try it. Let N = 35, as that's simple enough, and q=29 (I'll
explain how I picked it later). Then, T = 2(29) mod 35, which is T =
23 mod 35.
The first possible T is T = 93,
Why? Going back to T = 2q + jN from above, the first positive value[/quote]
for T I get is T = 23 with j = -1. You say that j must be a non-zero
integer and -1 is a non-zero integer. Why are you not trying this
value of j?
Factorising: 23 -> (1, 23)
3^(-1) mod 35 = 12
12 * (1 + 23) = 288 = 8 mod 35
8^2 = 64 = 29 mod 35
You have missed a solution by ignoring j = -1.
It is also worth noting that the numbers used are smaller than those
needed for larger values of j which will help speed up calculations
when working with numbers of cryptographic size.
rossum
[quote]and it does work with f_1 = 93, and
f_2 = 1 (so yes, trivial factorizations can work), as I get:
k = 3^{-1}(93 + 1) mod 35 = 12(94) mod 35 = 1128 mod 35 = 8 mod 35.
And k = 8 mod 35 is a correct answer.
And now you can see how I picked that example as knowing that 35 has 5
and 7 as factors I picked the first k that would not give a perfect
square:
8^2 = 29 mod 35
Result follows from linking factorizations together.
James Harris[/quote] |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Tue Nov 03, 2009 2:54 pm |
|
|
|
Guest
|
On Nov 3, 4:33 am, rossum <rossu... at (no spam) coldmail.com> wrote:
[quote]On Mon, 2 Nov 2009 17:19:44 -0800 (PST), JSH <jst... at (no spam) gmail.com> wrote:
There is another relation between factoring and quadratic residues
using simple congruences.
Given a quadratic residue q modulo N, where N is a non-unit odd
natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find T = 2q mod N
where T = 2q + jN, and j is a non-zero integer.
Yup, I follow that. I will come back to this equation below.
You next check each factorization of T to find positive f_1 and f_2
where f_1*f_2 = T and then you get k from
k = 3^{-1}(f_1 + f_2) mod N
where for roughly 50% of cases you will get a k that will work.
So let's try it. Let N = 35, as that's simple enough, and q=29 (I'll
explain how I picked it later). Then, T = 2(29) mod 35, which is T > >23 mod 35.
The first possible T is T = 93,
Why? Going back to T = 2q + jN from above, the first positive value
for T I get is T = 23 with j = -1. You say that j must be a non-zero
integer and -1 is a non-zero integer. Why are you not trying this
value of j?
[/quote]
I don't remember.
[quote] Factorising: 23 -> (1, 23)
3^(-1) mod 35 = 12
12 * (1 + 23) = 288 = 8 mod 35
8^2 = 64 = 29 mod 35
You have missed a solution by ignoring j = -1.
[/quote]
Oh. Interesting.
[quote]It is also worth noting that the numbers used are smaller than those
needed for larger values of j which will help speed up calculations
when working with numbers of cryptographic size.
rossum
[/quote]
Yeah if you wanted to do big numbers you'd want to make it easy.
Result is over a year old. I'm just re-hashing old news.
I figured out how to solve quadratic residues mod N, where N is a
prime or a composite, about a year ago.
I think now is somewhere around the actual 1 year anniversary.
Isn't the world fascinating? Of course, I guess some might think it
doesn't work well, but I don't know as I've only tested it on small
numbers
But wouldn't it be interesting if you people kept going for an entire
YEAR after the factoring problem was solved?
And either didn't know it or just kind of figured, why care?
Factoring problem was solved a year ago. If you missed that news,
why?
James Harris |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Wed Nov 04, 2009 3:49 pm |
|
|
|
Guest
|
On Nov 2, 5:19 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]There is another relation between factoring and quadratic residues
using simple congruences.
Given a quadratic residue q modulo N, where N is a non-unit odd
natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find T = 2q mod N
where T = 2q + jN, and j is a non-zero integer.
You next check each factorization of T to find positive f_1 and f_2
where f_1*f_2 = T and then you get k from
k = 3^{-1}(f_1 + f_2) mod N
where for roughly 50% of cases you will get a k that will work.
[/quote]
One important requirement I should mention is that (f_1 + f_2)/2 > N
must be true.
What I found is actually a fundamental set of congruences at the heart
of factoring.
IF they had been known before, it's hard to see why anyone would have
thought that factoring was a hard problem.
Proving the result is easy as it's trivial algebra. And the variable
k is critical as I just found relations where its square modulo N is
given in one place, and it's value modulo N is given in another by a
factorization. That's all.
Why your field seems to think it can just ignore this result is beyond
me, but you've been doing it for a year already.
My suspicion is that many of you disdain simple solutions, and WORSHIP
unneeded complexity.
You hate simple answers as you get bragging rights from abstruse
complex mathematics that you believe a select few in the world
understands.
In your minds then, a simple answer cannot exist, so you refuse to
accept that it DOES exist, even when the mathematics is presented to
you.
It is how you feel special, your knowledge. So a simple answer cuts
at your egos. So your egos simply pretend it does not exist.
So celebrate the sad birthday of the solution to the factoring problem
this month. The answer your society has willfully ignored.
James Harris |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Wed Nov 04, 2009 4:29 pm |
|
|
|
Guest
|
On Nov 4, 6:13 pm, Calvin Ramsey <calram... at (no spam) oaken.net> wrote:
[quote]JSH wrote:
On Nov 2, 5:19 pm, JSH <jst... at (no spam) gmail.com> wrote:
There is another relation between factoring and quadratic residues
using simple congruences.
Given a quadratic residue q modulo N, where N is a non-unit odd
natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find T = 2q mod N
where T = 2q + jN, and j is a non-zero integer.
You next check each factorization of T to find positive f_1 and f_2
where f_1*f_2 = T and then you get k from
k = 3^{-1}(f_1 + f_2) mod N
where for roughly 50% of cases you will get a k that will work.
One important requirement I should mention is that (f_1 + f_2)/2 > N
must be true.
What I found is actually a fundamental set of congruences at the heart
of factoring.
IF they had been known before, it's hard to see why anyone would have
thought that factoring was a hard problem.
Proving the result is easy as it's trivial algebra. And the variable
k is critical as I just found relations where its square modulo N is
given in one place, and it's value modulo N is given in another by a
factorization. That's all.
Why your field seems to think it can just ignore this result is beyond
me, but you've been doing it for a year already.
My suspicion is that many of you disdain simple solutions, and WORSHIP
unneeded complexity.
You hate simple answers as you get bragging rights from abstruse
complex mathematics that you believe a select few in the world
understands.
In your minds then, a simple answer cannot exist, so you refuse to
accept that it DOES exist, even when the mathematics is presented to
you.
It is how you feel special, your knowledge. So a simple answer cuts
at your egos. So your egos simply pretend it does not exist.
So celebrate the sad birthday of the solution to the factoring problem
this month. The answer your society has willfully ignored.
James Harris
This is some of the best free comedy entertainment I've seen in a long time.
Do you do stand-up comedy on the side, James?
[/quote]
No.
[quote]Is that what you do when you're not here?
Maybe you should think about it. You'd probably have better success at
that than you have with math.
[/quote]
I have thought about it, and that's actually not a bad suggestion!
[quote]Hey, I'm just saying.
[/quote]
It's a weird situation. You don't believe I have anything and I do,
so I'm saying things that make sense from my perspective and you say
things that makes sense from yours.
Nothing complicated in that.
James Harris |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Wed Nov 04, 2009 4:40 pm |
|
|
|
Guest
|
On Nov 4, 5:49 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 2, 5:19 pm, JSH <jst... at (no spam) gmail.com> wrote:
There is another relation between factoring and quadratic residues
using simple congruences.
Given a quadratic residue q modulo N, where N is a non-unit odd
natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find T = 2q mod N
where T = 2q + jN, and j is a non-zero integer.
You next check each factorization of T to find positive f_1 and f_2
where f_1*f_2 = T and then you get k from
k = 3^{-1}(f_1 + f_2) mod N
where for roughly 50% of cases you will get a k that will work.
One important requirement I should mention is that (f_1 + f_2)/2 > N
must be true.
[/quote]
No, I don't think that's necessary. Kind of fumbling here now... Ok,
I'll do another example.
My first example was with k=8, using q = 29 modulo 35, as that's the
first case where the quadratic residue is not a perfect square (though
this method WILL solve a perfect square as well I should add).
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.)
The saner among you may realize that even if someway, somehow this
doesn't solve the factoring problem, there is no other known method
that solves quadratic residues modulo N in this way.
Reality is, this result seems to be driving some of you bonkers so you
aren't reacting like you should, so people waiting for someone else to
do the right thing need to understand--they're mentally gone.
With some of my other research I noticed an odd trend where
mathematicians would suddenly go on sabbatical when faced with my
research. I'm in the U.S. and in the couple of times that happened
here that I noticed it, the mathematicians actually LEFT THE COUNTRY
during the sabbatical.
In one case, I'd convinced a non-mathematician academic to get a
mathematician colleague to look over my prime counting function. Guy
not only went on sabbatical--left the freaking country--but when he
came back, he claimed to not remember the request, but no he wasn't
interested in looking over my math....
Fun result here people. No way the saner among you can think it's not
important.
Humanity has a way to solve quadratic residues modulo N where the
result is celebrating its 1 year anniversary this month.
Believe it. Just do the math. I gave you one more example. Clearly
I'm not cherry-picking as k=8 gave the first non-square quadratic
residue and I just did k=9, just stepping up by 1. Not cherry-
picking.
James Harris |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Wed Nov 04, 2009 4:44 pm |
|
|
|
Guest
|
On Nov 4, 5:33 pm, n... at (no spam) dont-mail-me.com (Robert Scott) wrote:
[quote]You know, James, it would be much more convincing if, instead of presenting
mathematical proofs, you simply used your method to find someone's RSA private
key. Why haven't you done that? It can't be because it's hard, is it?
[/quote]
Because, say, I took the program to the FBI, as I couldn't just give
it out, and I couldn't just display the result because there is
national security impact. Where would the FBI take me? To the NSA--
the largest concentration of professional mathematicians in the
world. Math people hate me.
They might argue national security reasons against reason to hide the
result from the world, oh, and by the way, hide ME.
I could end up in a nice prison or squalid one where with the "nice"
they just wouldn't call it prison, but it would be one just the same.
Nope, looking for a group action here! I need a critical mass of
people so they can't round us all up and lock us away!
Here's the next example I've given in another reply in this thread.
Reminding you this technique does work.
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.)
(Oh yeah, I suspect math people know the above scenario is likely
where I end up imprisoned if I prove with a very large factorization,
which is why they taunt me to factor an RSA key, hoping then that
national security tough guys would solve their problem--me--for them.)
James Harris |
|
|
| Back to top |
|
|
|
| Robert Scott... |
| Posted: Wed Nov 04, 2009 8:33 pm |
|
|
|
Guest
|
You know, James, it would be much more convincing if, instead of presenting
mathematical proofs, you simply used your method to find someone's RSA private
key. Why haven't you done that? It can't be because it's hard, is it? |
|
|
| Back to top |
|
|
|
| Calvin Ramsey... |
| Posted: Wed Nov 04, 2009 9:13 pm |
|
|
|
Guest
|
JSH wrote:
[quote]On Nov 2, 5:19 pm, JSH <jst... at (no spam) gmail.com> wrote:
There is another relation between factoring and quadratic residues
using simple congruences.
Given a quadratic residue q modulo N, where N is a non-unit odd
natural number coprime to 3, where you wish to find k, where
k^2 = q mod N
you first find T = 2q mod N
where T = 2q + jN, and j is a non-zero integer.
You next check each factorization of T to find positive f_1 and f_2
where f_1*f_2 = T and then you get k from
k = 3^{-1}(f_1 + f_2) mod N
where for roughly 50% of cases you will get a k that will work.
One important requirement I should mention is that (f_1 + f_2)/2 > N
must be true.
What I found is actually a fundamental set of congruences at the heart
of factoring.
IF they had been known before, it's hard to see why anyone would have
thought that factoring was a hard problem.
Proving the result is easy as it's trivial algebra. And the variable
k is critical as I just found relations where its square modulo N is
given in one place, and it's value modulo N is given in another by a
factorization. That's all.
Why your field seems to think it can just ignore this result is beyond
me, but you've been doing it for a year already.
My suspicion is that many of you disdain simple solutions, and WORSHIP
unneeded complexity.
You hate simple answers as you get bragging rights from abstruse
complex mathematics that you believe a select few in the world
understands.
In your minds then, a simple answer cannot exist, so you refuse to
accept that it DOES exist, even when the mathematics is presented to
you.
It is how you feel special, your knowledge. So a simple answer cuts
at your egos. So your egos simply pretend it does not exist.
So celebrate the sad birthday of the solution to the factoring problem
this month. The answer your society has willfully ignored.
James Harris
[/quote]
This is some of the best free comedy entertainment I've seen in a long time.
Do you do stand-up comedy on the side, James?
Is that what you do when you're not here?
Maybe you should think about it. You'd probably have better success at
that than you have with math.
Hey, I'm just saying. |
|
|
| Back to top |
|
|
|
| Mark Murray... |
| Posted: Thu Nov 05, 2009 3:20 am |
|
|
|
Guest
|
JSH wrote:
[quote]On Nov 4, 5:33 pm, n... at (no spam) dont-mail-me.com (Robert Scott) wrote:
You know, James, it would be much more convincing if, instead of presenting
mathematical proofs, you simply used your method to find someone's RSA private
key. Why haven't you done that? It can't be because it's hard, is it?
Because, say, I took the program to the FBI, as I couldn't just give
it out, and I couldn't just display the result because there is
national security impact. Where would the FBI take me? To the NSA--
the largest concentration of professional mathematicians in the
world. Math people hate me.
[/quote]
Some hate you because you are an intensely persistent waste of time, and a
crank.
Others hate you because you are a pompous ass.
Others don't hate you, but laugh at your puerile attempts to gain fame
as a mathematician.
There are loads of other classes; in no significant number of people are
there those who take your mathematics seriously.
[quote]They might argue national security reasons against reason to hide the
result from the world, oh, and by the way, hide ME.
[/quote]
You are no threat to national security with your mathematics. You are
potentially much more dangerous with objects found in (say) your kitchen.
M
--
Mark Murray |
|
|
| Back to top |
|
|
|
| Mark Murray... |
| Posted: Thu Nov 05, 2009 3:21 am |
|
|
|
Guest
|
JSH wrote:
[quote]No, I don't think that's necessary. Kind of fumbling here now... Ok,
I'll do another example.
[/quote]
Stop the bloody fumbling, complete the work, CHECK it, THEN publish.
M
--
Mark Murray |
|
|
| Back to top |
|
|
|
| rossum... |
| Posted: Thu Nov 05, 2009 7:23 am |
|
|
|
Guest
|
On Wed, 4 Nov 2009 18:40:07 -0800 (PST), JSH <jstevh at (no spam) gmail.com> wrote:
[quote]No, I don't think that's necessary. Kind of fumbling here now... Ok,
I'll do another example.
Why are you still 'fumbling' with this James? A complete working and[/quote]
proven solution needs no 'fumbling'.
You are doing you own credibility no good at all here.
Once again James, check everything thoroughly before you post it. You
know that you can make mistakes yet you fail to take the obvious steps
to minimise those mistakes.
Sometimes you are your own worst enemy.
rossum |
|
|
| Back to top |
|
|
|
| Robert Scott... |
| Posted: Thu Nov 05, 2009 9:06 am |
|
|
|
Guest
|
On Wed, 4 Nov 2009 18:44:36 -0800 (PST), JSH <jstevh at (no spam) gmail.com> wrote:
[quote]Because, say, I took the program to the FBI, as I couldn't just give
it out, and I couldn't just display the result because there is
national security impact. Where would the FBI take me?...
[/quote]
If what you say is true, then your posting the theory of this method (which you
claim to have done a year ago) already puts you in grave danger. Why are you
still free? But you would not need to take anything to the FBI. Just crack one
publicly-known public RSA key, and send the private key privately to just one of
your critics here. That person would be instantly convinced, and throw his
reputation behind your cause, and you would have your desired group effect. You
would be putting yourself in no more danger than you are already in, which is
none (except, as has been previously noted, from your kitchen implements). |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Thu Nov 05, 2009 4:37 pm |
|
|
|
Guest
|
On Nov 5, 6:06 am, n... at (no spam) dont-mail-me.com (Robert Scott) wrote:
[quote]On Wed, 4 Nov 2009 18:44:36 -0800 (PST), JSH <jst... at (no spam) gmail.com> wrote:
Because, say, I took the program to the FBI, as I couldn't just give
it out, and I couldn't just display the result because there is
national security impact. Where would the FBI take me?...
If what you say is true, then your posting the theory of this method (which you
claim to have done a year ago) already puts you in grave danger. Why are you
[/quote]
Academic mathematicians in the US won't report the result! And the
NSA relies on academics for research at this level.
They're protecting their turf!!!
The only way to get the attention of the NSA would be to factor a very
large number.
So the catch is that academic mathematicians refuse to acknowledge it,
so there is no trigger for any of the big security organizations.
[quote]still free? But you would not need to take anything to the FBI. Just crack one
publicly-known public RSA key, and send the private key privately to just one of
your critics here. That person would be instantly convinced, and throw his
[/quote]
From past situations with my other math research said person would
probably snap.
That is, go completely bonkers.
Besides, if they did the right thing, they'd go to the FBI--as they
probably can't even get to the NSA--and then they'd end up imprisoned
along with me, and it might be a nice place or a harsh place but no
matter how nice it was or what it was called it would be prison.
[quote]reputation behind your cause, and you would have your desired group effect. You
would be putting yourself in no more danger than you are already in, which is
none (except, as has been previously noted, from your kitchen implements)..
[/quote]
Nope. I'm safe now because mathematicians won't acknowledge the
result.
So there is no trigger for the NSA. They rely on the academic
mathematicians!
That means I can simply talk about the result as a research result--
which it is--popularizing the solving by quadratic residues modulo N.
More than likely researchers in some other country than the US will
realize it works, and the news will spread rapidly, get back to this
country, and then I'll chat with the NSA without worry of
disappearing.
And I'll explain to president Obama at that time as well as probably
some Senate committees.
James Harris |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Dec 04, 2009 1:30 pm
|
|