HW Help: prove an element is primitive.

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

HW Help: prove an element is primitive.

Postby the tree » Thu Nov 11, 2010 5:51 pm UTC

If I'm told that that [imath]g[/imath] is a primitive element of [imath]\mathbf{Z}_p[/imath] where [imath]p[/imath] is 1. a prime, 2. pretty big - what can I do to show that [imath]g[/imath] really is a primitive element? Short of a fuck off spreadsheet (the numbers quickly get too big for excel to handle), is there a relevant theorem I should be looking up that will verify this? All the reading that I've done only seems to tell me that there's no way to find a primitive element, beyond trial and error, and I can't find a method for checking that an element is primitive beyond brute force.

User avatar
OverBored
Posts: 284
Joined: Mon Dec 10, 2007 7:39 pm UTC

Re: HW Help: prove an element is primitive.

Postby OverBored » Thu Nov 11, 2010 6:17 pm UTC

Can I just check, that by [imath]\mathbf{Z}_p[/imath] you mean integers modulo p correct?
G4!!

Grob FTW,

Hello. Smithers. You're. Quite good. At. Turning. Me. On.

User avatar
the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

Re: HW Help: prove an element is primitive.

Postby the tree » Thu Nov 11, 2010 6:27 pm UTC

Yes. \mathbb didn't seem to be working so I went for the next best thing.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: HW Help: prove an element is primitive.

Postby jaap » Thu Nov 11, 2010 6:42 pm UTC

If g were not primitive, what could its order be?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: HW Help: prove an element is primitive.

Postby mike-l » Thu Nov 11, 2010 6:47 pm UTC

There's a small-ish list of powers you actually need to check... do you know which ones they are?

You can keep your numbers small in excel by successively squaring and reducing mod p, then multiplying the appropriate [imath]g^{2^i}[/imath] values (eg [imath]g^{1000} = g^{512}g^{256}g^{128}g^{64}g^{32}g^8[/imath]
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

Re: HW Help: prove an element is primitive.

Postby the tree » Thu Nov 11, 2010 7:00 pm UTC

jaap wrote:If g were not primitive, what could its order be?
Anything up to p-1?
mike-l wrote:There's a small-ish list of powers you actually need to check... do you know which ones they are?
No, that was the kind of hint that I was looking for.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: HW Help: prove an element is primitive.

Postby skeptical scientist » Thu Nov 11, 2010 7:11 pm UTC

the tree wrote:
jaap wrote:If g were not primitive, what could its order be?
Anything up to p-1?

What do you know about the order of an element and the order of a group?
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

User avatar
the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

Re: HW Help: prove an element is primitive.

Postby the tree » Thu Nov 11, 2010 7:23 pm UTC

Okay I feel the answer is trying to bite me on the nose but I'm not just seeing it. Beyond what those terms mean, not much. g is primitive if it has order p-1, because then it has the same amount of distinct powers as there are elements in the group - so if it's not primitive then it has order less than p-1?

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: HW Help: prove an element is primitive.

Postby mike-l » Thu Nov 11, 2010 7:28 pm UTC

Yes, that's true. But can they be ANY order, or only particular ones? Maybe try a few examples... check the order of all the elements in [imath]\mathbf Z_{11}[/imath]. Do you notice anything?
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

Re: HW Help: prove an element is primitive.

Postby the tree » Thu Nov 11, 2010 7:51 pm UTC

2,6 or 10 apparently. 10 being the primitive elements. I'm afraid I still can't see where the 2 and 6 come from. (I'm tempted to say things like 2*6=1 mod 11 but that feels like shooting in the dark).

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: HW Help: prove an element is primitive.

Postby jaap » Thu Nov 11, 2010 8:06 pm UTC

the tree wrote:2,6 or 10 apparently. 10 being the primitive elements. I'm afraid I still can't see where the 2 and 6 come from. (I'm tempted to say things like 2*6=1 mod 11 but that feels like shooting in the dark).

Are you sure about the 6?

User avatar
the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

Re: HW Help: prove an element is primitive.

Postby the tree » Thu Nov 11, 2010 8:09 pm UTC

Make that five. Apparently all this mathsing it ruining my ability to count.

So okay, a penny has dropped, but possibly in the entirely wrong place - is it something to do with the elements can only have orders that are divisors of p-1? If so, does that urm... have a name I can look up or something?

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: HW Help: prove an element is primitive.

Postby jaap » Thu Nov 11, 2010 8:17 pm UTC

the tree wrote:Make that five. Apparently all this mathsing it ruining my ability to count.

So okay, a penny has dropped, but possibly in the entirely wrong place - is it something to do with the elements can only have orders that are divisors of p-1? If so, does that urm... have a name I can look up or something?

Lagrange's Theorem: If you have a subgroup of a group, then the order of a subgroup of divides the order of the group.
Here you have a group of order p-1 (the non-zero elements of Zp form a group under multiplication). Any element g generates a cyclic group of order o(g), which therefore must divide p-1.

User avatar
the tree
Posts: 801
Joined: Mon Apr 02, 2007 6:23 pm UTC
Location: Behind you

Re: HW Help: prove an element is primitive.

Postby the tree » Thu Nov 11, 2010 8:20 pm UTC

THANKYOU
:D :D :D :D :D :D

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: HW Help: prove an element is primitive.

Postby Yakk » Fri Nov 12, 2010 7:58 pm UTC

How to do it on paper.

Factor (p-1) into primes and powers of primes.

Build a table of g^1, g^2 mod p, (g^2)^2 mod p, ((g^2)^2)^2 mod p, etc, until (...(((2)^2)^2)...)^2 is greater than (p-1). (this takes log_2 steps).



Examine all of the factors of (p-1). Take the product of the above powers-of-g that "adds up" to that particular factor of (p-1). Is it 1?

...

Now can we do better than the above? Well, the factors of (p-1) have structure, so we could try using that structure to do less multiplication (ie, if p-1 is 20, we can do 2, 4 and 5, and then take 4*5 to get 10). I don't think this is significant, but it might be in pathological cases?

How big can the number of factors of p-1 get? Hmm. I'd intuitively guess "logarithmic", but I cannot think of a proof off of the top of my head. Anyone?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: HW Help: prove an element is primitive.

Postby mike-l » Fri Nov 12, 2010 8:36 pm UTC

You can also restrict yourself to checking (p-1)/q where q is a prime dividing (p-1), since any order must divide one of those. The number of primes dividing p-1 is certainly logarithmic at most... I don't feel like chugging through the PNT to figure out how much better it is than logarithmic.

Also, Yakk, your signature rocks.
Last edited by mike-l on Fri Nov 12, 2010 8:47 pm UTC, edited 2 times in total.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: HW Help: prove an element is primitive.

Postby Yakk » Fri Nov 12, 2010 8:44 pm UTC

Ah, good point. D'oh. :)

And the number of primes q such that q | n is ... roughly the inverse of product of the first n primes.
2*3*5*7*11*13*17*19*...
and that is going to grow somewhat faster than n!, let alone e^n.

Regardless, by this point the expensive part is going to be factoring p-1.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests