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 pis only true forz = 0, withk in {1, 2, 3, ...}
1^k = z mod pis only true forz = 1, withk in {1, 2, 3, ...}
(p-1)^k = z mod pis only true forz in {1, p-1}.
(p-1)^k = p-1 mod pfor all oddkvalues, and
(p-1)^k = 1 mod pfor all evenkvalues.
- Otherwise, let
ybe in[2, p-2]:- if
y^s = p-1 mod p:
for allz in [1, p-1], there is someksuch thaty^k = z mod p.
Let the set of all suchyvalues be represented asY.
- if
y^s = 1 mod p:
y^k = z mod phas a solutionkif and only ifp - z is in Y.
- if
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 |
| 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
17 comments:
I need to break this down a little bit:
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.
True. Fermat's Little Theorem states that for all a, a coprime to p, a^p = a (mod p). This means a^(p-1) = 1 (mod p). Of course, a^(p-1) = a^(2s) in this case. So a^s = 1 or -1 (mod p), and -1 = p-1 (mod p).
Furthermore, a discrete logarithm only exists under the following circumstances:
A small issue with your terminology here. As I recall, the discrete logaritm is defined in terms of a primitive root, which by definition means it is defined for all values [1, p-1]. But I get your point: there is a solution to x^k = z (mod p) only 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, ...}
These are trivially obvious.
(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.
Remembering that -1 = p-1 (mod p), these are also obvious.
Otherwise, let y be in [2, p-2]:
This part took me a while to decode:
if y^s = p-1 mod p:
Out of concern that you have missed the importance of this line, let's discuss it. Thanks to Lagrange's Theorem, the multiplicative order of any y coprime to p (which includes all the values in question here (i.e., [2, p-2])), must divide the totient of p. Since p is prime, the totient is p-1. That means that the order of any y must divide p-1 = 2s, and therefore the order of y is either 1, 2, s, or 2s. No number has an order of 1, save 1, because the cyclic group must contain at least 1 and itself. p-1 is the only value with an order of 2, which you've shown above because (p-1)^2 = 1 (mod p). Therefore, every other number must have an order of s or 2s. All the numbers for which y^s = p-1 (mod p) is true are therefore of order 2s. This is easy to check, because (y^s)^2 = y^(2s) = (p - 1)^2 = 1 (mod p).
This means that the line if y^s = p-1 mod p is another way of expressing the fact that y is a primitive root mod p, and subsequently a generator of the cyclic group Zp.
for all z in [1, p-1], there is some k such that y^k = z mod p.
That's obvious considering that y is a generator of Zp.
Let the set of all such y values be represented as Y.
Gotcha. Y is the set of all primitive roots modulo p.
if y^s = 1 mod p:
If y is of order s mod p.
y^k = z mod p has a solution k if and only if p - z is in Y.
Now, we know that |Y| = totient(totient(p)) = totient(p - 1) = totient(2s) = 2s(1 - 1/2)(1 - 1/s) = 2s(1/2)(1 - 1/s) = s(1 - 1/s) = s - 1. We also know that three other values: 0, 1, and p-1, do not have order s. Therefore, p - 3 - (s - 1) = p - s - 2 = 2s + 1 - s - 2 = s - 1 values have order s. Keep this in mind.
Consider that y forms a cyclic group of order s. It contains the number 1, and s - 1 other elements. These other elements cannot be members of Y. The reason is this:
Let y be of order s mod p. Suppose that the group <y> contains an element of Y. That is, for a an element of Y, and x an integer, y^x = a (mod p). Then, y^2x = a^2 (mod p), y^3x = a^3 (mod p), ... y^(p-1)x = a^(p-1)x (mod p). So therefore, y generates the entire group Zp. But this contradicts the fact that it is of order s mod p.
Therefore, y^x =/= a (mod p) for x an integer and a an element of Y.
0 is also not an element of <y>, for the simple reason that y^x =/= 0 (mod p) if y =/= 0 (mod p).
p-1 is also not an element if s > 2 (feel free to prove p=5 as a special case yourself) because if y^x = p-1 (mod p), then y^2x = (p-1)^2 = 1 (mod p). Since y^s = 1 (mod p), 2x = s, and therefore s is even. But this cannot be. Therefore p-1 is not in <y>.
So we have a group with |<y>| = s. One element is 1. The other elements cannot be (p-1), 0, or anything in Y. The only remaining options are the set of all numbers with order s mod p (which we'll call X, because Y' is hard to read). We have shown that there are exactly s-1 of these, which is convenient, seeing as we need s-1 more elements.
Now we can rephrase your statement as follows: y^k = z mod p has a solution if z is in Z. This is interesting when combined with your original hypothesis, because it implies that if z is in Z, then (p - z) is in Y. That is, there are no primitive roots mod p which are additive inverses.
I haven't worked out yet how to prove this part, but I'll ruminate on it. Still, interesting stuff.
It's been a while since I've done serious maths, so your explanation has helped a great deal... I haven't gotten anything else out of this, but I'll work on things and see where it takes me. I'm not sure if visualizing this data is really going to produce any developments, but go to the program I linked to, and try the safe-prime 47. Consider the sub-grid of y in [2,45 and z in [2,45]. Re-stating what I've said, and what you've added on, is: for any cell with y=z (the diagonal string of ones), either that cell's row, or that cell's column, can contain blanks, but not both; and, for any cell with y+z = 47, either both that cell's row and that cell's column contain blanks, or neither do, and furthermore, they only contain blanks if the cell itself contains blanks. Loosely, the subset of cells with y+z=47 is enough to generate the entire grid (not including the k values within the cells.)
By the way, I intend on going a bit further in all of this, and attempt to figure out a fast way to compute discrete logarithms for any prime (and in general any number, assuming I'm correct in my understanding that the concept of a discrete logarithm can be applied to non-prime base.) Part of my ongoing attempt to prove that P=NP.
Yeah, sure. It's not like it's a hard problem or anything.
As for discrete logarthms, they work in any composite modulo which has primitive roots. Only certain classes of composite numbers can have primitive roots: those of the form 4, 2p, p^a, or 2p^a, where p is an odd prime, a > 1.
Look at the charts for squared safe-primes, and compare to the charts for the safe-prime... I'm making my brains hurt.
Added weirdness... For some safe prime base p (I look at 5, 7, 11, 23, and 47), the y values generating groups of order p-1 follow some sort of pattern:
5: 2, 3
7: 3, 6 (or 3*{1, 2})
11: 2, 6, 7, 8 (or 2*{1,3,4}, 7)
23: 5, 7, 10, 11, 14, 15, 17, 19, 20, 21 (or 5*{1,2,3,4}, 7*{1,2,3}, 11, 17, 19)
47: 5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45 (or 5*{1,2,3,4,6,7,8,9}, 11*{1,2,3,4}, 13*{1,2,3}, 19*{1,2}, 23, 29, 31, 41, 43)
I haven't been able to determine why certain primes are excluded, but the primes that ARE included also imply that every non-square multiple of that prime less than p-1 is also included.
This means that in order to generate the entire grid for a safe prime (ignoring the numbers in the cells,) all you have to compute is the Sophie-Germain-of-p power of every prime less than p-1.
oh, and if some prime a is included, no smaller prime b where a*b is less than p-2 would be included. More or less, this means that using the above representation, every number has a unique representation (5*3 is there, so 3*5 won't be.)
Base 59 half-breaks that pattern:
2*{1,3,4,5,7,9,12,15,16,17,19,20,21,22,25,26,27,28}, 11*{1,3,4,5}, 13*{1,3,4}, 23, 31, 37, 43, 47}
The rule here is a little more complicated. You don't just exclude every square of the prime, but every multiple where, if you factor it out, you get an even number of that prime. So, 6 is included (2^1 * 3^1), but 12 is excluded (2^2 * 3^1), as is 36 (2^2 * 3^2) and 48 (2^4 * 3*1) but every other multiple of 2 is included (2^1 * 3*2, 2^3 * 3^1, 2^1 * 3^1 * 7^1, ...)
I'll have to look at much higher safe-primes before I can see if it's always like this, but I don't have time for that now.
i got one side of a rubics cube the other day. that was my accomplishment for the week.
This is patently obvious, but it may help along the way... For some y with y^s = -1 mod p, every odd power of y will also have that property, so, once we have found a potential candidate y of Zp-1, we can then generate all of the other Zp-1 y's by just taking all the odd powers. On the other hand, any y with y^s = 1 implies that every power of that y also is of Zs. That said, in order to figure out which y's are Zs and which are Zp-1, all you need to do is take the 1 through p-1 (or s, if y^s = 1) powers of 2, and handle the results appropriately.
Okay, I've solved why that for y in [2,p-2], if y is Zp-1*, p-y is Zs*, assuming s > 2 (p > 5)
Assume y^s = -1 mod p.
Note that (p-y) = -y = y(-1) = y(p-1) mod p
(p-y)^s = (y(p-1))^s = y^s(p-1)^s
y^s = -1 mod p
(p-1)^s = -1 mod p since s is necessarily odd (prime > 2)
so (p-y)^s = y^s * (p-1)^s = -1 * -1 = 1
so (p-y)^s is of Zs*.
Damnit, that's so freaking easy. Why was I trying to solve it using binomial expansion on (p-y)^k?
Also, this means that we can expand this to primes of the form 2 * p1^n1 * p2^n2 * ... * pf ^ nf + 1 where p1...pf are primes =/= 2. The reasoning is that p = 2s + 1, where s is no longer prime. And totient(p) = 2s. So if y^s = p-1 (mod p), y generates Zp*, and (p-y) does not.
There is other interesting stuff, too:
Consider any odd prime p, then p = p1^n1 * p2 ^ n2 * ... * pf^nf + 1. For simplicity's sake, lets assume the p terms are in ascending order. Therefore, because p - 1 must be even, p1 = 2, and we can say p = 2s + 1. So s = p2^n2 * ... * pf^nf, where (p1, n1) = (2,1). This is the case above.
Otherwise, s = p1^n1-1 * p2^n2 * ... * pf^nf. From now on, I'm going to represent factorizations as F = {(p1, n1),(p2,n2),...,(pf,nf)}, because it looks nicer. So Fs = {(p1,n1-1),(p2,n2),...,(pf,nf)}. We know a couple things here:
1. |Fs| = number of different prime factors of s = f.
2. sum(i = 1 to f)ni = total number of factors. Call this t.
3. totient(s) = s * product(i = 1 to f)(1 - (1 / pi)) = s + (f - 1) + f! - sum(i = 1 to f)(s/pi)
You might want to check that second formula for the totient. It looks good, but I didn't test it. I know the first one is good.
4. Now, to generalize a little bit, if p = 1 (mod 4), then 2|s. Otherwise, 2 does not divide (I can't make that symbol using ASCII) s (and p = 3 (mod 4)). Therefore, if p = 3 (mod 4), s's f = p's f - 1.
Let's see where that gets us.
Also, on a different tack: consider the follow series: 2,5,11,23,47. 5,11,23, and 47 are all safe primes. 2,5,11, and 23 are all Sophie-Germain primes. Are there other such chains? Are they longer? With what frequency do they occur?
The next-longest chain starts at 89: 89, 179, 359, 719, 1439, 2879.
What you're asking about are Cunningham chains of the first kind: http://primes.utm.edu/glossary/page.php?sort=CunninghamChain
Now I'm starting to consider the numbers within the cells. Only considering columns of Zp-1*, I've found a relationship between the numbers in one column and the numbers in another. Take, for simplicities sake, p=11. We get 4 Z10* chains, for y in {2, 6, 7, 8}. First, take the sequence of discrete logs for y = 2, and z in [1, 10]: y^(10, 1, 8, 2, 4, 9, 7, 3, 6, 5) = z. Now, consider the fact that 6^x = 2, for some x. This means that 6^nx = 2^n, so the cells in column 6 will be those in column 2, times n. Finding n can still a tricky operation, but I believe it can be done relatively quickly, given an appropriate algorithm:
First, compute the column for the first Zp-1* digit, in this case 2. This gives us the list above, restated here: (10, 1, 8, 2, 4, 9, 7, 3, 6, 5). This will be an expensive operation for large p values, but will grow linearly.
This gives us all other Zp-1* candidate y's (the indices of the odd powers, or {2, 6, 7, 8, 10}. We can ignore 10 since we're only interested in [2, p-2]. Now, we pair the powers of 2 with the new y values: {(1, 2), (9, 6), (7, 7), (3, 8)}. For each pair (take (9, 6) for example), we need to find some n such that the power of 2 (9 here) times n = 1 mod p-1. So, 9*n = 1 mod p-1. n must be in [1, p-1] for reasons I don't feel like getting into here. Again, this is an area that would benefit from a quick lookup-operation, but I don't know of any. Doing this with p=11 makes it easy, because we're working in mod p-1 now, which is mod 10, which is easy for our brains. The n here is easily determined to be 9. (9*9 = 1 mod 10). Now, we can translate the 2 column to the 6 column by multiplying every cell by 9, mod 10. This works for every other column, and in every other base.
Unfortunately, brute-forcing this is unlikely to yield a speed increase. It takes O(p) time to compute the first column, and O(p) time to find the appropriate n values, which needs to be done O(p) times, making the overall time for the entire grid to be O(p^2), which is the same if we just computed each cell individually. We only need to compute the discrete log once, though, in order to get it for all Zp-1* columns. If we can find a cheaper 'n' value lookup function less than O(p), let's say O(f(p)), then we can increase the speed to O(p*f(p))... I'm getting the feeling here that I'm just turning one hard problem into another hard problem.
Okay, this is getting long for a blog conversation... Once I get my French homework out of the way, I'm going to create some sort of page where all this stuff can be segmented more easily.
Something better. Feel free to establish whatever sort of structure you feel is appropriate. You'll want the MathML fonts, available here.
Post a Comment