 |
|
| Science Forum Index » Cryptography Forum » JSH: This factoring thing is scary... |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| JSH... |
 Posted: Wed Nov 04, 2009 4:53 pm |
|
|
|
Guest
|
You people need to wake up. I'm telling you the underlying math is
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)(2 = 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 |
|
|
| Back to top |
|
|
|
| Mark Murray... |
| Posted: Thu Nov 05, 2009 3:23 am |
|
|
|
Guest
|
JSH wrote:
[quote]Factoring problem solved.
[/quote]
Where is the complexity analysis?
M
--
Mark Murray |
|
|
| Back to top |
|
|
|
| amzoti... |
| Posted: Thu Nov 05, 2009 9:12 am |
|
|
|
Guest
|
On Nov 4, 6:53 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]
James Harris
[/quote]
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! |
|
|
| Back to top |
|
|
|
| bert... |
| Posted: Thu Nov 05, 2009 11:55 am |
|
|
|
Guest
|
On 5 Nov, 08:23, Mark Murray <w.h.o... at (no spam) example.com> wrote:
[quote]JSH wrote:
Factoring problem solved.
Where is the complexity analysis?
[/quote]
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.
-- |
|
|
| Back to top |
|
|
|
| Jens Stuckelberger... |
| Posted: Thu Nov 05, 2009 12:56 pm |
|
|
|
Guest
|
On Wed, 04 Nov 2009 18:53:20 -0800, JSH wrote:
[quote][What can he write but crap?]
[/quote]
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. |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Thu Nov 05, 2009 4:29 pm |
|
|
|
Guest
|
On Nov 4, 6:53 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]You people need to wake up. I'm telling you the underlying math is
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.)
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Enrico... |
| Posted: Thu Nov 05, 2009 6:41 pm |
|
|
|
Guest
|
On Nov 4, 7:53 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]You people need to wake up. I'm telling you the underlying math is
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)(2 = 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
[/quote]
=====================================================
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 |
|
|
| Back to top |
|
|
|
| Mark Murray... |
| Posted: Thu Nov 05, 2009 6:51 pm |
|
|
|
Guest
|
bert wrote:
[quote]On 5 Nov, 08:23, Mark Murray <w.h.o... at (no spam) example.com> wrote:
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.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Thu Nov 05, 2009 7:42 pm |
|
|
|
Guest
|
On Nov 5, 8:41 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
[quote]On Nov 4, 7:53 pm, JSH <jst... at (no spam) gmail.com> wrote:
You people need to wake up. I'm telling you the underlying math is
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)(2 = 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
=====================================================
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
[/quote]
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 |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Thu Nov 05, 2009 7:48 pm |
|
|
|
Guest
|
On Nov 5, 9:42 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 5, 8:41 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 4, 7:53 pm, JSH <jst... at (no spam) gmail.com> wrote:
You people need to wake up. I'm telling you the underlying math is
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)(2 = 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
=====================================================
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
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
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Mark Murray... |
| Posted: Fri Nov 06, 2009 3:00 am |
|
|
|
Guest
|
JSH wrote:
[quote]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.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Arturo Magidin... |
| Posted: Fri Nov 06, 2009 6:32 am |
|
|
|
Guest
|
On Nov 6, 8:06 am, rossum <rossu... at (no spam) coldmail.com> wrote:
[quote]On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne... at (no spam) 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.
[/quote]
GCD(a,b) = 0 if and only if a=b=0, so no, he does not have to check
that.
[quote] GCD > 0 gives you a factor
immediately.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| rossum... |
| Posted: Fri Nov 06, 2009 9:06 am |
|
|
|
Guest
|
On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungernerik at (no spam) aol.com>
wrote:
[quote]On Nov 4, 7:53Â pm, JSH <jst... at (no spam) gmail.com> wrote:
You people need to wake up. Â I'm telling you the underlying math is
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)(2 = 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
======================================================
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 > 0 gives you a factor[/quote]
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
[quote]
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[/quote] |
|
|
| Back to top |
|
|
|
| Enrico... |
| Posted: Fri Nov 06, 2009 11:04 am |
|
|
|
Guest
|
On Nov 6, 7:06 am, rossum <rossu... at (no spam) coldmail.com> wrote:
[quote]On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne... at (no spam) aol.com
wrote:
On Nov 4, 7:53 pm, JSH <jst... at (no spam) gmail.com> wrote:
You people need to wake up. I'm telling you the underlying math is
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)(2 = 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
=====================================================
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 > 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
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- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
[/quote]
===========================================
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 |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Fri Nov 06, 2009 3:55 pm |
|
|
|
Guest
|
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
[quote]On Nov 6, 7:06 am, rossum <rossu... at (no spam) coldmail.com> wrote:
On Thu, 5 Nov 2009 20:41:32 -0800 (PST), Enrico <ungerne... at (no spam) aol.com
wrote:
On Nov 4, 7:53 pm, JSH <jst... at (no spam) gmail.com> wrote:
You people need to wake up. I'm telling you the underlying math is
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)(2 = 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
=====================================================
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 > 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
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- Hide quoted text -
- 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)
[/quote]
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?
[quote]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.
[/quote]
Then no worries!!!
[quote]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
[/quote]
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 |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Tue Dec 01, 2009 8:15 pm
|
|