Re: JSH: Understanding quadratic residues result

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
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.
.

Relevant Pages

  • Re: hiers to the blood - baroque speculation - careful possible roleplaying spoiler
    ... something not exactly what the original post was about). ... James' second point was: when you want to keep talking ... vampires was actually very useful to your original question, ...
    (rec.games.trading-cards.jyhad)
  • Re: When on a cruise: Castaway Cay (long)
    ... John Sisker, SHITO-SHORE CRUISE AGENCY ... Instead you turn it around to something else to stay away from the truth of the original post. ... Psst James since Seacruise is the keeper of the Charter, you have no idea of what you are talking about. ...
    (rec.travel.cruises)
  • Re: Mens Hour Books
    ... Women wear semi ... The supporting material was in the original post. ... http://www.jim.com/ James A. Donald ...
    (rec.arts.sf.composition)
  • Re: Replying to OLD messages
    ... > James B. Davis wrote: ... > Pay attention to the dates of the messages you're answering. ... keep the information to themself simply because the original post is old? ...
    (rec.motorcycles.tech)
  • Re: Replying to OLD messages
    ... >> James B. Davis wrote: ... >> Pay attention to the dates of the messages you're answering. ... > keep the information to themself simply because the original post is old? ...
    (rec.motorcycles.tech)