Fast constant-time GCD algorithm and modular inversion
It&#x27;s pretty frustrating to see the discussion on this submission dominated by people litigating the &quot;constant time&quot; terminology. The authors, Bernstein and Yang, are using constant time in the conventional, complexity theoretic sense of the word. Here is a quote from Section 2, &quot;Organization of this paper&quot;:<p><i>&gt; We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Section 4, states our main algorithm to compute c coefficients of the nth iterate of divstep. This takes n(c + n) simple operations. We also explain how “jumps” reduce the cost for large n to (c + n)(log cn)^2+o(1) operations. All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c).</i><p>In particular note that last sentence. The asymptotic runtime of the presented algorithm does not depend on the inputs, <i>n</i> and <i>c</i>. This algorithm analysis is confirmed throughout the remainder of the paper, which walks through each stage of the algorithm. Now let&#x27;s look at a few canonical definitions of &quot;constant time&quot;, i.e. O(1).<p>From Skiena, we have:<p><i>Constant functions - f(n) = 1 - Such functions might measure the cost of adding two numbers, printing out the &quot;Star Spangled Banner&quot;, or the growth realized by functions such as f(n) = min(n, 100). In the big picture, there is no dependence on the parameter n.</i><p>Likewise from Sedgewick &amp; Wayne:<p><i>Constant. A program whose running time&#x27;s order of growth is constant executes a fixed number of operations to finish its job; consequently its running time does not depend on N. Most Java operations take constant time.</i><p>I&#x27;ll update if I find a choice example from Knuth in TAOCP, but I think this suffices. The discussion about whether or not the cryptographic use of the term satisfies the complexity theoretic sense of the term is a red herring; it&#x27;s a distinction without a difference. Algorithm analysis focuses on asymptotic behavior, which is definitionally given by tail behavior, or rate of growth of a function. Among other things, this paper is <i>not</i> about an implementation methodology that ensures the GCD algorithm will take exactly the same amount of time regardless of the input.<p>______________________<p>1. <i>The Algorithm Design Manual</i>, 2nd Edition, § 2.3.1 Dominance Relations, Page 39<p>2. <i>Algorithms</i>, 4th Edition, § 1.4 Analysis of Algorithms, Page 187