Timeline for Subgroups of multiplicative groups of the finite field with Mersenne prime order
Current License: CC BY-SA 4.0
43 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 11, 2020 at 22:07 | review | Close votes | |||
| Jun 17, 2020 at 3:04 | |||||
| Jun 11, 2020 at 22:06 | history | edited | Alexander | CC BY-SA 4.0 |
added 12 characters in body
|
| Jun 11, 2020 at 21:57 | comment | added | Alexander | The multiplicative group can be represented as table Rows: cosets for $C_k$ Columns: cosets for $C_{\frac{2^{k}-2}{k}}$ I know the generator for rows, but don't know the generator for columns if I find it - any element would be represented as $g^{r}*2^{s}$ for some $r,s$ | |
| Jun 11, 2020 at 21:53 | comment | added | Alexander | hypothesis: this is $3*2^t$ for some $t$ | |
| Jun 11, 2020 at 21:52 | comment | added | Alexander | no, I mean some formula | |
| Jun 11, 2020 at 21:50 | comment | added | verret | @AVT Can you clarify what you mean by "how to find"? Do you mean a fast algorithm? etc. | |
| Jun 11, 2020 at 17:04 | history | edited | Alexander | CC BY-SA 4.0 |
added 1 character in body
|
| Jun 11, 2020 at 16:42 | comment | added | Alexander | What is order of $3$ in such multiplicative groups ? | |
| Jun 11, 2020 at 16:31 | comment | added | Alexander | Modified question, added condition. | |
| Jun 11, 2020 at 16:31 | history | edited | Alexander | CC BY-SA 4.0 |
added 42 characters in body
|
| Jun 11, 2020 at 16:26 | comment | added | Emil Jeřábek | I can’t give you an example, as only two Wieferich primes are known. But anyway, the multiplicative group is $C_{2^k-2}$, which is isomorphic to $C_k\times C_{(2^k-2)/k}$ only if $k$ is coprime to $(2^k-2)/k$, and there is no a priori reason this should be the case. | |
| Jun 11, 2020 at 16:22 | comment | added | Alexander | @Emil Jeřábek Sorry don't understand your point Would be appreciative for such example of $k$ | |
| Jun 11, 2020 at 16:16 | comment | added | LSpice | @EmilJeřábek, right, I know that modular exponentiation is fast. That's why I was suggesting that a less difficult task than finding a generator—I assumed the question was how to find it quickly, since otherwise you can do as @GeoffRobinson suggests—might be to seek a faster test for membership than just exponentiation. | |
| Jun 11, 2020 at 16:12 | comment | added | Emil Jeřábek | @AVT The multiplicative group is not $C_k\times C_{(2^k-2)/k}$ if $k$ is a Wieferich prime; are you saying that this can’t happen? ($2^k-1$ itself cannot be Wieferich, but this is something else.) | |
| Jun 11, 2020 at 16:07 | comment | added | Emil Jeřábek | @LSpice Quite fast (in time $\tilde O(k^2)$ or so). This is just modular exponentiation. | |
| Jun 11, 2020 at 15:58 | comment | added | LSpice | @EmilJeřábek, right, but how fast can you perform that exponentiation? (Faster than $\mathrm O(2^k/k)$, obviously, now that I think about it; but, yes, testing that property quickly is what I had in mind.) | |
| Jun 11, 2020 at 15:58 | comment | added | Alexander | Is it possible that $g = 2^{t}*3$ ? | |
| Jun 11, 2020 at 15:55 | comment | added | Emil Jeřábek | @LSpice Testing membership is easy, as the group just consists of all $x$ such that $x^{(2^k-2)/k}=1$. | |
| Jun 11, 2020 at 15:35 | comment | added | Alexander | The whole multiplicative group is actually $C_k x C_{\frac{2^k-2}{k}}$ And I thought that may be there are some interesting properties | |
| Jun 11, 2020 at 15:33 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| Jun 11, 2020 at 15:31 | comment | added | Geoff Robinson | You might as well ask for a generator $x$ for the whole multiplicative group of the field, and then take $x^{k}$. | |
| S Jun 11, 2020 at 14:59 | history | suggested | Carl-Fredrik Nyberg Brodda | CC BY-SA 4.0 |
Added note that subgroups of multiplicative groups of finite fields are always cyclic
|
| Jun 11, 2020 at 14:59 | review | Suggested edits | |||
| S Jun 11, 2020 at 14:59 | |||||
| Jun 11, 2020 at 14:54 | comment | added | Alexander | May be there is some interesting property for described subgroup ? | |
| Jun 11, 2020 at 14:53 | comment | added | Alexander | For example generator for subgroup of order $k$ is clear - it is always 2. | |
| Jun 11, 2020 at 14:45 | comment | added | LSpice | OK, I see that you have changed the question to remove the incorrect conjecture; now it makes sense. The subgroup is cyclic—all finite subgroups of multiplicative groups of fields are—so there is no need to gather evidence for the existence of $g$. My suspicion is that this is probably not much easier than finding a primitive generator for a random $\mathbb Z/p\mathbb Z$, which is hard, but I have no evidence for that. It may be interesting even to see if you can come up with an $\mathrm o(2^k/k)$ algorithm for testing membership in this subgroup (but I'm no expert; it may be known). | |
| Jun 11, 2020 at 14:44 | history | edited | Alexander | CC BY-SA 4.0 |
added 30 characters in body
|
| Jun 11, 2020 at 14:42 | comment | added | Alexander | The question is the same: how to find generator for this subgroup ? | |
| Jun 11, 2020 at 14:42 | comment | added | Alexander | 24 68 108 52 105 107 28 37 126 103 59 19 75 22 20 99 90 1 | |
| Jun 11, 2020 at 14:37 | comment | added | LSpice | How can the question be the same? You've made a conjecture, and shown that it is false. | |
| Jun 11, 2020 at 14:37 | history | edited | Alexander | CC BY-SA 4.0 |
deleted 123 characters in body
|
| Jun 11, 2020 at 14:36 | comment | added | Alexander | Correct my bad. Anyway the question is the same. | |
| Jun 11, 2020 at 14:35 | comment | added | LSpice | Yes, your computations are correct, and they show that the order of $18$ modulo $127$ is not less than $18$; but, as you can tell by going one step further, it's not $18$, either. In fact, the order of $18$ modulo $127$ is $63$. | |
| Jun 11, 2020 at 14:32 | comment | added | Alexander | I just wrote simple computer script | |
| Jun 11, 2020 at 14:31 | comment | added | Alexander | 1 18 70 117 74 62 100 22 15 16 34 104 94 41 103 76 98 113 | |
| Jun 11, 2020 at 14:30 | comment | added | LSpice | Note that $18^{18} \equiv 2 \pmod{2^7 - 1}$, so I think your conjecture fails for the case $k = 7$, $g = 18$ that you specify. | |
| Jun 11, 2020 at 14:16 | review | Close votes | |||
| Jun 11, 2020 at 16:01 | |||||
| Jun 11, 2020 at 14:08 | history | edited | Alexander | CC BY-SA 4.0 |
added 6 characters in body
|
| Jun 11, 2020 at 14:01 | comment | added | Alexander | Fixed my mistake , thanks | |
| Jun 11, 2020 at 14:01 | history | edited | Alexander | CC BY-SA 4.0 |
edited body
|
| Jun 11, 2020 at 13:58 | comment | added | LSpice | The equality $k = \frac{2^k - 2}k$ is obviously false. (For example, as you say, for $k = 5$ it does not work.) What do you mean? | |
| Jun 11, 2020 at 13:36 | review | First posts | |||
| Jun 11, 2020 at 14:15 | |||||
| Jun 11, 2020 at 13:35 | history | asked | Alexander | CC BY-SA 4.0 |