JSH: Understanding quadratic residues result
JSH
connection between the solution for a quadratic residue, and a
factorization, where it is unbelievable how simple the mathematics is,
so explaining it is trivial.
Given a quadratic residue q, modulo N, where N is odd, I've found that
given
k^2 = q mod N
you can solve for k, with
k = a*(1 + 2a^2)^{-1}*(f_1 + f_2) mod N
where T = f_1*f_2 = (1 + a^2)*q + jN,
where j is a nonzero integer, where 'a' is a Natural number. And
selecting 'a' can be critical to getting an answer quickly.
The equations come from z^2 = y^2 + T, x^2 = y^2 mod p, z = x + ak mod
p, k = 2ax mod p, where p is a prime factor of N.
What makes this approach of interest is simply that k^2 is given in
one equation and k is given in another, where solutions exist for any
choice of 'a'--I remind 'a' is a Natural number--but the SIZE of
f_1*f_2 needed to find the solutions is what varies depending on what
'a' is chosen.
My reason for taking this approach path originally was an attempt at
factoring T by using another number, for which p is the factor, but
it's easier to factor T, and use the luck of k^2 and k being given to
you, in order to solve for k through that factorization.
Notice that with z^2 = y^2 + T, and x^2 = y^2 mod p, there are an
infinity of solutions for x, for a non-trivial factorization which
gives you one z and y.
The remaining two congruences, z = x + ak mod p and k = 2ax mod p,
narrow that infinity down, and in so doing, allow you to define 'a'
and k in such a way as to get k, given a quadratic residue modulo N,
by factoring T.
The jump to N from p is rather straightforward, though that is
remarkable as well that is is possible to make that jump.
The math is easy. Solutions exist for any 'a' if q is a quadratic
residue, but finding them can be harder or easier dependent on 'a', as
T may be relatively large for one 'a', while much smaller for another.
Weirdly enough there are 4 ruling congruences which I also call
constraints which decide when T will work:
1. f_1 = ak mod p
2. f_2 = a^{-1}*(1 + a^2)*k mod p
3. z = (2a)^{-1}*(1 + 2a^2)*k mod p
and
4. y = (2a)^{-1}*k mod p
If all of the above can be true without contradiction--for EACH prime
factor p of N--then that T will work and give you k, where I remind
k^2 = q mod N. An example of a contradiction is any two of the
relations have k as a factor when T does not. That can often be about
size, as if p is relatively large, so that f_1 = ak explicitly, and
for some reason k is still a factor of any of the others despite the
congruence relationship, then T must have k as a factor. A small T
might not meet those conditions while there is some larger one that
will.
Those 4 constraints are wild though because the mathematics is saying,
hey, if you can fulfill these conditions, then ok, you get the right
answer, if not, no.
So I came across this technique kind of by accident where there is
just this oddity that the mathematics will solve for k^2 and k, so you
can set k^2 = q mod N, and then go find k from factoring.
It can be wicked fast.
For example did a toy test bigger than I usually try, I picked p=91,
and q=30, as 11^2 = 30 mod 91. With a=1, I have T = 60 mod 91.
My first try is with T=151, which is prime, and that didn't work
(though trivial factorizations MAY work). If the first non-trivial
factorization doesn't work then none will so I know not to try any
others. Ok, next is:
T = 242, = 11(22), which works! k = 3^{-1}(11 + 22) mod 91 = 11 mod
91.
Here with ak less than p the math found an answer that fit the bill,
though it can also use 91 - 11 that would be with a bigger T.
So these relationships are fundamental relationships of factoring and
quadratic residues. They were always there.
It is so wild.
The answers are there it's just that where they show up depends on 'a'
and the actual answer for k. It's kind of strange but you can watch
the mathematics shifting things around to handle each issue presented
by the 4 constraints when it gives the answer.
But yeah, it's mathematics, so it has infinite intelligence, so it's
not like it actually DOES anything as these answers are logically
built into numbers already.
Wild. Just wild.
James Harris
MichaelW
<snipping due to length, you can read the previous post>
Summary: The algorithm provided by James requires the provision of values
that can only be known if you know the answer. In fact this happens twice
during the algorithm.
And here is how it works...
Say there is a k such that k^2 = q mod p. Therefore we can express k^2 as
p*m+q where m is some integer or zero. Remember the value for m!
Now T is taken as (1+a^2)*q + j * p.
For any given value of a select j=m*(1+a^2). This means that we have
T = (1+a^2)*(q+m*p)
However we know that q+m*p = k^2 so
T = (1+a^2)*k^2.
All that is needed now is to take f_1 = a*k (note that we are plugging
the answer into the algorithm!) and f_2 = k*(1+a^2)/a. We therefore have
f_1+f_2 = a*k + k*(1+a^2)/2 = k*(1+2*a^2)/a
Therefore we have
k= a * (1+2*a^2)^-1 * k * 1+(2*a^2)/a mod p = k mod p.
So let's work through James' example. We have p=91 and q=30 and k=11. We
decide that a=1. Now 11^2=91*1+30 so m=1. This gives us j=1*(1+1^2)=2 so
we use j=2. Note that we needed to know k to figure out m so that in turn
we can select a working j.
<quote>
My first try is with T=151, which is prime, and that didn't work
(though trivial factorizations MAY work). If the first non-trivial
factorization doesn't work then none will so I know not to try any
others. Ok, next is T = 242
</quote>
Here James has tried j=1 which fails and so moves to j=2 (T=2*121). We
know this will work. Sure enough we take f_1=1*k=11. Note that in James'
post he does not select f_1=1 or f_1=2 but goes straight to the correct
f_1. Presumably he has tested the other possibilities already. Anyway
plugging it all in remarkably enough gives k=11.
Note that you have to give the answer you are looking for twice. First
time is when selecting j; you have to know what I have called m which in
turn means you have to know k. Then when selecting f_1 you have to
provide a*k, requiring you to know k. If you don't know k then you have
to guess a number of times equal to k, which of course is no better than
trial and error.
Final point: the term for f_2 above is not always integer. Strictly
speaking this does not matter (the terms all cancel out) but since we are
operating in modular arithmetic then we should be using integers
throughout. In this case the true value for j is as given plus k (I
think).
Noob
> Those 4 constraints are wild though because the mathematics is saying,
> hey, if you can fulfill these conditions, then ok, you get the right
> answer, if not, no.
It's good to hear from the mathematics, I was worried something might
have happened to them.
JSH
> On Tue, 17 Nov 2009 17:26:13 -0800, JSH wrote:
>
> <snipping due to length, you can read the previous post>
>
> Summary: The algorithm provided by James requires the provision of values
> that can only be known if you know the answer. In fact this happens twice
> during the algorithm.
That is an interesting assertion. I'm not sure it matters even if
true.
Why do you think that's important?
> And here is how it works...
>
> Say there is a k such that k^2 = q mod p. Therefore we can express k^2 as
> p*m+q where m is some integer or zero. Remember the value for m!
>
> Now T is taken as (1+a^2)*q + j * p.
>
> For any given value of a select j=m*(1+a^2). This means that we have
>
> T = (1+a^2)*(q+m*p)
>
> However we know that q+m*p = k^2 so
>
> T = (1+a^2)*k^2.
>
> All that is needed now is to take f_1 = a*k (note that we are plugging
> the answer into the algorithm!) and f_2 = k*(1+a^2)/a. We therefore have
Yeah, you're working backwards. I do it all the time.
It's a useful way to test things.
>
> f_1+f_2 = a*k + k*(1+a^2)/2 = k*(1+2*a^2)/a
>
> Therefore we have
>
> k= a * (1+2*a^2)^-1 * k * 1+(2*a^2)/a mod p = k mod p.
>
> So let's work through James' example. We have p=91 and q=30 and k=11. We
> decide that a=1. Now 11^2=91*1+30 so m=1. This gives us j=1*(1+1^2)=2 so
There's a faster way. Turns out that 11 is less than 91, as is 22.
And you have f_1 = ak mod p, and f_2 = a^{-1}*(1 + a^2)*k mod p, so
with p=91, and knowing k=11, you know that the first solution with
a=1, is with f_1 = 11 mod 91, and f_2 = 22 mod 91.
Easy as pie. Working backwards is a great way to get a quick answer.
> we use j=2. Note that we needed to know k to figure out m so that in turn
> we can select a working j.
That's a leap. If you're working backwards then yeah, you need the
answer first! Duh.
But going forwards with k unknown, it's a different story.
> <quote>
> My first try is with T=151, which is prime, and that didn't work
> (though trivial factorizations MAY work). If the first non-trivial
> factorization doesn't work then none will so I know not to try any
> others. Ok, next is T = 242
> </quote>
>
> Here James has tried j=1 which fails and so moves to j=2 (T=2*121). We
> know this will work. Sure enough we take f_1=1*k=11. Note that in James'
> post he does not select f_1=1 or f_1=2 but goes straight to the correct
> f_1. Presumably he has tested the other possibilities already. Anyway
Nope. Since I knew that k=11, when I saw 11 was a factor of T, I knew
I was done.
> plugging it all in remarkably enough gives k=11.
Not remarkably.
Given a=1, if 3^{-1}*(f_1 + f_2) = k mod p, then f_1 or f_2 = k.
It's trivial to prove. But notice is only necessarily true with p, a
prime.
> Note that you have to give the answer you are looking for twice. First
> time is when selecting j; you have to know what I have called m which in
> turn means you have to know k. Then when selecting f_1 you have to
> provide a*k, requiring you to know k. If you don't know k then you have
> to guess a number of times equal to k, which of course is no better than
> trial and error.
Trial and error is actually easy in this case as with k^2 = 30 mod 91,
you can just notice that 30 + 91 = 121.
It's a toy example.
If your full assertion is that this approach is useless then just say
it. You know you wish to say it anyway, so quit wasting time and just
spit it out.
James Harris
Gordon Burditt
>>
>> Summary: The algorithm provided by James requires the provision of values
>> that can only be known if you know the answer. In fact this happens twice
>> during the algorithm.
>
>That is an interesting assertion. I'm not sure it matters even if
>true.
If you're trying to prove that you can do something FAST, like factor,
it's cheating to use knowledge of the factors to choose various magic
numbers to get the factors. It destroys your claim that it's FAST,
since you skipped over a lot of trial-and-error you'd have to do if
you didn't already know the answer.
In other situations, where you can prove that there is an answer
(e.g. let T be an odd composite integer: it's obvious that T has
two nontrivial factors) it may be OK to prove something about the
answer. Just don't assume you know the answer when the purpose
is to prove that there *is* an answer. Otherwise you end up with
a proof like:
To prove: ice cream has no bones.
Assume: ice cream plus one bone has one bone.
Therefore: ice cream has no bones, proof complete.
Incidentally, James, from some of the things you've said, you may
be able to construct a proof that your method will always come up
with an answer (except for 15), something you haven't done yet.
You said it will always work if you end up with a quadratic residue.
Can you prove it? Can you also prove that there always exists a
choice of magic numbers that makes you end up with a quadratic
residue?
This proof might also be able to put a bound on the number of
guesses for magic numbers you have to try before it works, which
might help with a speed proof. Although I'm still not convinced
it is faster than trial division.
MichaelW
I was wondering if anyone else was even reading this thread since the
original post is barely coherent and contradicts itself in places;
without the example he gave it was not entirely clear what his
algorithm actually does.
I had some experience several months ago where JSH claimed to be able
to factor using Pell equations. The reality is that all that had
happened is that he had so obscured the original equations with extra
terms and manipulations that when he put the answer into the equation
it was not at all obvious. Back then it took me a week to track it
down as I did not know what I was looking for. This time around it
took me about one and a half hours because I did know what I was
looking for.
I note in James' response that he has entirely missed both my point
and my sarcasm ("remarkably enough" was probably a bit dry). Again
from experience he may or may not get it over the next week or two. He
will claim victory some months from now in any case.
Regards, Michael W.
JSH
> >> <snipping due to length, you can read the previous post>
>
> >> Summary: The algorithm provided by James requires the provision of values
> >> that can only be known if you know the answer. In fact this happens twice
> >> during the algorithm.
>
> >That is an interesting assertion. I'm not sure it matters even if
> >true.
>
> If you're trying to prove that you can do something FAST, like factor,
> it's cheating to use knowledge of the factors to choose various magic
> numbers to get the factors. It destroys your claim that it's FAST,
> since you skipped over a lot of trial-and-error you'd have to do if
> you didn't already know the answer.
Oh yeah, sure, if that's what happened. I noted that with my toy
example I already knew k=11.
I tried the first T, which was prime, and no-go, so moved onto the
next, which was T = 11(22), so I knew I was done.
Hey, that one works fast but others do MUCH worse with a=1. For
instance if k=23, then you'd have a lot further to go to get to T = 23
(46), which must work. It exists, but it's FAR away with a=1. But
what about, say, a=25?
I don't know as I just tossed that out at random.
> In other situations, where you can prove that there is an answer
> (e.g. let T be an odd composite integer: it's obvious that T has
> two nontrivial factors) it may be OK to prove something about the
> answer. Just don't assume you know the answer when the purpose
> is to prove that there *is* an answer. Otherwise you end up with
> a proof like:
>
> To prove: ice cream has no bones.
> Assume: ice cream plus one bone has one bone.
> Therefore: ice cream has no bones, proof complete.
>
> Incidentally, James, from some of the things you've said, you may
> be able to construct a proof that your method will always come up
> with an answer (except for 15), something you haven't done yet.
> You said it will always work if you end up with a quadratic residue.
> Can you prove it? Can you also prove that there always exists a
> choice of magic numbers that makes you end up with a quadratic
> residue?
Well, yeah. Key equations are:
f_1 = ak mod p, f_2 = a^{-1}*(1 + a^2)*k mod p
where f_1*f_2 = T, and note that T = (1 + a^2)*q + jN = (1 + a^2)*q
mod N
where p is a prime factor of N; therefore, T = (1 + a^2)*q mod p.
Multiply the first two equations together and you get: ak(a^{-1}*(1 +
a^2)*k ) = (1 + a^2)*k^2 mod p.
So if q is a quadratic residue modulo p, then f_1 and f_2 exist, so T
exists.
TRIVIAL.
It's such easy algebra that an existence proof is not an effort.
So there is always a T that will factor to give you k. The issue then
is, how hard is it to find?
> This proof might also be able to put a bound on the number of
> guesses for magic numbers you have to try before it works, which
> might help with a speed proof. Although I'm still not convinced
> it is faster than trial division.
Oh wow, as if whether you're convinced or not moves mountains in
China.
The method is on sci.crypt and on my math blog. If it works it will
move the world all on its own.
Your belief is not necessary.
James Harris
Mark Murray
> Oh wow, as if whether you're convinced or not moves mountains in
> China.
Recently you've been threatening people who aren't convinced with
congressional hearings. From this, I conclude that getting people
to have some conviction in your work is rather important to you.
There is plenty of other evidence to back this up.
> The method is on sci.crypt and on my math blog. If it works it will
> move the world all on its own.
>
> Your belief is not necessary.
Like this.
M
Bruce Stephens
[...]
> The method is on sci.crypt and on my math blog. If it works it will
> move the world all on its own.
Normal people would want to try it themselves. In your position (where
on previous occasions you've complained that people have deliberately
misunderstood your methods) they'd be even more interested in doing it
themselves.
But you're not interested.
I think you don't believe it works. That seems likely, given that it
seems that none of your previous attempts seem to have worked. (They
haven't moved the world, after all.)
amzoti
> The method is on sci.crypt and on my math blog. If it works it will
> move the world all on its own.
>
> Your belief is not necessary.
>
> James Harris
Lets make the claim more exact.
It does not work and it will not move the world at all.
You delusional narcissist!
Tim Smith
<a05c375b-7ecd-4476...@o9g2000prg.googlegroups.com>,
JSH <jst...@gmail.com> wrote:
> > Summary: The algorithm provided by James requires the provision of values
> > that can only be known if you know the answer. In fact this happens twice
> > during the algorithm.
>
> That is an interesting assertion. I'm not sure it matters even if
> true.
>
> Why do you think that's important?
Given a problem and the answer, this algorithm:
1. State the answer.
Is faster than your algorithms:
1. Pretend you don't already have the answer.
2. Commit a bunch of mathematical masturbation.
3. Shoot out the answer as your mathematical cumshot
--
--Tim Smith
MichaelW
wrote:
We all need to clarify our thinking here. As a means to determining
quadratic residues then the algorithm does work since after all the
answer is plugged into the algorithm. As a means of factoring then it
"works" but it is not faster than trial division, so it becomes a
matter of defining what we mean by "the algorithm works".
The confusion stems from the original post on this thread which talks
about both factoring and quadratic residues (and yes, there is a
relationship) and does not spend any time on analyzing the speed of
the algorithm.
Regards, Michael W.
rossum
<reply_i...@mouse-potato.com> wrote:
>In article
><a05c375b-7ecd-4476...@o9g2000prg.googlegroups.com>,
> JSH <jst...@gmail.com> wrote:
>> > Summary: The algorithm provided by James requires the provision of values
>> > that can only be known if you know the answer. In fact this happens twice
>> > during the algorithm.
>>
>> That is an interesting assertion. I'm not sure it matters even if
>> true.
>>
>> Why do you think that's important?
>
>Given a problem and the answer, this algorithm:
>
> 1. State the answer.
>
>Is faster than your algorithms:
>
> 1. Pretend you don't already have the answer.
>
> 2. Commit a bunch of mathematical masturbation.
Would that be mathturbation?
rossum
JSH
wrote:
> JSH <jst...@gmail.com> writes:
>
> [...]
>
> > The method is on sci.crypt and on my math blog. If it works it will
> > move the world all on its own.
>
> Normal people would want to try it themselves. In your position (where
> on previous occasions you've complained that people have deliberately
> misunderstood your methods) they'd be even more interested in doing it
> themselves.
And I've given an example.
> But you're not interested.
Except I gave an example in the original post.
> I think you don't believe it works. That seems likely, given that it
> seems that none of your previous attempts seem to have worked. (They
> haven't moved the world, after all.)
Well, it's trivial that it *works* the issue is, how well?
Here's a simpler example to understand the concept where I've stripped
off a lot of the full machinery:
Consider you have q, a quadratic residue modulo p, and you say,
hmmm....why not let:
f_1 = k mod p, and f_2 = 2k mod p?
Then I can let T = f_1*f_2 = 2k^2 mod p, and yeah! I have a k^2, so
now I wonder, hey, can I find k by factoring T?
YES. If T = z^2 - y^2, then T = (z-y)(z+y) is a factorization, and z
= (f_1 + f_2)/2, so I have
z = 3k/2 mod p, so k = 3^{-1}*(f_1 + f_2) mod p, trivially.
But how do I connect T with q? Well if k^2 = q mod p, then T =2 k^2 =
2q mod p, so I can search for T's that factor by considering T = 2q +
pj, where j is some nonzero integer.
That's the WAY stripped down way to consider it which should at least
remove the notion that it may not work.
There MUST be f_1, such that f_1 = k mod p, and MUST be f_2, such that
f_2 = 2k mod p, and the rest follows trivially.
So, yes. ABSOLUTELY. Without any shadow of a doubt, the method WILL
find a quadratic residues.
The full method includes the stripped down example above plus an
infinity more with the variable 'a'.
The issue is, when? How many T's do you need to try on average until
you get the answer?
James Harris
MichaelW
>
> The issue is, when? How many T's do you need to try on average until
> you get the answer?
>
> James Harris
Summary: The answer is exactly the same number of tries when directly
checking except without the intermediate calculations.
Analysis: If a=1 then T = 2*q + j*p. To rephrase your question how
many j's do you need to try on average (starting at j=1 and
incrementing) until you get the answer?
Consider k^2=q mod p. This can also be expressed as k^2 = q + p * m
where m is an integer, possibly zero.
The correct value of j (when a=1) is 2 * m as I posted earlier. The
first observation here is that you should only try even values for j.
Now if k^2=q mod p then (k+p)^2 = q mod p so the range of possible
values of k is {0,1,2...p-1} assuming we are looking for the smallest
k. Taking k=p-1 we have a maximum value of m equal to p-2.
Therefore we try values of j equal to {0,2,4,6,...,2p-4}. So there are
p-1 values to check and a crude analysis would suggest that we
therefore have to try (p-1)/2 values on average. However since we are
talking about squares there are more answers clustered around lower
values of j than higher values.
What exactly are we doing, however? The answer is that we check all
values of T=2k^2 for k={0,1,2,3...} such that plugging this T into a
complex formula gives us k such that k^2=q mod p. Doing the same for
simply checking values of k^2 mod p for k={0,1,2,...} will take
exactly the same time and require less intermediate calculation.
Regards, Michael W.
JSH
> On Nov 20, 11:38 am, JSH <jst...@gmail.com> wrote:
>
>
>
> > The issue is, when? How many T's do you need to try on average until
> > you get the answer?
>
> > James Harris
>
> Summary: The answer is exactly the same number of tries when directly
> checking except without the intermediate calculations.
>
> Analysis: If a=1 then T = 2*q + j*p. To rephrase your question how
> many j's do you need to try on average (starting at j=1 and
> incrementing) until you get the answer?
>
> Consider k^2=q mod p. This can also be expressed as k^2 = q + p * m
> where m is an integer, possibly zero.
>
> The correct value of j (when a=1) is 2 * m as I posted earlier. The
> first observation here is that you should only try even values for j.
Let N = 35, and q=29. Then with a=1, T = 2(29) mod 35, which is T = 23
mod 35.
You can use even T, but here I'll use the first odd, which is T = 93,
and it does work with f_1 = 93, and f_2 = 1, as I get:
k = 3^{-1}(93 + 1) mod 35 = 12(94) mod 35 = 1128 mod 35 = 8 mod 35.
And k = 8 mod 35 is a correct answer.
It will work with the even solution as well, but my point is the odd
one works just fine.
So you are wrong.
James Harris
MichaelW
>
> - Show quoted text -
8^2=64
64 mod 35 = 29
64 = 35 + 1 * 29
m = 1
j = 2 * m = 2
T = N + q * j = 35 + 29 * 2 = 93 as given by you
My point is that j is even, not T. In fact with odd N the value for T
will obviously be odd. Please read carefully before responding.
Regards, Michael W.
JSH
Let's try q=9, p=19. Obviously then, k = 3. But let's play through:
T = 18 mod 19
T = 37, does not work. T = 75, does work. With f_1 = 3, f_2=25:
k = 3^{-1}(3 + 25) mod 19 = 13(28) mod 19 = 3 mod 19.
T = 18 + 29*3 = 75
>
> Regards, Michael W.
You're still wrong.
James Harris
MichaelW
Okay, I need to be more precise. The correct values of j are 2*m as
well as larger values derived by adding multiples of k. In this case
m=0 so j=0 along with j=3, j=6, j=9 etc. You have selected j=3 which
of course works. My assumption was that we were looking for the
smallest working value of j. I note that in your original post you
actually specified that j is nonzero so strictly speaking yes, the
first value for j is odd as given. I would suggest that j=0 (that is,
T=18) works just as well:
k = 3^-1 * (3+6) mod 19 = 13*9 mod 19 = 117 mod 19 = 3
So then to be precise:
<precise statement>
On the basis of the orginal post if a =1 then the values of j that
will work are
j = p * m + k * n
where m = (k^2 - q)/p and n is any integer; the smallest j occurs when
n=0. When selecting f_1 use f_1 = k or f_2 = k (the algorithm is
symmetric at this point).
</precise statement>
Now that I have accepted your correction will you also run through my
first post on this thread and actually check the algebra? My point
that you have to know k to derive k still stands; nothing you have
provided so far changes that.
Regards, Michael W.
JSH
You already were precise--precisely wrong.
> well as larger values derived by adding multiples of k. In this case
> m=0 so j=0 along with j=3, j=6, j=9 etc. You have selected j=3 which
> of course works. My assumption was that we were looking for the
> smallest working value of j. I note that in your original post you
> actually specified that j is nonzero so strictly speaking yes, the
> first value for j is odd as given. I would suggest that j=0 (that is,
> T=18) works just as well:
>
> k = 3^-1 * (3+6) mod 19 = 13*9 mod 19 = 117 mod 19 = 3
>
> So then to be precise:
>
> <precise statement>
> On the basis of the orginal post if a =1 then the values of j that
> will work are
>
> j = p * m + k * n
>
> where m = (k^2 - q)/p and n is any integer; the smallest j occurs when
> n=0. When selecting f_1 use f_1 = k or f_2 = k (the algorithm is
> symmetric at this point).
> </precise statement>
>
> Now that I have accepted your correction will you also run through my
> first post on this thread and actually check the algebra? My point
> that you have to know k to derive k still stands; nothing you have
> provided so far changes that.
With N=161 = 7(23), q=71, try a=2.
Then T = 5q + jN = 5(71) mod 161 = 33 mod 161.
Then first T is, T = 194 = 2(97), and here
k = a*(1 + 2a^2)^{-1}*(f_1 + f_2) mod N = 2(9)^{-1)(f_1 + f_2) mod
161, so
k = 2(18)(f_1 + f_2) mod 161 = 36(f_1 + f_2) mod 161.
Trying the trivial factorization first 36(1 + 194) = 97 mod 161, and
97^2 = 71 mod 161.
MichaelW
Before I start are any other JSHites following any of this or has this
become a private conversation?
Here we go....
p=161 (or N=161, please make up your mind)
q=71
k=97
m=58
j=m*(1+a^2). If a=2 then j=290
We know from my previous post that any j=290+n*97 will work including
negative n. Let us take n=-3.
j=290-3*97=-1.
T=5*71-1*161=194
The rest follows as you provided. Still right, you just keep changing
the goalposts as we say in Oz.
Just to confirm, let's have a=3. Therefore the j-generator is
j=580 + n*97
Using n=-5, j=95, T=16005, f_1=3*k=291, f_2=55
k=3*19^-1*(291+55) mod 161 = 3 * 17 * 346 mod 161 = 97 as required.
Give me any combination of starting values you like and I can provide
all working j values. If you are looking for a way out then I suggest
you pick some values that are not co-prime. I suspect that this will
allow extra values of j for fractional n.
Regards, Michael W.
Enrico
>
> - Show quoted text -
=====================================================
>
> Before I start are any other JSHites following any of this or has this
> become a private conversation?
>
Hi ! - Glad to see things getting away from that N = 35 bit.
Also a, getting up to 3 at last.
Can't follow along easily, though - my spreadsheet is a kludge and
designed around a=1 only. Can't use a cell formula for inverse mod
with a > 1 either - have to add a routine. And other stuff.
Enrico
MichaelW
A spreadsheet is definitely the way to go. Of course following the
explanation is... tricky. I found the best way is to have the same value
for a and then set a range of j values. Then manually change a to get
different effects. I can post some formulae if you like.
Regarding the inverse mod I cheat. I use this site:
http://2000clicks.com/mathhelp/
NumberChineseExtendedEuclideanAlgorithm.aspx
and plug the answer into the spreadsheet. Note that for some values there
are not enough rows on the page.
Finally it is clear that my first post on this thread is not very good. I
spend too much time on proof which obscures the basic formula.
Regards, Michael W.
Mark Murray
> Before I start are any other JSHites following any of this or has this
> become a private conversation?
I'm following.
M
Enrico
=========================================================
MIne is similar, but has 2 columns with x=0,1,2, ... and x mod N
I use those to generate 2q + jN and have f1 selectable with a
spinner (up / down increment control). subsequent columns implement
James' formulas. Its probably more complicated than it needs to be,
but
it grew by accretion as time went by and I thought of more things I
wanted to see.
I've got the extended Euclidean Algorithm working on a different
spreadsheet - getting a variable length routine to return a value
from a column position not known in advance, and without using
any code was a challenge. Maybe I'll use code this time.
Go ahead and post your formulas - that'll give me something to check
mine against. Something about what I'm doing doesn't look quite right
- I
I can come up with James' numbers, but not without a lot of work.
I wonder about JSH's 4 constraint equations, which are all mod p.
p is defined as a divisor of N (N=161 = 7*23 in the current case)
If the factors of N are known, you can calculate x^2 mod N = 71 from
simultaneous congruence equations mod 7 and 23.
Enrico
Mark Murray
> Before I start are any other JSHites following any of this or has this
> become a private conversation?
Looks like JSH is going to bail out shortly.
Intelligence (Twitter) suggests he is going to move over to his (broken) copy-protection scheme.
M
Mark Murray
HisMathGroup (http://groups.google.com/group/mymathgroup) promises us
Pythagorean Triples with Pell's Equation. Bets, anyone?
M
MichaelW
>
> MIne is similar, but has 2 columns with x=0,1,2, ... and x mod N I use
> those to generate 2q + jN and have f1 selectable with a spinner (up /
> down increment control). subsequent columns implement James' formulas.
> Its probably more complicated than it needs to be, but
> it grew by accretion as time went by and I thought of more things I
> wanted to see.
>
> I've got the extended Euclidean Algorithm working on a different
> spreadsheet - getting a variable length routine to return a value from a
> column position not known in advance, and without using any code was a
> challenge. Maybe I'll use code this time.
>
> Go ahead and post your formulas - that'll give me something to check
> mine against. Something about what I'm doing doesn't look quite right -
> I
> I can come up with James' numbers, but not without a lot of work.
>
> I wonder about JSH's 4 constraint equations, which are all mod p. p is
> defined as a divisor of N (N=161 = 7*23 in the current case) If the
> factors of N are known, you can calculate x^2 mod N = 71 from
> simultaneous congruence equations mod 7 and 23.
>
>
>
> Enrico
I only focused on the quadratic residue part; in the original post that's
what was in the example and all of James' answers to me have followed the
same approach. I can see there is a link to factoring but it is hard to
see exactly what is meant.
The constraint equations are actually saying the same thing that I am. If
I can summarise:
k^2 = q mod p (1) This leads to...
k^2 = p * m + q (2) where m is any integer
I have determined that the value for j must be of the form
j = (1+a^2) * m + k * n (3) where n is any integer and a is any positive
integer
Note that at this point we need to know k which also gives us m. Thus we
have
T = (1+a^2) * (k^2 + k * n * p) (4)
f_1 = a*k (5)
f_2 = T/a*k = (1+a^2) * (k + n * p) / a (6)
f_1+f_2 = ((2a^2+1)*k + (a^2+1)*n*p)/a (7)
This is multiplied by a/(2a^2+1) and taken at mod p. By inspection this
leaves k. Note that again to get f_1 you need to know k.
Now (5) is equivalent to constraint 1 and (6) is equivalent to constraint
2. What James does not realise is that working back from these
constraints forces (3).
Of course all of this is way too convoluted and slow compared to simply
counting off k=1,2,3... until you get k^2=q mod p.
This is not one of those James algorithms where interesting patterns
emerge. The behaviour once you expand the formulae is very boring and
predictable. The closest to being fun is picking a value for a that gives
the smallest possible j.
I have yet to determine the relationship between N and p, and what the
business of x, y and z is about (constraints 3 and 4). None of James'
examples appear to have anything to do with them.
Regards, Michael W.
MichaelW
You missed yesterday's wacky twitters; sorry I did not keep them.
Mark Murray
> You missed yesterday's wacky twitters; sorry I did not keep them.
I got them alright! He's come up with the usual lame excuse as to
why, which is even more amusing.
M
JSH
Ugh, using a spreadsheet. Yuck. But if it'll help I now believe
(just kind of was ruminating on it) that the probability of success
with a=1 should be roughly 1/k, when 2k<N.
The a=1 case may be the only one where it is possible to get a
probability like that where also notice that even then it assumes 2k <
N.
The problem of course are the congruences. They clip in random ways
depending on which 'a' value you have, where the effect is magnified
once 'a' is greater than 1 as a^{1]} factors kick in, so the modular
inverse becomes a factor.
Do you see the 1/k probability with your a=1 spreadsheet?
James Harris
Enrico
====================================================
I get 4/N complicated by the need to choose the right f1.
Enrico
JSH
That doesn't sound right.
If N is a prime p, then for instance, if 2k^2 is approximately equal
to p, then the algorithm will exit on the first iteration. Actually,
in general if 2k^2 is approximately equal to N, then the algorithm
will exit on the first iteration.
The value of k is what matters. Do you continue to disagree?
James Harris
Enrico
===================================================
>
> The value of k is what matters. Do you continue to disagree?
>
You asked me:
>> Do you see the 1/k probability with your a=1 spreadsheet?
I answered:
> > I get 4/N complicated by the need to choose the right f1.
This is not disagreement. I looked at my spreadsheet and
decribed what I saw. Remember, I start with k=0, 1, 2, 3, ...
and k^2 mod N in the first two columns on my spreadsheet.
additional columns apply your equations.
Its a brute force, show everything, tweak anything research tool.
Given q mod N, k matters. With N the product of 2 primes and
k, q coprime to N, I can find 4 values of k that work in every
interval of N. Thats where the 4/N comes from.
Enrico
MichaelW
>
> This is not disagreement. I looked at my spreadsheet and decribed what I
> saw. Remember, I start with k=0, 1, 2, 3, ... and k^2 mod N in the first
> two columns on my spreadsheet. additional columns apply your equations.
> Its a brute force, show everything, tweak anything research tool.
>
> Given q mod N, k matters. With N the product of 2 primes and k, q
> coprime to N, I can find 4 values of k that work in every interval of N.
> Thats where the 4/N comes from.
>
>
> Enrico
If N is the product of two odd primes then every k such that k^2=q mod N
will be matched by another k (call it l) such that l^2=q mod N. Proof
provided on request but basically (k-l) will be a multiple of one of the
primes and (k+l) a multiple of the other prime.
Given each k^2 = q mod N is also matched by (N-k)^2 = q mod N then we
have four solutions: k, l, N-k, N-l. This is why you are finding four
values.
Regards, Michael W.
MichaelW
Before someone else points it out; for low q we will have (k+l) as a
multiple of N and no factorisation.
Regards, Michael W.
JSH
...with an assertion that the probability was roughly 1/k, when you
gave something different.
Not a big deal. I just wanted to know if you were firm on your
position given the example I had.
> >> Do you see the 1/k probability with your a=1 spreadsheet?
>
> I answered:
>
> > > I get 4/N complicated by the need to choose the right f1.
>
> This is not disagreement. I looked at my spreadsheet and
> decribed what I saw. Remember, I start with k=0, 1, 2, 3, ...
> and k^2 mod N in the first two columns on my spreadsheet.
> additional columns apply your equations.
> Its a brute force, show everything, tweak anything research tool.
>
> Given q mod N, k matters. With N the product of 2 primes and
> k, q coprime to N, I can find 4 values of k that work in every
> interval of N. Thats where the 4/N comes from.
>
> Enrico
Yeah but the algorithm is moving mod N, as you have T = 2q mod N.
James Harris