 |
|
| Science Forum Index » Cryptography Forum » Factoring to solve quadratic residues... |
|
Page 2 of 2 Goto page Previous 1, 2 |
|
| Author |
Message |
| Tim Peters... |
 Posted: Thu Nov 05, 2009 7:39 pm |
|
|
|
Guest
|
[JSH <jstevh at (no spam) gmail.com>]
[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.
[/quote]
Poor James. It already happened, but you don't remember. That was part of
their plan for you, and it's working brilliantly. They actually succeeded
at brainwashing you into believing that periodically destroying your
credibility with lunatic ranting was /your/ idea! It wasn't. It was
theirs. |
|
|
| Back to top |
|
|
|
| Lits O'Hate... |
| Posted: Fri Nov 06, 2009 9:56 am |
|
|
|
Guest
|
On Nov 5, 9:37 pm, James "Google SWJPAM" Harris wrote:
[quote]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.
[/quote]
Yep. That's probably what will happen.
--
"The factoring problem was solved about a year ago, and you
people just failed to notice because you're pig-headed, arrogant,
and also kind of dumb, unfortunately, despite your pretensions to
the contrary." -- James Harris |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Fri Nov 06, 2009 4:21 pm |
|
|
|
Guest
|
On Nov 4, 6:40 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 4, 5:49 pm, JSH <jst... at (no spam) gmail.com> 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.
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.)
[/quote]
Oh yeah, if T - f_1^2 is a quadratic residue modulo N, then that f_1
and f_2 must work to give you k.
Turns out that follow from another fundamental result:
T - k^2 - f_1^2 = 0 mod N
The interested reader can verify that relation with the solutions
given.
James Harris |
|
|
| Back to top |
|
|
|
| rossum... |
| Posted: Fri Nov 06, 2009 5:31 pm |
|
|
|
Guest
|
On Thu, 5 Nov 2009 18:37:26 -0800 (PST), JSH <jstevh at (no spam) gmail.com> wrote:
[quote]And I'll explain to president Obama at that time as well as probably
some Senate committees.
Better get a move on James, you only have until January 2017 at the[/quote]
most before someone else takes over, or do you think that Michelle is
going to do a Hilary?
rossum |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Tue Dec 08, 2009 10:47 pm
|
|