mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-11-27, 18:01   #1
vector
 
vector's Avatar
 
Nov 2007
home

318 Posts
Default 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.
vector is offline   Reply With Quote
Old 2007-11-29, 16:56   #2
m_f_h
 
m_f_h's Avatar
 
Feb 2007

24·33 Posts
Default

Quote:
Originally Posted by vector View Post
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
m_f_h is offline   Reply With Quote
Old 2007-11-30, 07:42   #3
Kevin
 
Kevin's Avatar
 
Aug 2002
Ann Arbor, MI

433 Posts
Default

Looking up stuff on Primitive Roots is probably as close as you'll get to a solution.
Kevin is offline   Reply With Quote
Old 2007-11-30, 11:02   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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 mkn (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
akruppa is offline   Reply With Quote
Old 2007-11-30, 13:18   #5
vector
 
vector's Avatar
 
Nov 2007
home

318 Posts
Default

"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.
vector is offline   Reply With Quote
Old 2007-11-30, 13:25   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

Yes, that follows from my statement, but it is not equivalent.

Alex
akruppa is offline   Reply With Quote
Old 2007-11-30, 13:26   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by vector View Post
"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'.
R.D. Silverman is offline   Reply With Quote
Old 2007-12-02, 02:40   #8
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default

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.
vector is offline   Reply With Quote
Old 2007-12-02, 08:28   #9
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by vector View Post
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 View Post
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
akruppa is offline   Reply With Quote
Old 2007-12-02, 10:26   #10
vector
 
vector's Avatar
 
Nov 2007
home

52 Posts
Default

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.
vector is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cyclic fields with class number h carpetpool Abstract Algebra & Algebraic Number Theory 0 2018-01-30 06:10
Cyclic Group Problem davar55 Homework Help 67 2017-05-23 13:16
Round Off Checking and Sum (Inputs) Error Checking Forceman Software 2 2013-01-30 17:32
Name That Element Flatlander Lounge 24 2009-08-21 16:53
Number of n-element permutations with exactly k inversions tytus Math 3 2005-02-04 10:10

All times are UTC. The time now is 22:31.


Wed May 18 22:31:16 UTC 2022 up 34 days, 20:32, 1 user, load averages: 2.03, 1.91, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔