mersenneforum.org > Math checking cyclic group belongingness of an element
 Register FAQ Search Today's Posts Mark Forums Read

 2007-11-27, 18:01 #1 vector     Nov 2007 home 52 Posts checking cyclic group belongingness of an element How do I check if some element was generated by some base. For example if the base is 2 and modulus is 7 the elements that are generated are {1,2,4} while elements that are not generated are {3,5,6,0}. Is there some test to check if some element like {4 or 5} was really generated by 2 or not? I tried googling this but did not find anything, probably because the phrasing of the question is incorrect.
2007-11-29, 16:56   #2
m_f_h

Feb 2007

24·33 Posts

Quote:
 Originally Posted by vector How do I check if some element was generated by some base. For example if the base is 2 and modulus is 7 the elements that are generated are {1,2,4} while elements that are not generated are {3,5,6,0}. Is there some test to check if some element like {4 or 5} was really generated by 2 or not? I tried googling this but did not find anything, probably because the phrasing of the question is incorrect.
"base" seems to refer to successive multiplication, i.e. the subgroup <2> generated by 2 in the multiplicative group U(Z/7Z) = Z/7Z \ {0} since 7 is prime.

There is the notion of the multiplicative order of an element,
ord(x,n) = # { x^i mod n ; i=0,1,... }
(well if we have an element of a finite group we know that we will get sooner or later the neutral element of the group)

I don't think there is an explicit formula not even for ord(x,n) ;
and I fear that it's not simple to find the answer to your problem in the general case.

In some cases you may know, e.g. if x is invertible in Z/nZ then you can only get invertible elements (relatively prime to n) and no divisors of zero (having a common divisor > 1 with n)

If n is prime, all nonzero elements are invertible and they will never give
0.

If (Z/nZ)* is monogenic (thus cyclic) then any of the generators gives any other element.

If the order of an element does not divide the order of the "base", it cannot be written as a power of that base.

etc.

PS: even, I think that the LL-test amounts just to know if some element can be written as a power of another one (once the procedure is rewritten in some "twisted" way), so if there were a simple general solution, you knew about primality without doing the p -1(?) squarings.

Last fiddled with by m_f_h on 2007-11-29 at 17:09

 2007-11-30, 07:42 #3 Kevin     Aug 2002 Ann Arbor, MI 6618 Posts Looking up stuff on Primitive Roots is probably as close as you'll get to a solution.
 2007-11-30, 11:02 #4 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts You want to know if there is a k so that b[I]k[/I] ≡ a (mod p), where b is your base, a is the element whose "belongingness" you want to check and p is the modulus. The order of a power is ord(b[I]k[/I]) = ord(b)/gcd(ord(b),k), so the order of the power will divide the order of b. Hence we obviously need ord(a)|ord(b) to have a solution. Since your group (Z/pZ)* is cyclic, let g be a generator and write a = g[I]n[/I], b = g[I]m[/I]. We want b[I]k[/I] = (g[I]m[/I])[I]k[/I] = g[I]mk[/I] = a = g[I]n[/I], hence mk ≡ n (mod p-1). This has a solution in k if gcd(m, p-1) | gcd(n, p-1), and since ord(b) = (p-1)/gcd(m, p-1) (likewise for a) we have (p-1)/ord(b) | (p-1)/ord(a) which is equivalent to ord(a)|ord(b). Hence ord(a)|ord(b) is a necessary and sufficient condition that there is a k so that b[I]k[/I] = a in a cyclic group. Alex Edit: to compute ord(a) and ord(b) in (Z/pZ)* efficiently you'll need the factorisation of p-1 of course. Last fiddled with by akruppa on 2007-11-30 at 11:04
 2007-11-30, 13:18 #5 vector     Nov 2007 home 52 Posts "Hence ord(a)|ord(b) is a necessary and sufficient condition that there is a k so that bk = a in a cyclic group." So, in other words, if the order of the element is greater than the order of the base then the element can't be generated by the base.
 2007-11-30, 13:25 #6 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Yes, that follows from my statement, but it is not equivalent. Alex
2007-11-30, 13:26   #7
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010010002 Posts

Quote:
 Originally Posted by vector "Hence ord(a)|ord(b) is a necessary and sufficient condition that there is a k so that bk = a in a cyclic group." So, in other words, if the order of the element is greater than the order of the base then the element can't be generated by the base.

Your statement is a corollary, but is not equivalent 'in other words'.

 2007-12-02, 02:40 #8 vector     Nov 2007 home 110012 Posts Yeah I realized this couple of minutes after posting. A correct simplification is that ord(b) must be divisible ord(a) without leaving a remainder. Anyway it turned out that this did not help me solve that problem I was working on. I was trying to find a way to transform base1^x mod p problem into a base2^x mod p problem, where base2 has a higher order than base1. This transform is easy if the order of the base1 and base2 are the same and base2 is unspecified. All you have to do is take a valid kth root of the base1 and the element. This way the exponent remains the same. However if you are trying to change the non-primitive base1 to any primitive base2 this transform can only be valid for exponents that are less than the order of base1. So far I can't figure out how to do this.
2007-12-02, 08:28   #9
akruppa

"Nancy"
Aug 2002
Alexandria

9A316 Posts

Quote:
 Originally Posted by vector Yeah I realized this couple of minutes after posting. A correct simplification is that ord(b) must be divisible ord(a) without leaving a remainder.
That's not a simplification, that's exactly what ord(a)|ord(b) means.

Quote:
 Originally Posted by vector Anyway it turned out that this did not help me solve that problem I was working on. I was trying to find a way to transform base1^x mod p problem into a base2^x mod p problem, where base2 has a higher order than base1. This transform is easy if the order of the base1 and base2 are the same and base2 is unspecified. All you have to do is take a valid kth root of the base1 and the element. This way the exponent remains the same. However if you are trying to change the non-primitive base1 to any primitive base2 this transform can only be valid for exponents that are less than the order of base1. So far I can't figure out how to do this.

Alex

 2007-12-02, 10:26 #10 vector     Nov 2007 home 52 Posts 3^4 mod 11=5; ord(3)=5; 3rd root inverting exponent= 3*exponent=1 mod 5, inverting exponent=2; so (3^2)^4 =5^2 mod 11; therefore 9^x = 3 mod 11; and 3^x = 5 mod 11; also ord(9)=5; So base 3 is changed to base 9, exponent is kept the same and the element is modified. However it does not seem possible transform a non-primitive base to any primitive base.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Abstract Algebra & Algebraic Number Theory 0 2018-01-30 06:10 davar55 Homework Help 67 2017-05-23 13:16 Forceman Software 2 2013-01-30 17:32 Flatlander Lounge 24 2009-08-21 16:53 tytus Math 3 2005-02-04 10:10

All times are UTC. The time now is 15:44.

Fri Dec 9 15:44:10 UTC 2022 up 113 days, 13:12, 0 users, load averages: 0.90, 1.06, 1.12