Timeline for A formula for a generator of the multiplicative group of $\mathbb{F}_p$ ?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 21, 2013 at 21:57 | comment | added | user9072 | You are welcome! It was interesting to think about this for me. Yes one might wish to avoid knowing the divisors. But at least the improvement to only go to (|F|-1)/2 could always be done. | |
| Feb 21, 2013 at 10:45 | comment | added | Matthieu Romagny | On the other hand, optimizing implies knowing some arithmetic of $p-1$ (e.g. its decomposition into primes) and then it gets complicated. By the way, thanks quid for your participation! | |
| Feb 20, 2013 at 18:19 | comment | added | user9072 | Yes, I agree. This is about what I had in mind when saying it is not optimized. | |
| Feb 20, 2013 at 15:31 | comment | added | Matthieu Romagny | ... and in particular $d\le \lfloor (p-1)/2 \rfloor$. | |
| Feb 20, 2013 at 15:29 | comment | added | Matthieu Romagny | I came to a similar formula after discussions with Pascal Boyer. And if I have it right, in the second product you can restrict to $d$'s dividing $|F|-1$. | |
| Feb 19, 2013 at 23:13 | history | edited | user9072 | CC BY-SA 3.0 |
added 'fun' formula; edited body
|
| Feb 19, 2013 at 20:43 | comment | added | user9072 | Personally I hardly use the word "canonical". Yet, if one would not consider the field but only the multiplicative group (I think) one could show that there cannot be a functor (or likely I should say faithful functor or something) from cyclic groups to cyclic groups with distinguished generating element. (And in some sense it seems there is even no apparent way to "name" a distinguished generating element just knowing the group abstractly.) | |
| Feb 19, 2013 at 20:26 | comment | added | Matthieu Romagny | I agree that the smallest integer $g$ such that $g.1$ is a generator in $(\mathbb{F}_p)^\times$ makes sense and is preserved by all field automorphisms. This supports the claim that there is a canonical generator. However this "canonical" generator clearly does not enjoy better algebraic or number-theoretic properties than the other generators, but in our daily experience canonical objects <em>do</em> have nice properties. I am starting to think that the statement that "there is no canonical generator" is just a way of speaking that carries hardly any solid mathematical content. | |
| Feb 19, 2013 at 19:22 | history | edited | user9072 | CC BY-SA 3.0 |
expanded to reflect updated version of the question
|
| Feb 19, 2013 at 14:49 | history | edited | José Hdz. Stgo. | CC BY-SA 3.0 |
added 1 characters in body
|
| Feb 19, 2013 at 13:44 | comment | added | user9072 | The "known" in the in the discret logarithm proble is a bit sloppy, i should likely better say 'well-known to be believed to be hard'. | |
| Feb 19, 2013 at 13:30 | history | answered | user9072 | CC BY-SA 3.0 |