Re: JSH: Understanding quadratic residues result
- From: MichaelW <msjmb@xxxxxxxxxx>
- Date: 20 Nov 2009 19:34:07 +1100
On Thu, 19 Nov 2009 23:40:10 -0800, Enrico wrote:
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 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.
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
Note that at this point we need to know k which also gives us m. Thus we
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.
- Prev by Date: Re: JSH: Understanding quadratic residues result
- Next by Date: Re: JSH: Understanding quadratic residues result
- Previous by thread: Re: JSH: Understanding quadratic residues result
- Next by thread: Re: JSH: Understanding quadratic residues result