Re: related to group theory

ok sorry... i am not mentioning the problem clearly................
now just try to understand my problem..........
I have mistakenly typed 0 in my previous post....

leave it alll.............

I would like to explain u my problem with an example..

consider Z_p * = { 1, 2, -----, p - 1 } where p is prime ,
mod p - multiplication modulo p
Z-p* is a cyclic group.

for p = 11, Z_11* = { 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10 }

2 is a generator of Z_11*
but 3 is not a generator surely.

consider, 3^1 mod 11 = 3
3^2 mod 11 = 9
3^3 mod 11 = 5
3^4 mod 11 = 4
3^5 mod 11 = 1

So < 3 > = { 3, 9 , 5, 4, 1 } is a cyclic subgroup of Z_11*
generated by 3

So 3 is an element of Z_11* of order 5 ( = 11 / 2 )

Now here what my problem is that I need an efficient algo. to
find an element 3 of Z_n* of order n / 2 .

I think now u can understand my problem clearly....
Sorry for inconvenience...............

Arturo Magidin wrote:
In article <1155985264.481714.128150@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
anil <anilkumar.iitm@xxxxxxxxx> wrote:
Suppose given a group Z_n with n numbers, order < n,

This is overly confusing. You mean: given THE group Z_n (cyclic of
order n, represented by the residue classes of integers modulo n,
under addition), and given an integer k<n (in fact, you need MORE, you
need k to DIVIDE n), how do you find a generator for the unique
subgroup of order k of Z_n?

How to find the generator for a given order?

If a cyclic group (written additively) has order n, and is generated
by x, then the order of the element mx (x added to itself m times) is
n/(gcd(m,n).

So if you know that k divides n, then just take kn.

for example: I have group Z_11 = { 0,1,2,3,4,5,6,7,8,9,10 } ,
order = 5, then generator = ?

There is no element of order 5 in Z_{11}; Z_{11} has no subgroup of
order 5. Z_{11} only has two subgroups: the trivial one and the total
one. You cannot find any element of orders other than 1 and 11.


If there is no order restriction,
we will simply found generator as 10 = 2 * 5

This is nonsense.


2^(10 / 2 ) mod 11 = 10 ( != 1 )
2^(10 / 5 ) mod 11 = 4 ( != 1 )
So 2 is a generator....

Whoa! You mean the MULTIPLICATIVE SUBGROUP of Z_{11}? Then what the
hell is 0 doing above?

First you need to find a primitive root; finding primitive roots
modulo p for arbitrary p is not easy, and there is no known algorithm
to do so.

Please suggest me what way I have to proceed.

First, learn to state what you want intelligibly.

Then, look up "primitive root modulo p."

--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================

Arturo Magidin
magidin-at-member-ams-org

.

Relevant Pages

  • Re: related to group theory
    ... order n, represented by the residue classes of integers modulo n, ... subgroup of order k of Z_n? ... First you need to find a primitive root; ... modulo p for arbitrary p is not easy, and there is no known algorithm ...
    (sci.math)
  • Re: Proving a subset of Z_j for some j in Z is a group
    ... say you want to do this for + modulo Z_j ... and so has only cyclic subgroups. ... check whether it denotes a subgroup of ... You need them to be relatively prime to j, ...
    (sci.math)
  • Re: Algebra with order a, b
    ... H /\ N is a subgroup of H and N. ... is congruent to 1 modulo 7 and divides 3*7. ... It means that this Sylow 7-subgroup is normal in G. ...
    (sci.math)
  • Re: constructing a specified hash function
    ... Denote G is a subgroup of Z*_p generated by g. ... and then reduce it modulo p.) ... Now, let's rise our requirement. ...
    (sci.crypt)
  • Re: Paper & pencil password algorithm
    ... multiplication modulo 10). ... I was also thinking about performing the whole computation modulo 11. ...
    (sci.crypt)