Making a Ring

Making a Ring

There was a time before I understood rings in public key methods, and the time after it. I basically allowed me to understand how public key encryption and discrete logs work. Basically, I take a prime number (p), and then use a (mod p) operation, and it creates a ring.

For a ring in encryption, we create can a g value and have a prime number of N. For values of x, we get g^ x (mod N). For example if we use g=2 and N=42:

1	2
2	4
3	8
4	16
5	32
6	22
7	2
8	4
...	
40	16
41	32
42	22
43	2
44	4

Notice that we repeat after 42, and start the sequence again with 2, 4, etc. This is the ring. Note that g must work for the ring. With C#, here is the algorithm for working out g, once we have a prime number:

public int getG(int p)
 {
 for (int i = 2; i < p; i++)
 {
 int rand = i;
 int exp = 1;
 int next = rand % p;
 
 while (next!=1)
 {
 next = (next * rand) % p;
 exp = exp + 1;
 }
 if (exp == p — 1)
 return (rand);
 
 }
 return (2);
 
 }

Can you try this one:

For a g value of 2 and a prime number of 53, what is the next value in the sequence of 2, 4, 8, 16, 32, 11, …

The answer is 22 (2⁷ mod 53).

Now try the following (it is the 4th question):

Why does this work? Well a (mod p) operation means that we always give a unique output (from 0 to p-1) for all the values of x for 0 to p-1. The (mod p) operation also works for all our arthimetic operations, such as:

(a x b) (mod p) = a (mod p) x (b mod p) (mod p)

If you are interested, here’s a speadsheet to determine the sequence [here]: