
Topic review (newest first)
 bob bundy
 20130711 22:21:01
hi napalmgrenade
Welcome to the forum.
This topic is not my area of expertise (if indeed I have one at all ) but I can get you started I think.
The underlying mathematics for this is group theory. There's a bit on this page
http://en.wikipedia.org/wiki/Generating_set_of_a_group
If the operation of a group is multiplication, then 1 is the identity element because
x.1 = x for all x in the group.
A member of the group is called a generator if you can make all the other elements of the group from it.
Let's say the group is G = {1,2,3,4,5,6} and the operation is multiplication, mod 7
3 is a generator because
3^1 = 3 = 3mod7 3^2 = 9 = 2mod7; 3^3 =27 = 6mod7; 3^4 = 81 = 4mod7; 3^5 = 243 = 5mod7; 3^6 = 729 = 1mod7
Once you get to the identity like this, higher powers of 3 will just generate the same elements again (eg 3^7 = 3mod7)
Note: You can save some effort by using the previous answer to get the next, taking advantage of the mod
eg 3^3 = 3^2 x 3 = 2 x3mod 7 = 6mod7
On the other hand, 2 isn't a generator because
2^1 = 2; 2^2 = 4; 2^3 = 8 = 1mod7
I've reached the identity before generating all the group elements. Higher powers will just keep producing 2,4 and 1 over and over.
Bob
 napalmgrenade
 20130711 10:43:09
Hi guys, I'm taking a course about cryptography, and Im currently confused on a topic I learned about. Basically my task is to find 5 generators by testing g=2,3,4,5,6,7. I dont quite understand what generators are but what I understand ( or think I understand) is that if I take p, which is the number of the modulus and observe p1's factors, I then raise g to those powers and mod by p and see if I get one as an answer. If I get one, then I know the number is not a generator. Please help me understand this topic the specific question is test g=2,3,4,5,6,7... for being generators mod 103 until you can find one of them. Since 102's factors are 2,3,17,51 and 6, I first tried testing 2 out. I did 2^2,2^3,2^17,2^51 and 2^6 and modded them all by 103 and didnt get a single 1. Does this mean that 2 is a generator? (I already know it is, but I want to know why). Thanks for any help, its appreciated, thanks.
EDIT: http://crypto.stanford.edu/pbc/notes/numbertheory/gen.xhtml this link may help explain
