Timeline for Are there natural choices of $\sqrt{-1}$ in $\mathbb Z/p\mathbb Z$ for a prime $p\equiv 1\pmod 4$
Current License: CC BY-SA 2.5
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 22, 2010 at 5:42 | comment | added | Victor Protsak | When searching for a quadratic non-residue, it's somewhat better to test randomly generated $g$ than consecutive small $a$. This is because when $a$ and $b$ are both residues, then so are $ab$ and the smallest non-residue must be a prime; if you believe in statistical independence of residuosity of small primes then we'll be doing extra work. On the other hand, in the randomized algorithm the lucky probability is always 1/2, but the tradeoff is the cost of computing $\binom{a}{p}$ when $a$ is large if it doesn't yield the answer. Thus it may be preferable to test tabulated small primes. | |
| Jun 22, 2010 at 4:55 | comment | added | Wadim Zudilin | Yes, that would be another option. There are several $p$-congruences where the products $\Gamma_p(x)\Gamma_p(1-x)$ occur, but I can't find any (reasonable!) with a sole gamma. | |
| Jun 22, 2010 at 3:06 | comment | added | Junkie | You can also rewrite $((p-1)!/2)$, up to $(-1)^{(p+1)/2}$, as $\Gamma_p(1/2)$ which I think Cohen calls the canonical root. See Corollary 11.6.3 and comments thereafter in his book. | |
| Jun 22, 2010 at 2:43 | history | answered | Wadim Zudilin | CC BY-SA 2.5 |