Re: Order question

From: Gregory G Rose (ggr_at_qualcomm.com)
Date: 04/30/04 

Date: 29 Apr 2004 15:15:38 -0700

In article <BCB7344B.4C93F%zenadsl6186@zen.co.uk>,
Peter Fairbrother <zenadsl6186@zen.co.uk> wrote:
>>> Take 11 = 2*5+1 as an example. 1,3,4,5,and 9 are quadratic residues, and
>>> 2,6,7,8 and 10 are non-residues. Both groups have five members.
>>
>> No, {2,6,7,8,10} is not a group, and hence not a
>> subgroup. It has no identity and is not closed.
>
>Thanks. That was the answer I wanted.
>
>Next question. Can you simply show that the subgroup of order q is the same
>group as the group of QR's? I've done this before, but I lost it.

Back to first principals. CAIN: Closure,
Associativity, Identity, iNverse.
Let X = x^2, Y=y^2.

Closure: X*Y = x*x*y*y = x*y*x*y = (x*y)^2

Associativity flows from the parent group.

Identity: 1*1=1, therefore 1 is a QR.

Inverse: if x*y=1, then x^2*y^2 = 1, so X*Y=1, so
every QR X has an inverse Y.

Conclusion: The QRs form a (sub)group.

Now note that x^2 and (-x)^2 both are X;
therefore there are half as many QRs as there are
x's. (I think this step requires the distributive
law, so it works on integers mod P (which form a
field), but not necessarily other groups.)

There is a unique subgroup of order (p-1)/2,
so it must be the QR's. QED.

(I'm very out of practice with this stuff, so I'm
not certain this is a valid proof, but...)

Greg. 

-- 
Greg Rose
232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C
Qualcomm Australia: http://www.qualcomm.com.au

Relevant Pages

  • Re: general question how to choose parameters
    ... but there are potential attacks ... These are often called "small subgroup ... was still large enough for security. ... Greg Rose ...
    (sci.crypt)
  • Re: generators be bound
    ... Standard algorithm, the terminology is "generator ... of the order-q subgroup". ... No, that's incorrect terminology too. ... Greg Rose ...
    (sci.crypt)