Return to Answer

If one would like to have some "formula"/definition that would give a generator as requested for each field of prime order and always 'the same' for (isomorphic) fields, one could proceed like this:

Let $g_F = n \cdot 1_{F}$ where $$n = \min \{m \in \mathbb{N} \colon \text{ord} ( m \cdot 1_F) = |F|-1\}$$ and $\text{ord}$ denotes the multiplicative order (which one could also write out just using the field operations and quantifiers and the natural numbers).

If I oversee things correctly (which is a lot less clear than usually when I answer) one could define in principle this way a functor from the category with objects fields of prime order and morphism field homomorphisms (or iso would be the same in this case) to the category of "fields of prime order with minimally chosen multiplicative generator" (objects field of prime order plus distinguished element as defined above, and morphisms fields homo/isomorphisms mapping the distinguished element to the distinguished element of the respective fields).

The point being that between fields of different prime cardinality there is no morphism at all, and if the cardinality is the same there is exatly one (as everything is determine by the one-element).

So, it is in principle possible to "select" (in a uniform way for all such fields) some 'distinguished' (which perhaps one might call canonical) multiplicatively generating element. (Of course one could also make other selections than the minimal one.)

I am sorry if this either should not make sense at all, or should miss the point completely. In either case I would be glad for an explication.

Old version:

To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.

A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).

So, if you want some 'canonical' (in a certain sense) choice, take the smallest. Alas no one knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjectured it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).

To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).

And the question is somewhat closely linked to the discrete logarithm problem which is knwon to be hard.

See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/

One more update (sorry for the slight sillyness, and hoping I at least got it right, yet it is not optimized):

For $F$ a field of prime cardinality $$1 + \sum_{a=1}^{|F|-1} \prod_{b=1}^{a} (1 - \prod_{d=1}^{|F|-2}(b^d -1)^{|F|-1} )$$ generates the multiplicative group (with usual convention that $n$ is $n \cdot 1_F$).

If one would like to have some "formula"/definition that would give a generator as requested for each field of prime order and always 'the same' for (isomorphic) fields, one could proceed like this:

Let $g_F = n \cdot 1_{F}$ where $$n = \min \{m \in \mathbb{N} \colon \text{ord} ( m \cdot 1_F) = |F|-1\}$$ and $\text{ord}$ denotes the multiplicative order (which one could also write out just using the field operations and quantifiers and the natural numbers).

If I oversee things correctly (which is a lot less clear than usually when I answer) one could define in principle this way a functor from the category with objects fields of prime order and morphism field homomorphisms (or iso would be the same in this case) to the category of "fields of prime order with minimally chosen multiplicative generator" (objects field of prime order plus distinguished element as defined above, and morphisms fields homo/isomorphisms mapping the distinguished element to the distinguished element of the respective fields).

The point being that between fields of different prime cardinality there is no morphism at all, and if the cardinality is the same there is exatly one (as everything is determine by the one-element).

So, it is in principle possible to "select" (in a uniform way for all such fields) some 'distinguished' (which perhaps one might call canonical) multiplicatively generating element. (Of course one could also make other selections than the minimal one.)

I am sorry if this either should not make sense at all, or should miss the point completely. In either case I would be glad for an explication.

Old version:

To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.

A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).

So, if you want some 'canonical' (in a certain sense) choice, take the smallest. Alas no one knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjectured it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).

To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).

And the question is somewhat closely linked to the discrete logarithm problem which is knwon to be hard.

See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/

To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.

A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).

So, if you want some 'canonical' (in a certain sense) choice, take the smallest. Alas no one knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjectured it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).

To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).

And the question is somewhat closely linked to the discrete logarithm problem which is knwon to be hard.

See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/

If one would like to have some "formula"/definition that would give a generator as requested for each field of prime order and always 'the same' for (isomorphic) fields, one could proceed like this:

Let $g_F = n \cdot 1_{F}$ where $$n = \min \{m \in \mathbb{N} \colon \text{ord} ( m \cdot 1_F) = |F|-1\}$$ and $\text{ord}$ denotes the multiplicative order (which one could also write out just using the field operations and quantifiers and the natural numbers).

If I oversee things correctly (which is a lot less clear than usually when I answer) one could define in principle this way a functor from the category with objects fields of prime order and morphism field homomorphisms (or iso would be the same in this case) to the category of "fields of prime order with minimally chosen multiplicative generator" (objects field of prime order plus distinguished element as defined above, and morphisms fields homo/isomorphisms mapping the distinguished element to the distinguished element of the respective fields).

The point being that between fields of different prime cardinality there is no morphism at all, and if the cardinality is the same there is exatly one (as everything is determine by the one-element).

So, it is in principle possible to "select" (in a uniform way for all such fields) some 'distinguished' (which perhaps one might call canonical) multiplicatively generating element. (Of course one could also make other selections than the minimal one.)

I am sorry if this either should not make sense at all, or should miss the point completely. In either case I would be glad for an explication.

Old version:

To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.

A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).

So, if you want some 'canonical' (in a certain sense) choice, take the smallest. Alas no one knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjectured it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).

To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).

And the question is somewhat closely linked to the discrete logarithm problem which is knwon to be hard.

See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/

To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.

A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).

So, if you want some 'canoncical' (in a certain sense) choice, take the smallest. Alas noone knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjecture it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).

To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).

And the question is somewhat closely linked to the discrete logarithl problem which is knwon to be hard.

See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/

To say that a "formula" cannot exist is always a bit of a tricky issue, as there are for examples formulas that generate primes still these are in general of little relevance for finding them.

A generator of this group typically goes by the name of primitive root modulo $p$ and to find one algorithmically is not easy, and of course there are various (open) conjectures on the smallest one (which would not in itself preclude that one could find some).

So, if you want some 'canonical' (in a certain sense) choice, take the smallest. Alas no one knows how large it is; the I believe best upper bound is $p^{1/4 + \varepsilon}$; under the extended Rieman hypothesis one has $O((\log p)^6)$. On the other hand one knows that for infinitely many primes it is as large as $C \log p$, while it is famously conjectured it is infinitely often also $2$ (and it is known it is infinitely of one of a very small set of small numbers).

To say something more specific: the best (to my knowledge) deterministic algorithm to find one takes $p^{1/4 + o(1)}$ (by Shparlinski).

And the question is somewhat closely linked to the discrete logarithm problem which is knwon to be hard.

See this paper by Bachman for more information http://www.ams.org/journals/mcom/1997-66-220/S0025-5718-97-00890-9/