Realistic analysis of some randomized algorithms (Q2277019)

The author considers algorithms calling for random numbers which might satisfy a condition with probability 1/2. If the first random number x fails then it is natural to try \(x\to x+1\) until the algorithm succeeds, (or maybe \(x\to \alpha x+\beta).\) We assume these trials to be ``independent'', but in many cases there is a proof by the theory of algebraic curves that successive trials effectively have probability (almost) 1/2, by use of algebraic curve theory. For instance, the Cipolla-Lehmer algorithm for finding \(\sqrt{a} mod p\), for a residue a, requires that x be found such that \(x^ 2-4a\) is a nonresidue mod p. The ``bad'' situation is k successive failures for x, \(x+1,...,x+k-1\). Then the k equations \(Y^ 2_ 1-(X^ 2-4a),...,Y_ k^ 2-((X+k-1)^ 2- 4a)\) represent a space-curve with a point in \({\mathbb{F}}_ p\). This is generally a complete intersection (by independence of the radicals \(Y_ j)\) and there is a classical (Weil) theory for counting such points. The conclusion is that if k has the order of magnitude \((\log_ 2p)/2\) then the probability of failure is O((log p)/\(\sqrt{p})\). A similar analysis is made of the Tonelli-Shanks method for doing the same thing. Other applications including Miller primality tests are given. There is a very useful bibliography.