 |
|
| Science Forum Index » Cryptography Forum » JSH: This factoring thing is scary... |
|
Page 2 of 2 Goto page Previous 1, 2 |
|
| Author |
Message |
| Enrico... |
 Posted: Fri Nov 06, 2009 4:49 pm |
|
|
|
Guest
|
On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- Show quoted text -
[/quote]
==============================================
[quote]But why? What mathematical reason would there be beyond your
intuition that the bigger the number the harder to factor?
[/quote]
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 |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Fri Nov 06, 2009 4:57 pm |
|
|
|
Guest
|
On Nov 6, 6:49 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
[quote]On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- 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
[/quote]
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 |
|
|
| Back to top |
|
|
|
| rossum... |
| Posted: Fri Nov 06, 2009 5:35 pm |
|
|
|
Guest
|
On Fri, 6 Nov 2009 08:32:29 -0800 (PST), Arturo Magidin
<magidin at (no spam) member.ams.org> wrote:
[quote]On Nov 6, 8: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:
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.[/quote]
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.
[quote]
 GCD > 0 gives you a factor
immediately.
GCD > 1 and GCD < N[/quote]
[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.
Yes, that is what I meant to say, but my brain decided not to[/quote]
cooperate. Naughty brain!
rossum |
|
|
| Back to top |
|
|
|
| Mark Murray... |
| Posted: Sat Nov 07, 2009 3:24 am |
|
|
|
Guest
|
JSH wrote:
[quote]So then, what could possibly have made me so confident without having
worked a SINGLE composite example?
[/quote]
Your usual arrogant hubris.
[quote]It's actually very beautiful mathematics.
[/quote]
.... like this.
M
--
Mark Murray |
|
|
| Back to top |
|
|
|
| Enrico... |
| Posted: Sat Nov 07, 2009 6:57 am |
|
|
|
Guest
|
On Nov 6, 7:57 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 6, 6:49 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- 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
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- Hide quoted text -
- Show quoted text -
[/quote]
===============================================
Did a retake on T = 2q +jN
I've been using j = 1 only
With additional values of j things work alot better.
Enrico |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Sat Nov 07, 2009 7:42 am |
|
|
|
Guest
|
On Nov 7, 8:57 am, Enrico <ungerne... at (no spam) aol.com> wrote:
[quote]On Nov 6, 7:57 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 6:49 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- 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
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- Hide quoted text -
- Show quoted text -
===============================================
Did a retake on T = 2q +jN
I've been using j = 1 only
[/quote]
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.
[quote]With additional values of j things work alot better.
Enrico
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Enrico... |
| Posted: Sat Nov 07, 2009 2:26 pm |
|
|
|
Guest
|
On Nov 7, 10:42 am, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 7, 8:57 am, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 7:57 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 6:49 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- 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
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- Hide quoted text -
- Show quoted text -
===============================================
Did a retake on T = 2q +jN
I've been using j = 1 only
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- Hide quoted text -
- Show quoted text -
[/quote]
====================================================
[quote]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.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Sat Nov 07, 2009 4:46 pm |
|
|
|
Guest
|
On Nov 7, 4:26 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
[quote]On Nov 7, 10:42 am, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 7, 8:57 am, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 7:57 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 6:49 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- 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
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- Hide quoted text -
- Show quoted text -
===============================================
Did a retake on T = 2q +jN
I've been using j = 1 only
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- Hide quoted text -
- Show quoted text -
====================================================
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?
[/quote]
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.
[quote]As N gets larger than 35, the list of quadratic residues gets
unmanagably long.
Enrico
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Mark Murray... |
| Posted: Sat Nov 07, 2009 5:39 pm |
|
|
|
Guest
|
JSH wrote:
[quote]Showing you the power of mathematical proof.
[/quote]
Proof?
Where is the theorem?
M
--
Mark Murray |
|
|
| Back to top |
|
|
|
| Enrico... |
| Posted: Sat Nov 07, 2009 5:58 pm |
|
|
|
Guest
|
On Nov 7, 7:46 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 7, 4:26 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 7, 10:42 am, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 7, 8:57 am, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 7:57 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 6:49 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- 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
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- Hide quoted text -
- Show quoted text -
===============================================
Did a retake on T = 2q +jN
I've been using j = 1 only
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- Hide quoted text -
- Show quoted text -
====================================================
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?
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
[/quote]
====================================================
[quote]
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.[/quote]
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 |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Sat Nov 07, 2009 6:19 pm |
|
|
|
Guest
|
On Nov 7, 7:58 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
[quote]On Nov 7, 7:46 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 7, 4:26 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 7, 10:42 am, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 7, 8:57 am, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 7:57 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 6:49 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- 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
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- Hide quoted text -
- Show quoted text -
===============================================
Did a retake on T = 2q +jN
I've been using j = 1 only
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- Hide quoted text -
- Show quoted text -
====================================================
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?
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
====================================================
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.
[/quote]
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.
[quote]A trivial factorization will always work on any odd composite N
[/quote]
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)
[quote]coprime to 3. *** eventually ***, NEVER on the first one I check.
[/quote]
I have given an example where the trivial factorization DID work on
the first one I checked.
[quote]How do _you_ select "the very first one you check" ?
[/quote]
I use 2q + N. j=1.
I GAVE an example.
[quote]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
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Enrico... |
| Posted: Sat Nov 07, 2009 7:11 pm |
|
|
|
Guest
|
On Nov 7, 9:19 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 7, 7:58 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 7, 7:46 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 7, 4:26 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 7, 10:42 am, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 7, 8:57 am, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 7:57 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 6:49 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 6, 6:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 6, 1:04 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
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)
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- Hide quoted text -
- 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
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- Hide quoted text -
- Show quoted text -
===============================================
Did a retake on T = 2q +jN
I've been using j = 1 only
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- Hide quoted text -
- Show quoted text -
====================================================
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?
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
====================================================
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.
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- Hide quoted text -
- Show quoted text -
[/quote]
===============================================
[quote]How do _you_ select "the very first one you check" ?
[/quote]
[quote]I use 2q + N. j=1.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Sat Nov 07, 2009 7:55 pm |
|
|
|
Guest
|
On Nov 7, 9:11 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
[quote]On Nov 7, 9:19 pm, JSH <jst... at (no spam) gmail.com> wrote:
[/quote]
<deleted>
[quote]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.
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- Hide quoted text -
- Show quoted text -
===============================================
How do _you_ select "the very first one you check" ?
I use 2q + N. j=1.
Terrific.
How do you select the first q without using
the factors of N ?
[/quote]
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.
[quote](What you call q is what I call X^2 mod N)
[/quote]
Yeah the quadratic residue. I got that part.
[quote]Remember - I've got this whole thing on a speadsheet.
[/quote]
Ok.
[quote]Conditional color coding to make the solutions
[/quote]
Sounds really funky, and the significance escapes me.
[quote]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.
[/quote]
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?
[quote]Experimental results trump theory unless the experiment
[/quote]
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!!!
[quote]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
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Enrico... |
| Posted: Sun Nov 08, 2009 7:08 am |
|
|
|
Guest
|
On Nov 7, 10:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
[quote]On Nov 7, 9:11 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 7, 9:19 pm, JSH <jst... at (no spam) gmail.com> wrote:
deleted
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.
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- Hide quoted text -
- Show quoted text -
===============================================
How do _you_ select "the very first one you check" ?
I use 2q + N. j=1.
Terrific.
How do you select the first q without using
the factors of N ?
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- Hide quoted text -
- Show quoted text -
[/quote]
==========================================================> > How do you select the first q without using
[quote]the factors of N ?
That's trivial. Just pick a quadratic residue.
[/quote]
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.
[quote]
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?
[/quote]
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.
[quote]
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.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| JSH... |
| Posted: Sun Nov 08, 2009 8:12 am |
|
|
|
Guest
|
On Nov 8, 9:08 am, Enrico <ungerne... at (no spam) aol.com> wrote:
[quote]On Nov 7, 10:55 pm, JSH <jst... at (no spam) gmail.com> wrote:
On Nov 7, 9:11 pm, Enrico <ungerne... at (no spam) aol.com> wrote:
On Nov 7, 9:19 pm, JSH <jst... at (no spam) gmail.com> wrote:
deleted
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.
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- Hide quoted text -
- Show quoted text -
===============================================
How do _you_ select "the very first one you check" ?
I use 2q + N. j=1.
Terrific.
How do you select the first q without using
the factors of N ?
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- Hide quoted text -
- Show quoted text -
==========================================================
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.
[/quote]
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.
[quote]Didn't work, but was worth a try.
Enrico
[/quote]
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 |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sat Nov 28, 2009 7:16 am
|
|