Felix' Math Place (Posts about algorithms.)https://math.fontein.de/tag/algorithms.atom2019-11-17T10:38:19ZFelix FonteinNikolaFinding Lattice Points, Finite Abelian Groups, and Explaining Algorithms.https://math.fontein.de/2010/01/29/finding-lattice-points-finite-abelian-groups-and-explaining-algorithms/2010-01-29T10:20:34+01:002010-01-29T10:20:34+01:00Felix Fontein<div>
<p>
In this article, I want to discuss three questions, which turn out to be closely related. The first question is,
</p>
<blockquote class="block-quote">
<p>
“Given a lattice <span class="inline-formula"><img class="img-inline-formula img-formula" width="58" height="15" src="https://math.fontein.de/formulae/EBTY1cww2.XbyZp0zeo5cPIgVso4OVcWdqrNBg.svgz" alt="\Lambda \subseteq \R^n" title="\Lambda \subseteq \R^n"></span>. How do I find a basis of this lattice?”
</p>
</blockquote>
<p>
(Note that this question is far from being well-posed.) The second question is,
</p>
<blockquote class="block-quote">
<p>
“If <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/1SEBa2mo2npdO9VAigPQfAPRoqEDUsQLVvcYYg.svgz" alt="G" title="G"></span> is a finite abelian group and <span class="inline-formula"><img class="img-inline-formula img-formula" width="109" height="16" src="https://math.fontein.de/formulae/BWBfkw1tFOwkSFCyGjYCJHLTKtrsFhMzoE.pmg.svgz" alt="g_1, \dots, g_n \in G" title="g_1, \dots, g_n \in G"></span>, how do I compute the structure of <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/AFTrljwrIUL8p87wUjwHIKTeq3wKZh2LGnLnqQ.svgz" alt="\langle g_1, \dots, g_n \rangle" title="\langle g_1, \dots, g_n \rangle"></span>, the subgroup generated by these elements?”
</p>
</blockquote>
<p>
The third question comes up in the description of algorithms, for example of the <a href="https://en.wikipedia.org/wiki/Baby-step_giant-step">baby-step giant-step</a> algorithm by D. Shanks, an optimization by D. Terr, and more general algorithms, like the <a href="http://www.ams.org/mcom/2005-74-252/S0025-5718-05-01740-0/home.html">Buchmann-Schmidt</a> algorithm. These algorithms can be described in terms of the first question, making them easier to understand.
</p>
<p>
We begin with sketching the relation between lattices and finite abelian groups. If <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/1SEBa2mo2npdO9VAigPQfAPRoqEDUsQLVvcYYg.svgz" alt="G" title="G"></span> is a finite abelian group, and <span class="inline-formula"><img class="img-inline-formula img-formula" width="109" height="16" src="https://math.fontein.de/formulae/BWBfkw1tFOwkSFCyGjYCJHLTKtrsFhMzoE.pmg.svgz" alt="g_1, \dots, g_n \in G" title="g_1, \dots, g_n \in G"></span> some elements, for example, a set of generators, consider the map
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="380" height="52" src="https://math.fontein.de/formulae/Y9ZkuypXm6G6JUFzuvigrsv9oe535tRDS5gQzw.svgz" alt="\Psi_{(g_1, \dots, g_n)} : \Z^n \to G, \qquad (\lambda_1, \dots, \lambda_n) \mapsto \sum_{i=1}^n \lambda_i g_i." title="\Psi_{(g_1, \dots, g_n)} : \Z^n \to G, \qquad (\lambda_1, \dots, \lambda_n) \mapsto \sum_{i=1}^n \lambda_i g_i.">
</div>
<p>
This turns out to be a group homomorphism onto <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/AFTrljwrIUL8p87wUjwHIKTeq3wKZh2LGnLnqQ.svgz" alt="\langle g_1, \dots, g_n \rangle" title="\langle g_1, \dots, g_n \rangle"></span>. The kernel of <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="18" src="https://math.fontein.de/formulae/Thn.VJ6EcZXjfBQX6vC8ro_zJh31O7U7KeAoYQ.svgz" alt="\Psi_{(g_1, \dots, g_n)}" title="\Psi_{(g_1, \dots, g_n)}"></span>, which we will denote by <span class="inline-formula"><img class="img-inline-formula img-formula" width="75" height="18" src="https://math.fontein.de/formulae/GG3EhhMCSaVPIvV65_g9OCvFQq5mjPQGmXNMdA.svgz" alt="\Lambda_{(g_1, \dots, g_n)}" title="\Lambda_{(g_1, \dots, g_n)}"></span>, is called the <em>relation lattice</em>. This is in fact a lattice in <span class="inline-formula"><img class="img-inline-formula img-formula" width="22" height="12" src="https://math.fontein.de/formulae/bZVXuWhECmRV9pmTW_AgHZeLTOYax7svHPDCxQ.svgz" alt="\R^n" title="\R^n"></span> of volume
</p>
<div class="display-formula">
<img class="img-display-formula img-formula" width="372" height="21" src="https://math.fontein.de/formulae/lkM6shlKOxYX1WIwjR7Z.etcoPTsN17SYDE9tQ.svgz" alt="\det \Lambda_{(g_1, \dots, g_n)} = \abs{\Z^n / \Lambda_{(g_1, \dots, g_n)}} = \abs{\langle g_1, \dots, g_n\rangle};" title="\det \Lambda_{(g_1, \dots, g_n)} = \abs{\Z^n / \Lambda_{(g_1, \dots, g_n)}} = \abs{\langle g_1, \dots, g_n\rangle};">
</div>
<p>
note that by the Homomorphism Theorem, <span class="inline-formula"><img class="img-inline-formula img-formula" width="216" height="20" src="https://math.fontein.de/formulae/L1UwOXe8hZ9PPRPjTAbhxUae4kKQL5zzVKhUuQ.svgz" alt="\langle g_1, \dots, g_n \rangle \cong \Z^n / \Lambda_{(g_1, \dots, g_n)}" title="\langle g_1, \dots, g_n \rangle \cong \Z^n / \Lambda_{(g_1, \dots, g_n)}"></span>. On the other hand, if <span class="inline-formula"><img class="img-inline-formula img-formula" width="57" height="15" src="https://math.fontein.de/formulae/J8WZLQNTj4hsLiLptic9ZbHN6du478Qep2spzQ.svgz" alt="\Lambda \subseteq \Z^n" title="\Lambda \subseteq \Z^n"></span> is a lattice, then <span class="inline-formula"><img class="img-inline-formula img-formula" width="85" height="18" src="https://math.fontein.de/formulae/QXEARutZhkoMuJNkP5mTBLrSW0l6mbq3Sux3Og.svgz" alt="G := \Z^n / \Lambda" title="G := \Z^n / \Lambda"></span> is a finite abelian group of <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="12" src="https://math.fontein.de/formulae/MkKgnu7KW8WKNztwQZ467RqtXt6ZZmpv_Ql7dQ.svgz" alt="\det G" title="\det G"></span> elements. Moreover, if the residue class of <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="10" src="https://math.fontein.de/formulae/YKfTJhroPCuKti4tYD9Nez3w2qenB_QDlTC_qg.svgz" alt="e_i" title="e_i"></span>, the vector consisting of zeroes except a one at the <span class="inline-formula"><img class="img-inline-formula img-formula" width="6" height="12" src="https://math.fontein.de/formulae/S43oPTrFqmoVC.yqOcgzvrroaMU3pS7pa40ROQ.svgz" alt="i" title="i"></span>-th position, in <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/1SEBa2mo2npdO9VAigPQfAPRoqEDUsQLVvcYYg.svgz" alt="G" title="G"></span> is denoted by <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="11" src="https://math.fontein.de/formulae/Y7fPqfXQseOSvmc5S_ABBbRn3pC6Brh_wI4sqQ.svgz" alt="g_i" title="g_i"></span>, then <span class="inline-formula"><img class="img-inline-formula img-formula" width="111" height="18" src="https://math.fontein.de/formulae/tVQw8MqssNEjyNGYevnC4sBy2Dhe5hEs8wb.Pg.svgz" alt="\Lambda = \Lambda_{(g_1, \dots, g_n)}" title="\Lambda = \Lambda_{(g_1, \dots, g_n)}"></span>. Therefore, lattices in <span class="inline-formula"><img class="img-inline-formula img-formula" width="21" height="12" src="https://math.fontein.de/formulae/b0L3WheKKmrzgT4WpFrivkdln2XTtzJYEJqQZQ.svgz" alt="\Z^n" title="\Z^n"></span> and finite abelian groups with <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> generators are essentially the same thing.
</p>
<p>
How is this related to group structure computations? Recall the <a href="https://en.wikipedia.org/wiki/Smith_normal_form">Smith normal form</a>; this allows to convert a basis <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/zt1itL6D8gU1KsAconD3EjSKDrQySl4EWvudTQ.svgz" alt="(v_1, \dots, v_n)" title="(v_1, \dots, v_n)"></span> of a lattice <span class="inline-formula"><img class="img-inline-formula img-formula" width="12" height="12" src="https://math.fontein.de/formulae/XY_2LK590TGO0.jb0ZbkmaiBi4kJr1xvp52q2g.svgz" alt="\Lambda" title="\Lambda"></span> into another basis, such that if one applies an invertible linear transformation to <span class="inline-formula"><img class="img-inline-formula img-formula" width="21" height="12" src="https://math.fontein.de/formulae/b0L3WheKKmrzgT4WpFrivkdln2XTtzJYEJqQZQ.svgz" alt="\Z^n" title="\Z^n"></span>, this basis is sent to <span class="inline-formula"><img class="img-inline-formula img-formula" width="112" height="16" src="https://math.fontein.de/formulae/HhVipjjN6cYHd9Xd_aJOf6bf2p06uGaEWE7SBA.svgz" alt="\lambda_1 e_1, \dots, \lambda_n e_n" title="\lambda_1 e_1, \dots, \lambda_n e_n"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="70" height="16" src="https://math.fontein.de/formulae/JOggpGgO3_IvXwUFjqnmLxk6FVafwqwKwNbQ0g.svgz" alt="\lambda_i \in \N_{>0}" title="\lambda_i \in \N_{>0}"></span> such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="15" src="https://math.fontein.de/formulae/wgS2TExzobiFvFSVhuw63UrFJJrpoTTHDB74fQ.svgz" alt="\lambda_i" title="\lambda_i"></span> divides <span class="inline-formula"><img class="img-inline-formula img-formula" width="34" height="16" src="https://math.fontein.de/formulae/pTT3Gk7R30fvmX0jEVi8rRtBqSFCxONvwtTo1A.svgz" alt="\lambda_{i+1}" title="\lambda_{i+1}"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="73" height="14" src="https://math.fontein.de/formulae/vxFxMFWjKONmQE8PUHCs34oV1vHCFu1qaP8V0g.svgz" alt="1 \le i < n" title="1 \le i < n"></span>; then, <span class="inline-formula"><img class="img-inline-formula img-formula" width="158" height="20" src="https://math.fontein.de/formulae/86s1qsl0WbCGfA9uznKuaJQqpJfr8ej_7dO.EA.svgz" alt="\Z^n / \Lambda \cong \prod_{i=1}^n \Z/\lambda_i \Z" title="\Z^n / \Lambda \cong \prod_{i=1}^n \Z/\lambda_i \Z"></span>. Hence, computing the structure of a finite abelian group generated by <span class="inline-formula"><img class="img-inline-formula img-formula" width="74" height="11" src="https://math.fontein.de/formulae/Fu0_nlKIc0UUBt4FnNjm2anOMMT5GEx2bVAbSA.svgz" alt="g_1, \dots, g_n" title="g_1, \dots, g_n"></span> can be split up in the two parts, (a) computation of a basis of the relation lattice <span class="inline-formula"><img class="img-inline-formula img-formula" width="75" height="18" src="https://math.fontein.de/formulae/GG3EhhMCSaVPIvV65_g9OCvFQq5mjPQGmXNMdA.svgz" alt="\Lambda_{(g_1, \dots, g_n)}" title="\Lambda_{(g_1, \dots, g_n)}"></span> and (b) computation of a Smith normal form of this basis. There exist a lot of algorithms for computation of Smith normal forms; usually, the bottleneck is finding a basis of <span class="inline-formula"><img class="img-inline-formula img-formula" width="75" height="18" src="https://math.fontein.de/formulae/GG3EhhMCSaVPIvV65_g9OCvFQq5mjPQGmXNMdA.svgz" alt="\Lambda_{(g_1, \dots, g_n)}" title="\Lambda_{(g_1, \dots, g_n)}"></span>.
</p>
<p>
Often, the process of finding a lattice equals determining the relation lattice of a finite abelian group, or something similar. One often has a way to test whether <span class="inline-formula"><img class="img-inline-formula img-formula" width="114" height="14" src="https://math.fontein.de/formulae/z_cD9X9Z8q.HuJUDaKA61lbtB3NP_wX15oce.Q.svgz" alt="v + \Lambda = w + \Lambda" title="v + \Lambda = w + \Lambda"></span>, by computing a unique representation of the residue class <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="14" src="https://math.fontein.de/formulae/ljhySPBiN.RBkydZIg_F9Zi0ZYn3hsHU1qkAqw.svgz" alt="v + \Lambda" title="v + \Lambda"></span>; then, one tries to find two ways <span class="inline-formula"><img class="img-inline-formula img-formula" width="114" height="14" src="https://math.fontein.de/formulae/z_cD9X9Z8q.HuJUDaKA61lbtB3NP_wX15oce.Q.svgz" alt="v + \Lambda = w + \Lambda" title="v + \Lambda = w + \Lambda"></span> of writing the same residue class, but with <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="16" src="https://math.fontein.de/formulae/92ZakeUtmlthAn5lYIe64jt87JCr.MsZVE4cDg.svgz" alt="v \neq w" title="v \neq w"></span>: then <span class="inline-formula"><img class="img-inline-formula img-formula" width="44" height="12" src="https://math.fontein.de/formulae/cRcW1c2DGsIPzli9rAb5DrCb699rSQa9zuHjkQ.svgz" alt="v - w" title="v - w"></span> is a non-trivial element of <span class="inline-formula"><img class="img-inline-formula img-formula" width="12" height="12" src="https://math.fontein.de/formulae/XY_2LK590TGO0.jb0ZbkmaiBi4kJr1xvp52q2g.svgz" alt="\Lambda" title="\Lambda"></span>. If one sets <span class="inline-formula"><img class="img-inline-formula img-formula" width="85" height="18" src="https://math.fontein.de/formulae/QXEARutZhkoMuJNkP5mTBLrSW0l6mbq3Sux3Og.svgz" alt="G := \Z^n / \Lambda" title="G := \Z^n / \Lambda"></span>, then this means that one seeks for pairs <span class="inline-formula"><img class="img-inline-formula img-formula" width="40" height="18" src="https://math.fontein.de/formulae/acPN39KZ4v3YoVjuZPiNkEBm6yWgEXs9tdSV.Q.svgz" alt="(v, g)" title="(v, g)"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="45" height="18" src="https://math.fontein.de/formulae/q.aj7E737Va0ICujJpDZw0z4hMbYXrcAM29.2A.svgz" alt="(w, h)" title="(w, h)"></span>, where <span class="inline-formula"><img class="img-inline-formula img-formula" width="76" height="16" src="https://math.fontein.de/formulae/ZlWkW1R1yVrhGskbaI.6xxURGu.acD0kJIBHaw.svgz" alt="g = v + \Lambda" title="g = v + \Lambda"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="81" height="14" src="https://math.fontein.de/formulae/80tj1Pf0C3AOTqiYoE7ChlUcXjKr9rcjD368xQ.svgz" alt="h = w + \Lambda" title="h = w + \Lambda"></span>, such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="43" height="16" src="https://math.fontein.de/formulae/K5uunNv0DaadfiOcEpAjgR7UZMQFXl6LPFuQRg.svgz" alt="g = h" title="g = h"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="46" height="16" src="https://math.fontein.de/formulae/92ZakeUtmlthAn5lYIe64jt87JCr.MsZVE4cDg.svgz" alt="v \neq w" title="v \neq w"></span>.
</p>
<p>
More generally, assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="16" height="12" src="https://math.fontein.de/formulae/El54jcSPwk.2ASHD5GrpJ57pTPCUt4gRfS4OSg.svgz" alt="X" title="X"></span> is a finite set and <span class="inline-formula"><img class="img-inline-formula img-formula" width="91" height="12" src="https://math.fontein.de/formulae/9VQLY61Ypa7eLbaak1A5.kjxUny8f0UWT0ohMw.svgz" alt="\pi : \Z^n \to X" title="\pi : \Z^n \to X"></span> is a map such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="18" src="https://math.fontein.de/formulae/tL4VQMNr..bzwzX0SMTGSuhapmduHfQAonLT1g.svgz" alt="\pi(x + \lambda) = \pi(x)" title="\pi(x + \lambda) = \pi(x)"></span> for all <span class="inline-formula"><img class="img-inline-formula img-formula" width="44" height="13" src="https://math.fontein.de/formulae/A5CppZBos4lcq9WsAE.53BBJujPwtmvA8McOnA.svgz" alt="\lambda \in \Lambda" title="\lambda \in \Lambda"></span>. Our above example, <span class="inline-formula"><img class="img-inline-formula img-formula" width="80" height="18" src="https://math.fontein.de/formulae/LKcp.9b0In9J_51VGq7qa7vdxbPEOrmMtX7ZZw.svgz" alt="G = \Z^n / \Lambda" title="G = \Z^n / \Lambda"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="102" height="18" src="https://math.fontein.de/formulae/8SN_LwFKPOXRUBeIg3.Dl8Qx18bOmLt23ZvERQ.svgz" alt="\pi(x) = x + \Lambda" title="\pi(x) = x + \Lambda"></span> satisfies this. Moreover, assume that <span class="inline-formula"><img class="img-inline-formula img-formula" width="112" height="18" src="https://math.fontein.de/formulae/PEECs8QpoJ29td9SXvL3QiYeFiv4XfVxVcYZRA.svgz" alt="\pi : \Z^n / \Lambda \to X" title="\pi : \Z^n / \Lambda \to X"></span> is “mostly injective”, i.e. that <span class="inline-formula"><img class="img-inline-formula img-formula" width="95" height="18" src="https://math.fontein.de/formulae/ne0FeN0pxxt358Lxau2VPoQqk.pFUoL475xXOg.svgz" alt="\pi(v) = \pi(w)" title="\pi(v) = \pi(w)"></span> implies that one can find <span class="inline-formula"><img class="img-inline-formula img-formula" width="73" height="16" src="https://math.fontein.de/formulae/l2185qe1cZ1gIw186RDc7PsLcgFhIyrqthGBBA.svgz" alt="\tilde{v}, \tilde{w} \in \Z^n" title="\tilde{v}, \tilde{w} \in \Z^n"></span> such that <span class="inline-formula"><img class="img-inline-formula img-formula" width="42" height="12" src="https://math.fontein.de/formulae/u2tLbCTQrRm4VXqoR6uUj2TRuHLalfSuQqJVbQ.svgz" alt="\tilde{v} \approx v" title="\tilde{v} \approx v"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="50" height="12" src="https://math.fontein.de/formulae/IyqmlzElPrDFgd5bz_eWYHZ37wdNWlh.Ubxoxw.svgz" alt="\tilde{w} \approx w" title="\tilde{w} \approx w"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="78" height="14" src="https://math.fontein.de/formulae/qodWAFPWIJ_6s2C8UCSDLZjnXmFsGheDpEPbXQ.svgz" alt="\tilde{v} - \tilde{w} \in \Lambda" title="\tilde{v} - \tilde{w} \in \Lambda"></span> with very little effort. Then one can work with elements <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="18" src="https://math.fontein.de/formulae/p1xOHJn1uc3KaP04NNve3_vm0Zr_NQ5jV8MqiQ.svgz" alt="(x, y)" title="(x, y)"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="68" height="18" src="https://math.fontein.de/formulae/4CgQ3J1JUdDWVsUejg62Oz5Fm66f.DMjXUMiHA.svgz" alt="y = \pi(x)" title="y = \pi(x)"></span>, and try to find two such pairs <span class="inline-formula"><img class="img-inline-formula img-formula" width="41" height="18" src="https://math.fontein.de/formulae/p1xOHJn1uc3KaP04NNve3_vm0Zr_NQ5jV8MqiQ.svgz" alt="(x, y)" title="(x, y)"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="51" height="18" src="https://math.fontein.de/formulae/OIClJFldAlX5mjdhN9PrLiZ7jKwqsFb4ZiaOcg.svgz" alt="(x', y')" title="(x', y')"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="17" src="https://math.fontein.de/formulae/h9ZzWo9YuwuhdSM7AjtArjWdj9oKk5fn._RhLA.svgz" alt="y = y'" title="y = y'"></span>; then this gives rise to an element of <span class="inline-formula"><img class="img-inline-formula img-formula" width="12" height="12" src="https://math.fontein.de/formulae/XY_2LK590TGO0.jb0ZbkmaiBi4kJr1xvp52q2g.svgz" alt="\Lambda" title="\Lambda"></span> near to <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="15" src="https://math.fontein.de/formulae/hVj5WXY2GYlgdxqxUlUwfY0d8qMCgK.CTo3FpQ.svgz" alt="x - x'" title="x - x'"></span>.
</p>
<p>
Which brings us to the subject of explaining algorithms. Consider, for example, Shanks' baby-step giant- step algorithm. You are given a group element of finite order <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/UxCAbnAvo.LhIVRUfLjfwIlPAfhwrVfYLg_Adw.svgz" alt="g" title="g"></span> together with a bound <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="13" src="https://math.fontein.de/formulae/li9mtsMMu1gXBZNPKxdQihJTsK9xXNjJjvX1xQ.svgz" alt="B > 0" title="B > 0"></span>. Then, for the algorithm, one computes <span class="inline-formula"><img class="img-inline-formula img-formula" width="121" height="18" src="https://math.fontein.de/formulae/wPqzh3ErZ9m4MlycLO0Mw1kqset5pAohBF5SKw.svgz" alt="g^0, g^1, \dots, g^{B-1}" title="g^0, g^1, \dots, g^{B-1}"></span>, as well as <span class="inline-formula"><img class="img-inline-formula img-formula" width="122" height="18" src="https://math.fontein.de/formulae/0fNiMvfApXlqcXKPI84agpJrJEVbvPMYQGUPrA.svgz" alt="g^B, g^{2 B}, g^{3 B}, \dots" title="g^B, g^{2 B}, g^{3 B}, \dots"></span>, and compares this elements with the first <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/Ih7V6Mp4twAjwq7Tr86Dt9U5c5VQJd0XWRPlqw.svgz" alt="B" title="B"></span> elements. Any match will result in a multiple of the order of <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/UxCAbnAvo.LhIVRUfLjfwIlPAfhwrVfYLg_Adw.svgz" alt="g" title="g"></span>. But why is this the case? One can of course try to prove this; it is actually not very hard, in fact one just needs <a href="https://en.wikipedia.org/wiki/Fermat%27s_little_theorem">Fermat's Little Theorem</a> as well as <a href="https://en.wikipedia.org/wiki/Long_division">long division</a>. But one can do better, by visualizing the algorithm in a way which makes the solution looking obvious, and which allows even people who have no understanding of formal mathematics or computer science to immediately realize that the algorithm produces the correct result.
</p>
<p>
Namely, you might have guessed it, the order of <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/UxCAbnAvo.LhIVRUfLjfwIlPAfhwrVfYLg_Adw.svgz" alt="g" title="g"></span> generates the relation lattice <span class="inline-formula"><img class="img-inline-formula img-formula" width="32" height="18" src="https://math.fontein.de/formulae/6nXiTCUdwp1N80Ges9V0hRNeRtGWBRWxsBj3gg.svgz" alt="\Lambda_{(g)}" title="\Lambda_{(g)}"></span>. Hence finding the order is equivalent to finding a the smallest positive element in <span class="inline-formula"><img class="img-inline-formula img-formula" width="67" height="18" src="https://math.fontein.de/formulae/zpIslr9j9DdGhdPysZtUjkiHNg0Azc3u7Hko4Q.svgz" alt="\Lambda_{(g)} \subseteq \Z" title="\Lambda_{(g)} \subseteq \Z"></span>. For this correspondence, we use the pairs <span class="inline-formula"><img class="img-inline-formula img-formula" width="51" height="18" src="https://math.fontein.de/formulae/TV5CRkveOnUhtm4UcfYNkOOPkDDLiTzb78NxCw.svgz" alt="(n, g^n)" title="(n, g^n)"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="44" height="13" src="https://math.fontein.de/formulae/XpBPwowNNTbUIL5g3SqKnKd1BnfcrcAa2nmWmg.svgz" alt="n \in \Z" title="n \in \Z"></span> as above. Two pairs <span class="inline-formula"><img class="img-inline-formula img-formula" width="119" height="18" src="https://math.fontein.de/formulae/7JPc_DKhQJElodQcmCdmvRrUjyEq4lqshGFNsw.svgz" alt="(n, g^n), (m, g^m)" title="(n, g^n), (m, g^m)"></span> with <span class="inline-formula"><img class="img-inline-formula img-formula" width="65" height="15" src="https://math.fontein.de/formulae/YiYchIXzF4LYjphOMb1DsKaqS67SN4DOLkjvDA.svgz" alt="g^n = g^m" title="g^n = g^m"></span> gives a multiple <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="12" src="https://math.fontein.de/formulae/hTKM8_SeRLcMk0GF6R.p6shqxF2_f_njchF5Dw.svgz" alt="n - m" title="n - m"></span> of the order of <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/UxCAbnAvo.LhIVRUfLjfwIlPAfhwrVfYLg_Adw.svgz" alt="g" title="g"></span>. Now, the algorithm can be interpreted as translating the set of elements <span class="inline-formula"><img class="img-inline-formula img-formula" width="307" height="18" src="https://math.fontein.de/formulae/Kmy3H.yRtjZHcXg_XLT76oFIRaw8vPP4o18znQ.svgz" alt="X_B := \{ -B+1, -B+2, \dots, -2, -1, 0 \}" title="X_B := \{ -B+1, -B+2, \dots, -2, -1, 0 \}"></span> by <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/Ih7V6Mp4twAjwq7Tr86Dt9U5c5VQJd0XWRPlqw.svgz" alt="B" title="B"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="23" height="12" src="https://math.fontein.de/formulae/ulqwWBONYZ7cOp8Dtdy_DLtAhVcPH0bhPavoAg.svgz" alt="2 B" title="2 B"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="23" height="12" src="https://math.fontein.de/formulae/NPpDmxvfhddPCLEIAFv08AZUsZ3fwncXDovAsg.svgz" alt="3 B" title="3 B"></span>, and checking if a lattice element is contained in any of these translates. If one visualizes this, one immediately sees that this method will eventually find the smallest non-zero element of the lattice. First, this depicts the lattice <span class="inline-formula"><img class="img-inline-formula img-formula" width="12" height="12" src="https://math.fontein.de/formulae/wHyKSgMZTFrtdvMomD9SLs8Z27XS7B.vR28n6w.svgz" alt="\Z" title="\Z"></span> (gray dots) with its sublattice <span class="inline-formula"><img class="img-inline-formula img-formula" width="32" height="18" src="https://math.fontein.de/formulae/6nXiTCUdwp1N80Ges9V0hRNeRtGWBRWxsBj3gg.svgz" alt="\Lambda_{(g)}" title="\Lambda_{(g)}"></span> (black dots), with the set <span class="inline-formula"><img class="img-inline-formula img-formula" width="175" height="18" src="https://math.fontein.de/formulae/iTUVYKXquRneyDIuWVe_8sXks0w.yLmu2wKr_w.svgz" alt="X_B = \{ -B+1, \dots, 0 \}" title="X_B = \{ -B+1, \dots, 0 \}"></span> drawn in for <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="12" src="https://math.fontein.de/formulae/K1jDVQeDaZObVXgXcXM64oVEwI2Xd_BmFWq9gg.svgz" alt="B = 8" title="B = 8"></span>:
</p>
<div class="center-block">
<p>
<span class="tikz-formula"><img class="img-(" tikzpicture node distance="0mm')-formula" img-formula width="585" height="39" src="https://math.fontein.de/formulae/tEfQxddCWWI8ASH70W4ZAFeYtXxUlWvWv75eVQ.svgz" alt="\tikzstyle{gelt} = [draw, shape = circle, fill=black, inner sep=0pt, minimum size = 0.2cm];
\tikzstyle{empt} = [draw, shape = circle, inner sep=0pt, minimum size = 0.2cm];
\filldraw[black!67, fill=black!20] (-7.4,-0.4) to (-7.4,0.4) to (0.4,0.4) to (0.4,-0.4) to (-7.4,-0.4);
\draw (-5,0) to (-5,-0.75);
\node[empt] (gm5) at (-5,0) [label=below: \footnotesize \( g^{-5} \)] {};
\draw (0,0) to (0,-0.75);
\node[gelt] (g0) at (0,0) [label=below: \footnotesize \( g^0 \)] {};
\draw (5,0) to (5,-0.75);
\node[empt] (g5) at (5,0) [label=below: \footnotesize \( g^5 \)] {};
\draw (10,0) to (10,-0.75);
\node[empt] (g10) at (10,0) [label=below: \footnotesize \( g^{10} \)] {};
\draw (23,0) to (23,-0.75);
\node[gelt] (g23) at (23,0) [label=below: \footnotesize \( g^{23} \)] {};
\foreach \i in {-9,-8,-7,-6,-4,-3,-2,-1} \node[empt] at (\i,0) {};
\foreach \i in {1,2,3,4,6,7,8,9,11,12,13,14,15,16,17,18,19,20,21,22} \node[empt] at (\i,0) {};
\foreach \i in {24,25,26,27,28,29} \node[empt] at (\i,0) {};" title="\tikzstyle{gelt} = [draw, shape = circle, fill=black, inner sep=0pt, minimum size = 0.2cm];
\tikzstyle{empt} = [draw, shape = circle, inner sep=0pt, minimum size = 0.2cm];
\filldraw[black!67, fill=black!20] (-7.4,-0.4) to (-7.4,0.4) to (0.4,0.4) to (0.4,-0.4) to (-7.4,-0.4);
\draw (-5,0) to (-5,-0.75);
\node[empt] (gm5) at (-5,0) [label=below: \footnotesize \( g^{-5} \)] {};
\draw (0,0) to (0,-0.75);
\node[gelt] (g0) at (0,0) [label=below: \footnotesize \( g^0 \)] {};
\draw (5,0) to (5,-0.75);
\node[empt] (g5) at (5,0) [label=below: \footnotesize \( g^5 \)] {};
\draw (10,0) to (10,-0.75);
\node[empt] (g10) at (10,0) [label=below: \footnotesize \( g^{10} \)] {};
\draw (23,0) to (23,-0.75);
\node[gelt] (g23) at (23,0) [label=below: \footnotesize \( g^{23} \)] {};
\foreach \i in {-9,-8,-7,-6,-4,-3,-2,-1} \node[empt] at (\i,0) {};
\foreach \i in {1,2,3,4,6,7,8,9,11,12,13,14,15,16,17,18,19,20,21,22} \node[empt] at (\i,0) {};
\foreach \i in {24,25,26,27,28,29} \node[empt] at (\i,0) {};"></span>
</p>
</div>
<p>
The next figure depicts the translates of <span class="inline-formula"><img class="img-inline-formula img-formula" width="27" height="15" src="https://math.fontein.de/formulae/R_a65PqeC5xW7z8KTXg0v_xbSCpOHycBY9ATqQ.svgz" alt="X_B" title="X_B"></span> by <span class="inline-formula"><img class="img-inline-formula img-formula" width="105" height="16" src="https://math.fontein.de/formulae/z8kKDk5PbUj2fhpm7Yi1HsSSNY5pYT4R0qQinQ.svgz" alt="B, 2 B, 3 B, \dots" title="B, 2 B, 3 B, \dots"></span>:
</p>
<div class="center-block">
<p>
<span class="tikz-formula"><img class="img-(" tikzpicture node distance="0mm')-formula" img-formula width="586" height="39" src="https://math.fontein.de/formulae/pVjjMxOfq.35GhNwImjBKVdpDrH3DHf0kJaaEg.svgz" alt="\tikzstyle{gelt} = [draw, shape = circle, fill=black, inner sep=0pt, minimum size = 0.2cm];
\tikzstyle{empt} = [draw, shape = circle, inner sep=0pt, minimum size = 0.2cm];
\filldraw[black!67, fill=black!20] (0.6,-0.4) to (0.6,0.4) to (8.4,0.4) to (8.4,-0.4) to (0.6,-0.4);
\filldraw[black!67, fill=black!20] (8.6,-0.4) to (8.6,0.4) to (16.4,0.4) to (16.4,-0.4) to (8.6,-0.4);
\filldraw[black!67, fill=black!20] (16.6,-0.4) to (16.6,0.4) to (24.4,0.4) to (24.4,-0.4) to (16.6,-0.4);
\filldraw[black!67, fill=black!20] (29.4,-0.4) to (24.6,-0.4) to (24.6,0.4) to (29.4,0.4);
\draw (-5,0) to (-5,-0.75);
\node[empt] (gm5) at (-5,0) [label=below: \footnotesize \( g^{-5} \)] {};
\draw (0,0) to (0,-0.75);
\node[gelt] (g0) at (0,0) [label=below: \footnotesize \( g^0 \)] {};
\draw (5,0) to (5,-0.75);
\node[empt] (g5) at (5,0) [label=below: \footnotesize \( g^5 \)] {};
\draw (10,0) to (10,-0.75);
\node[empt] (g10) at (10,0) [label=below: \footnotesize \( g^{10} \)] {};
\draw (23,0) to (23,-0.75);
\node[gelt] (g23) at (23,0) [label=below: \footnotesize \( g^{23} \)] {};
\foreach \i in {-9,-8,-7,-6,-4,-3,-2,-1} \node[empt] at (\i,0) {};
\foreach \i in {1,2,3,4,6,7,8,9,11,12,13,14,15,16,17,18,19,20,21,22} \node[empt] at (\i,0) {};
\foreach \i in {24,25,26,27,28,29} \node[empt] at (\i,0) {};" title="\tikzstyle{gelt} = [draw, shape = circle, fill=black, inner sep=0pt, minimum size = 0.2cm];
\tikzstyle{empt} = [draw, shape = circle, inner sep=0pt, minimum size = 0.2cm];
\filldraw[black!67, fill=black!20] (0.6,-0.4) to (0.6,0.4) to (8.4,0.4) to (8.4,-0.4) to (0.6,-0.4);
\filldraw[black!67, fill=black!20] (8.6,-0.4) to (8.6,0.4) to (16.4,0.4) to (16.4,-0.4) to (8.6,-0.4);
\filldraw[black!67, fill=black!20] (16.6,-0.4) to (16.6,0.4) to (24.4,0.4) to (24.4,-0.4) to (16.6,-0.4);
\filldraw[black!67, fill=black!20] (29.4,-0.4) to (24.6,-0.4) to (24.6,0.4) to (29.4,0.4);
\draw (-5,0) to (-5,-0.75);
\node[empt] (gm5) at (-5,0) [label=below: \footnotesize \( g^{-5} \)] {};
\draw (0,0) to (0,-0.75);
\node[gelt] (g0) at (0,0) [label=below: \footnotesize \( g^0 \)] {};
\draw (5,0) to (5,-0.75);
\node[empt] (g5) at (5,0) [label=below: \footnotesize \( g^5 \)] {};
\draw (10,0) to (10,-0.75);
\node[empt] (g10) at (10,0) [label=below: \footnotesize \( g^{10} \)] {};
\draw (23,0) to (23,-0.75);
\node[gelt] (g23) at (23,0) [label=below: \footnotesize \( g^{23} \)] {};
\foreach \i in {-9,-8,-7,-6,-4,-3,-2,-1} \node[empt] at (\i,0) {};
\foreach \i in {1,2,3,4,6,7,8,9,11,12,13,14,15,16,17,18,19,20,21,22} \node[empt] at (\i,0) {};
\foreach \i in {24,25,26,27,28,29} \node[empt] at (\i,0) {};"></span>
</p>
</div>
<p>
One directly sees that the translates <span class="inline-formula"><img class="img-inline-formula img-formula" width="73" height="15" src="https://math.fontein.de/formulae/SY7mnZUyyi3z4dJmWtLRHgNHsAMa_5bMqUUloA.svgz" alt="X_B + k B" title="X_B + k B"></span>, <span class="inline-formula"><img class="img-inline-formula img-formula" width="63" height="16" src="https://math.fontein.de/formulae/Gg05XbwS0EMxbCuD3ePE.QuuvsuIREnr.Ode9A.svgz" alt="k \in \N_{>0}" title="k \in \N_{>0}"></span> cover all positive integers, and that every positive integer is contained in exactly one translate. Moreover, one sees that if the first translate contains at most one lattice element, the first translate which contains a lattice element uniquely determines the smallest positive integer. Note that in case <span class="inline-formula"><img class="img-inline-formula img-formula" width="11" height="8" src="https://math.fontein.de/formulae/CiIJDoNXXhwwshmAknaOy.cbqWs.Z_qmDZe21A.svgz" alt="n" title="n"></span> is the order of <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/UxCAbnAvo.LhIVRUfLjfwIlPAfhwrVfYLg_Adw.svgz" alt="g" title="g"></span>, then one can minimize the number of operations by chosing <span class="inline-formula"><img class="img-inline-formula img-formula" width="63" height="18" src="https://math.fontein.de/formulae/H6nwZLUuP2msHlc_GwS3Rcs4pV2po93dBBSM2Q.svgz" alt="B \approx \sqrt{n}" title="B \approx \sqrt{n}"></span>.
</p>
<p>
Now let us consider <a href="http://portal.acm.org/citation.cfm%3Fid%3D343671">Terr's modification</a> of the baby-step giant-step algorithm; there, the situation is a bit more complicated. In Terr's algorithm, the bound <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/Ih7V6Mp4twAjwq7Tr86Dt9U5c5VQJd0XWRPlqw.svgz" alt="B" title="B"></span> from above constantly changes, starting with <span class="inline-formula"><img class="img-inline-formula img-formula" width="47" height="12" src="https://math.fontein.de/formulae/fmDmak5tIHKXqpy6gUcw5vN3gtDCGfOfT_dRVw.svgz" alt="B = 1" title="B = 1"></span>. Written as pseudo-code, the algorithm looks like this:
</p>
<ol class="enum-level-1">
<li>Let <span class="inline-formula"><img class="img-inline-formula img-formula" width="55" height="18" src="https://math.fontein.de/formulae/WKuI73oAUgjwR_L3kANK.FkT98ML_kDDQM3tuQ.svgz" alt="a := g^1" title="a := g^1"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="53" height="18" src="https://math.fontein.de/formulae/kN02zUIObhwbyeWq._EQer4Wia6nMWL7hZfoaQ.svgz" alt="b := g^1" title="b := g^1"></span>, and let <span class="inline-formula"><img class="img-inline-formula img-formula" width="52" height="12" src="https://math.fontein.de/formulae/JWl4Mz2jALsRayL7doW1yAUkcWbyGRtHCYfIHg.svgz" alt="B := 1" title="B := 1"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="121" height="19" src="https://math.fontein.de/formulae/KZyfai0WA1NplBiS_VUvpYdxKzPsGd9JMklbCw.svgz" alt="X_B := \{ (g^0, 0) \}" title="X_B := \{ (g^0, 0) \}"></span>.</li>
<li>If <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/n7XIXF4cgetyUjZrjGKpnj50AyqcEZQR7MPGCg.svgz" alt="(b, n) \in X_B" title="(b, n) \in X_B"></span> for some <span class="inline-formula"><img class="img-inline-formula img-formula" width="45" height="13" src="https://math.fontein.de/formulae/UeChwhh6h7Bw5vi122OTLvfxRX.k6iU0MpIILg.svgz" alt="n \in \N" title="n \in \N"></span>, return <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="24" src="https://math.fontein.de/formulae/V3Ic5DSVncwBG7P9a4.nY66YelDDNlY6pgVvxw.svgz" alt="\frac{B (B + 1)}{2} - n" title="\frac{B (B + 1)}{2} - n"></span>.</li>
<li>Set <span class="inline-formula"><img class="img-inline-formula img-formula" width="165" height="18" src="https://math.fontein.de/formulae/WogDnIjvx2hLj0u1DJkAQCOPTonifBoWOFAs4g.svgz" alt="X_B := X_B \cup \{ (a, B) \}" title="X_B := X_B \cup \{ (a, B) \}"></span>, and set <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="14" src="https://math.fontein.de/formulae/U.jYSRkkyy1bnGooBLJC1zprDKDql89DSNJtSw.svgz" alt="B := B + 1" title="B := B + 1"></span>.</li>
<li>Compute <span class="inline-formula"><img class="img-inline-formula img-formula" width="69" height="11" src="https://math.fontein.de/formulae/1Boi8CmNk4BXStJcQl37AOemmSPimnjUjby.FQ.svgz" alt="a := a \cdot g" title="a := a \cdot g"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="66" height="12" src="https://math.fontein.de/formulae/EieIWN6_JPMwh5rNJzV2DPGH2FuYICLqJTV71Q.svgz" alt="b := b \cdot a" title="b := b \cdot a"></span>.</li>
<li>Go back to Step 2.</li>
</ol>
<p>
There is no obvious reason why this should work. Note that the test whether <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/n7XIXF4cgetyUjZrjGKpnj50AyqcEZQR7MPGCg.svgz" alt="(b, n) \in X_B" title="(b, n) \in X_B"></span> means that one translates <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="18" src="https://math.fontein.de/formulae/wJkTH3yYbvj4zrm4xjhKoqz8TqLp8S4r0RCX.w.svgz" alt="\{ -B + 1, \dots, 0 \}" title="\{ -B + 1, \dots, 0 \}"></span> by the exponent <span class="inline-formula"><img class="img-inline-formula img-formula" width="8" height="8" src="https://math.fontein.de/formulae/ezGhcedUyemgOYRIiV2KoCZA0AXombpWKjnqTA.svgz" alt="c" title="c"></span> of <span class="inline-formula"><img class="img-inline-formula img-formula" width="48" height="16" src="https://math.fontein.de/formulae/SrxqUM2.28sO_S9Brn7z7aXa49CvO8yEPDc1og.svgz" alt="b = g^c" title="b = g^c"></span>, which turns out to be <span class="inline-formula"><img class="img-inline-formula img-formula" width="56" height="24" src="https://math.fontein.de/formulae/ohjNJP5097UCC5JB4fppvavk9SXViTaikefzbw.svgz" alt="\frac{B (B + 1)}{2}" title="\frac{B (B + 1)}{2}"></span>. One immediately gets the idea if one draws the first few translates:
</p>
<div class="center-block">
<p>
<span class="tikz-formula"><img class="img-(" tikzpicture node distance="0mm')-formula" img-formula width="586" height="39" src="https://math.fontein.de/formulae/p_lilbOm.iIcaceY4YGCExkgkGueihqENjB9vg.svgz" alt="\tikzstyle{gelt} = [draw, shape = circle, fill=black, inner sep=0pt, minimum size = 0.2cm];
\tikzstyle{empt} = [draw, shape = circle, inner sep=0pt, minimum size = 0.2cm];
\filldraw[black!67, fill=black!20] (0.6,-0.4) to (0.6,0.4) to (1.4,0.4) to (1.4,-0.4) to (0.6,-0.4);
\filldraw[black!67, fill=black!20] (1.6,-0.4) to (1.6,0.4) to (3.4,0.4) to (3.4,-0.4) to (1.6,-0.4);
\filldraw[black!67, fill=black!20] (3.6,-0.4) to (3.6,0.4) to (6.4,0.4) to (6.4,-0.4) to (3.6,-0.4);
\filldraw[black!67, fill=black!20] (6.6,-0.4) to (6.6,0.4) to (10.4,0.4) to (10.4,-0.4) to (6.6,-0.4);
\filldraw[black!67, fill=black!20] (10.6,-0.4) to (10.6,0.4) to (15.4,0.4) to (15.4,-0.4) to (10.6,-0.4);
\filldraw[black!67, fill=black!20] (15.6,-0.4) to (15.6,0.4) to (21.4,0.4) to (21.4,-0.4) to (15.6,-0.4);
\filldraw[black!67, fill=black!20] (21.6,-0.4) to (21.6,0.4) to (28.4,0.4) to (28.4,-0.4) to (21.6,-0.4);
\filldraw[black!67, fill=black!20] (29.4,-0.4) to (28.6,-0.4) to (28.6,0.4) to (29.4,0.4);
\draw (-5,0) to (-5,-0.75);
\node[empt] (gm5) at (-5,0) [label=below: \footnotesize \( g^{-5} \)] {};
\draw (0,0) to (0,-0.75);
\node[gelt] (g0) at (0,0) [label=below: \footnotesize \( g^0 \)] {};
\draw (5,0) to (5,-0.75);
\node[empt] (g5) at (5,0) [label=below: \footnotesize \( g^5 \)] {};
\draw (10,0) to (10,-0.75);
\node[empt] (g10) at (10,0) [label=below: \footnotesize \( g^{10} \)] {};
\draw (23,0) to (23,-0.75);
\node[gelt] (g23) at (23,0) [label=below: \footnotesize \( g^{23} \)] {};
\foreach \i in {-9,-8,-7,-6,-4,-3,-2,-1} \node[empt] at (\i,0) {};
\foreach \i in {1,2,3,4,6,7,8,9,11,12,13,14,15,16,17,18,19,20,21,22} \node[empt] at (\i,0) {};
\foreach \i in {24,25,26,27,28,29} \node[empt] at (\i,0) {};" title="\tikzstyle{gelt} = [draw, shape = circle, fill=black, inner sep=0pt, minimum size = 0.2cm];
\tikzstyle{empt} = [draw, shape = circle, inner sep=0pt, minimum size = 0.2cm];
\filldraw[black!67, fill=black!20] (0.6,-0.4) to (0.6,0.4) to (1.4,0.4) to (1.4,-0.4) to (0.6,-0.4);
\filldraw[black!67, fill=black!20] (1.6,-0.4) to (1.6,0.4) to (3.4,0.4) to (3.4,-0.4) to (1.6,-0.4);
\filldraw[black!67, fill=black!20] (3.6,-0.4) to (3.6,0.4) to (6.4,0.4) to (6.4,-0.4) to (3.6,-0.4);
\filldraw[black!67, fill=black!20] (6.6,-0.4) to (6.6,0.4) to (10.4,0.4) to (10.4,-0.4) to (6.6,-0.4);
\filldraw[black!67, fill=black!20] (10.6,-0.4) to (10.6,0.4) to (15.4,0.4) to (15.4,-0.4) to (10.6,-0.4);
\filldraw[black!67, fill=black!20] (15.6,-0.4) to (15.6,0.4) to (21.4,0.4) to (21.4,-0.4) to (15.6,-0.4);
\filldraw[black!67, fill=black!20] (21.6,-0.4) to (21.6,0.4) to (28.4,0.4) to (28.4,-0.4) to (21.6,-0.4);
\filldraw[black!67, fill=black!20] (29.4,-0.4) to (28.6,-0.4) to (28.6,0.4) to (29.4,0.4);
\draw (-5,0) to (-5,-0.75);
\node[empt] (gm5) at (-5,0) [label=below: \footnotesize \( g^{-5} \)] {};
\draw (0,0) to (0,-0.75);
\node[gelt] (g0) at (0,0) [label=below: \footnotesize \( g^0 \)] {};
\draw (5,0) to (5,-0.75);
\node[empt] (g5) at (5,0) [label=below: \footnotesize \( g^5 \)] {};
\draw (10,0) to (10,-0.75);
\node[empt] (g10) at (10,0) [label=below: \footnotesize \( g^{10} \)] {};
\draw (23,0) to (23,-0.75);
\node[gelt] (g23) at (23,0) [label=below: \footnotesize \( g^{23} \)] {};
\foreach \i in {-9,-8,-7,-6,-4,-3,-2,-1} \node[empt] at (\i,0) {};
\foreach \i in {1,2,3,4,6,7,8,9,11,12,13,14,15,16,17,18,19,20,21,22} \node[empt] at (\i,0) {};
\foreach \i in {24,25,26,27,28,29} \node[empt] at (\i,0) {};"></span>
</p>
</div>
<p>
This is another tiling of <span class="inline-formula"><img class="img-inline-formula img-formula" width="32" height="16" src="https://math.fontein.de/formulae/H9YHoJrixkDwPHR84D5L3klWYofEkkCHEMC_og.svgz" alt="\N_{>0}" title="\N_{>0}"></span>, where every positive integer is contained in exactly one translate. This tiling has the property that the first time <span class="inline-formula"><img class="img-inline-formula img-formula" width="88" height="18" src="https://math.fontein.de/formulae/n7XIXF4cgetyUjZrjGKpnj50AyqcEZQR7MPGCg.svgz" alt="(b, n) \in X_B" title="(b, n) \in X_B"></span> occurs for some <span class="inline-formula"><img class="img-inline-formula img-formula" width="45" height="13" src="https://math.fontein.de/formulae/UeChwhh6h7Bw5vi122OTLvfxRX.k6iU0MpIILg.svgz" alt="n \in \N" title="n \in \N"></span> is when the order of <span class="inline-formula"><img class="img-inline-formula img-formula" width="9" height="11" src="https://math.fontein.de/formulae/UxCAbnAvo.LhIVRUfLjfwIlPAfhwrVfYLg_Adw.svgz" alt="g" title="g"></span> is found, and one no longer has to fix a bound <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/Ih7V6Mp4twAjwq7Tr86Dt9U5c5VQJd0XWRPlqw.svgz" alt="B" title="B"></span> before. The asymptotic complexity of this method is the same as the previous method in case <span class="inline-formula"><img class="img-inline-formula img-formula" width="63" height="18" src="https://math.fontein.de/formulae/H6nwZLUuP2msHlc_GwS3Rcs4pV2po93dBBSM2Q.svgz" alt="B \approx \sqrt{n}" title="B \approx \sqrt{n}"></span>, but in case <span class="inline-formula"><img class="img-inline-formula img-formula" width="14" height="12" src="https://math.fontein.de/formulae/Ih7V6Mp4twAjwq7Tr86Dt9U5c5VQJd0XWRPlqw.svgz" alt="B" title="B"></span> is chosen the wrong way, the first algorithm will perform worse than the second. Another way to visualize the second agorithm is to depict the set <span class="inline-formula"><img class="img-inline-formula img-formula" width="125" height="18" src="https://math.fontein.de/formulae/.z2etceKQUnRbbaOm.OkFwcQX9k35hAIJ9ZJng.svgz" alt="\{ -B+1, \dots, 0 \}" title="\{ -B+1, \dots, 0 \}"></span> together with <span class="inline-formula"><img class="img-inline-formula img-formula" width="56" height="24" src="https://math.fontein.de/formulae/ohjNJP5097UCC5JB4fppvavk9SXViTaikefzbw.svgz" alt="\frac{B (B + 1)}{2}" title="\frac{B (B + 1)}{2}"></span>, where <span class="inline-formula"><img class="img-inline-formula img-formula" width="54" height="18" src="https://math.fontein.de/formulae/IoawfvOfhu8ZEAa1LVl270IM5mwq8GJbywWSKg.svgz" alt="a = g^B" title="a = g^B"></span> and <span class="inline-formula"><img class="img-inline-formula img-formula" width="107" height="19" src="https://math.fontein.de/formulae/1C3b_lz9nlu.vm.3ZBrZxU_KZO0UgFPu8MS_FQ.svgz" alt="b = g^{B (B + 1)/2}" title="b = g^{B (B + 1)/2}"></span>, for <span class="inline-formula"><img class="img-inline-formula img-formula" width="112" height="16" src="https://math.fontein.de/formulae/PwG1Trxzd_Slu04OgrSbysioX2VUfMYEHYHyww.svgz" alt="B = 1, 2, \dots, 7" title="B = 1, 2, \dots, 7"></span>:
</p>
<div class="center-block">
<p>
<span class="tikz-formula"><img class="img-(" tikzpicture node distance="0mm')-formula" img-formula width="585" height="104" src="https://math.fontein.de/formulae/eeLjB9E7_vLsKfgJ2xlcXQTAWbCue.xXHHwDVA.svgz" alt="\tikzstyle{gelt} = [draw, shape = circle, fill=black, inner sep=0pt, minimum size = 0.2cm];
\tikzstyle{empt} = [draw, shape = circle, inner sep=0pt, minimum size = 0.2cm];
\foreach \B in { 1, 2, 3, 4, 5, 6, 7 }
{
\filldraw[black!20, fill=black!67] (-\B+0.6,-\B-0.4) to (-\B+0.6,-\B+0.4) to (0.4,-\B+0.4) to (0.4,-\B-0.4) to (-\B+0.6,-\B-0.4);
\filldraw[black!67, fill=black!20] (\B*\B/2-\B/2+0.6,-\B-0.4) to (\B*\B/2-\B/2+0.6,-\B+0.4) to (\B*\B/2+\B/2+0.4,-\B+0.4)
to (\B*\B/2+\B/2+0.4,-\B-0.4) to (\B*\B/2-\B/2+0.6,-\B-0.4);
\filldraw[black!20, fill=black!67] (\B*\B/2+\B/2-0.4,-\B-0.4) to (\B*\B/2+\B/2-0.4,-\B+0.4) to (\B*\B/2+\B/2+0.4,-\B+0.4)
to (\B*\B/2+\B/2+0.4,-\B-0.4) to (\B*\B/2+\B/2-0.4,-\B-0.4);
\foreach \i in {-9,-8,-7,-6,-5,-4,-3,-2,-1} \node[empt] at (\i,-\B) {};
\node[gelt] at (0,-\B) {};
\foreach \i in {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22} \node[empt] at (\i,-\B) {};
\node[gelt] at (23,-\B) {};
\foreach \i in {24,25,26,27,28,29} \node[empt] at (\i,-\B) {};
}" title="\tikzstyle{gelt} = [draw, shape = circle, fill=black, inner sep=0pt, minimum size = 0.2cm];
\tikzstyle{empt} = [draw, shape = circle, inner sep=0pt, minimum size = 0.2cm];
\foreach \B in { 1, 2, 3, 4, 5, 6, 7 }
{
\filldraw[black!20, fill=black!67] (-\B+0.6,-\B-0.4) to (-\B+0.6,-\B+0.4) to (0.4,-\B+0.4) to (0.4,-\B-0.4) to (-\B+0.6,-\B-0.4);
\filldraw[black!67, fill=black!20] (\B*\B/2-\B/2+0.6,-\B-0.4) to (\B*\B/2-\B/2+0.6,-\B+0.4) to (\B*\B/2+\B/2+0.4,-\B+0.4)
to (\B*\B/2+\B/2+0.4,-\B-0.4) to (\B*\B/2-\B/2+0.6,-\B-0.4);
\filldraw[black!20, fill=black!67] (\B*\B/2+\B/2-0.4,-\B-0.4) to (\B*\B/2+\B/2-0.4,-\B+0.4) to (\B*\B/2+\B/2+0.4,-\B+0.4)
to (\B*\B/2+\B/2+0.4,-\B-0.4) to (\B*\B/2+\B/2-0.4,-\B-0.4);
\foreach \i in {-9,-8,-7,-6,-5,-4,-3,-2,-1} \node[empt] at (\i,-\B) {};
\node[gelt] at (0,-\B) {};
\foreach \i in {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22} \node[empt] at (\i,-\B) {};
\node[gelt] at (23,-\B) {};
\foreach \i in {24,25,26,27,28,29} \node[empt] at (\i,-\B) {};
}"></span>
</p>
</div>
</div>