Maths

I've been digging around some, and have failed to see this information demonstrated, at least not in a way that I could identify, so...

I propose the following:

For all p, p being a safe prime (with a corresponding Sophie Germain prime s,) implies that for all y in [2, p-1], y^s mod p is either 1 or p-1.

Furthermore, a discrete logarithm only exists under the following circumstances:

• 0^k = z mod p is only true for z = 0, with k in {1, 2, 3, ...}
  
• 1^k = z mod p is only true for z = 1, with k in {1, 2, 3, ...}
  
• (p-1)^k = z mod p is only true for z in {1, p-1}.
  (p-1)^k = p-1 mod p for all odd k values, and
  (p-1)^k = 1 mod p for all even k values.
  
• Otherwise, let y be in [2, p-2]:
  
  
  • if y^s = p-1 mod p:
    for all z in [1, p-1], there is some k such that y^k = z mod p.
    Let the set of all such y values be represented as Y.
    
  • if y^s = 1 mod p:
    y^k = z mod p has a solution k if and only if p - z is in Y.
    
  
  

I have managed to show that this is true for all safe primes under one thousand, I just need to figure out how to prove it for all safe primes. Hopefully there will be more to come here.

For a follow up, here's an interesting chart showing this information for the safe prime 11. The columns represent the y values, the rows represent the z values, and the numbers in the cells (if present) represent the k values. The relevant Sophie-Germain prime powers are highlighted in green.

A			5				5	5	5		1
9			6	2	3	4	4	8	2	1
8			3				7	9	1
7			7				3	1	9
6			9				1	7	3
5			4	3	2	1	6	2	8	4
4			2	4	1	3	8	6	4	2
3			8	1	4	2	2	4	6	3
2			1				9	3	7
1		1	A	5	5	5	A	A	A	5	2
0	1
	0	1	2	3	4	5	6	7	8	9	A

---

2007/11/08: Here's a similar chart for the safe primes 5 and 7:

4			2	2	1
3			3	1
2			1	3
1		1	4	4	2
0	1
	0	1	2	3	4

6				3		3	1
5				5		1
4			2	4	1	2
3				1		5
2			1	2	2	4
1		1	3	6	3	6	2
0	1
	0	1	2	3	4	5	6

Compare these against a non safe-prime (not even prime) base 12:

B												1
A											1
9				2						1
8			3						1
7								1
6							1
5						1
4			2		1				2		2
3				1
2			1
1		1				2		2				2
0	1						2
	0	1	2	3	4	5	6	7	8	9	A	B

---

I've written a program to show these tables, available here