Fast constant-time GCD algorithm and modular inversion
gcd.cr.yp.to
gcd.cr.yp.to
To illustrate the kind of thing it's talking about, consider the naive algorithm for computing a^n via exponentiation by squaring:
total = 1
while n > 0:
if n is odd:
total = total*a
n = n-1
a = a*a
n = n/2
return total
Consider this alternative:
total = 1
while n > 0:
maybe_total = total * a
if n is odd:
total = maybe_total
a = a * a
n = n >> 1
return total
# if n is odd:
# total = maybe_total
# becomes this:
low_bit = n & 1 # i.e. 0 or 1 if n is odd or even
mask = low_bit - 1 # i.e. "all 1s" or 0 respectively
total = (total & mask) | (maybe_total & ~mask)Obtuse, perhaps, but neologism?
http://etymology.enacademic.com/20730/isochronous meaning "equal time" dating back to the early 1700s.
Harsh but not entirely unfair (it is, after all, how language evolves.) Although I'd counter that "isochron" isn't uncommon in travel-related situations (cf [1]) and "isochronous" is easily understandable by extension.
[1] e.g. in the UK parliament, #7927, "the resident population within the Woolwich 20-minute isochron area was about 60,000" https://publications.parliament.uk/pa/cm200607/cmselect/cmcr...
This seems very obvious to me. "Constant" independent of the input size seems literally impossible for any nontrivial algorithm. At the very least you need to somehow read in all the input, and that's already input-size dependent.
A simple example of constant-time within this definition, as well as why constant-time does not mean O(1) in this context, is that of a comparator:
The most normal, and fastest, approach is to go through data in the largest chunks the CPU can handle, returning 1 immediately a mismatch is found, and 0 at the end under the assumption that no termination = no mismatch. However, this reveals information about the values compared, as the time it takes to compare reveals where the mismatch is located.
For constant time, your goal is to ensure that all data is processed equally regardless of outcome. You do this by effectively making the comparison a-b=c, or a^b=c, where a zero-result means equality. In reality, this would be implemented by XOR'ing the largest chunk the CPU can handle together, and then OR'ing the result with a global value starting at 0, overwriting it. This continues without termination to the very end, where you then simply return the running OR'd counter, which is either 0 for equality, or an arbitrary value for the opposite.
Both of course leak the length of the values compared, but the lengths in these cases are commonly known by the adversary, making its protection less relevant.
It doesn't necessarily follow that any algorithm on a arbitrarily-sized input can't run in O(1) - for a trivial example there is an algorithm for "determine if the input number is odd" which is O(1).
I would argue that this particular example cannot be considered a case of arbitrarily-sized input: There is only a single meaningful bit of information, which is the single bit accessed.
However, if you must, we can expand to clarify that the input is meant to include arbitrary meaningful bits of information that require processing and cannot simply be ignored.
If "meaningful" is a non-trivial property, as difficult to determine as an algorithmic lower bound, then it's not terribly useful.
And it also leaves us with no way to talk about non-constant time algorithms for determining whether a number is odd. Can we say one runs in exponential time when we only talk about "meaningful" bits of input?
I do not believe it is tough to find a suitable practical definition of meaningful: If a piece of information has no effect on the output of the algorithm, regardless of its value, then it is not meaningful.
Examples of meaningful values would be any value in a list being sorted. Non-meaningful values would be any other bit than the lowest bit when determining if a number is even or odd.
I find it to be an incredibly trivial definition when considering algorithms.
> If "meaningful" is a non-trivial property, as difficult to determine as an algorithmic lower bound, then it's not terribly useful.
I find the case where the full input is not meaningful to be an outlier that does not at all affect how we normally deal with algorithms and bounds.
However, when the two do not match, one can start discussing what your input actually is. I would, for example, argue that an even/odd number checker only ever takes a single bit as input. It may consume more due to architectural limitations around bit accesses on modern architectures, but that is not part of the core algorithm.
However, I do see your point in that whether a bit flip in input leads to a change in output depends on the particular input. My counter to that is that it is not the specific input, but the potential inputs that matter.
(It also makes the statement "no program can run faster than linear time in the size of the meaningful input" true directly by definition, which makes it a pretty boring statement...)
It is not an input if it does not affect your output (I am sure a better formal definition exists—I usually hear "meaningful", hence my use of that). Without this restriction, any input could be arbitrarily padded, inflating input sizes and making an algorithms complexity appear lower.
I find the even/odd example to be an exceptionally clear case of an algorithm that takes a fixed 1-bit input: Its implementation on a little-endian machine does not know the bounds of its input, only the location of the least significant byte (due to byte-addressing).
Without a defined bound, such an implementation must be assumed to either take a single byte as input (here a byte read is an implementation detail, despite the algorithm only needing one bit), or the full system memory from the location specified as input regardless of contents (due to having used the word "arbitrary", the input is allowed to not fit in registers).
However, I admit that I am now entering deeper theoretical waters with regards to definition details that I am normally comfortable with. I do however not find any other definition to line up with practice.
The point I'm making is that this statement reduces to the claim that defining an algorithm's worst case time complexity as O(1) or constant time is nonsensical.
Do you disagree that adding two numbers is a constant time operation?
It is constant time by crypto programming definition in both theory and practice, and O(1) only in theory (bigints are a pain).
I did not try to claim that O(1) is nonsensical. Rather, that certain O(1) variable-input algorithms are in fact simply fixed input algorithms due to not considering its input.
I also find these "non-sensical" O(1) algorithms to be outliers.
I do. A general algorithm for adding two numbers, at least one represented in the conventional way as a series of digits in some base, has a lower bound of O(log n).
Within cryptography, yes, but in programming in general, absolutely not.
The cryptographic definition of constant-time postdates the algorithmic one by decades, i think. It's a shame the cryptographers didn't pick a different term.
I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time. The reason for that I do not find this possible with classical computers is that no matter what you do, reading data from memory is an unavoidable variable time process.
Do not that arbitrary sized inputs here imply that the input is meaningful and must all be processed. I do not see algorithms that do not process their inputs as candidates here, such as the elsewhere stated example of even/odd test which just read a single bit. I consider an algorithm that only reads a fixed amount of information from its input to be a fixed-input algorithm, regardless of the "full" size of its input.
Of course, if you place an upper bound on the input, then you can pad in various ways, or possibly have algorithms whose execution time is inversely proportional to its input size, thus balancing itself. However, placing an upper bound also mean violating the "arbitrary" requirement entirely, thus disqualifying the algorithm.
Do note that I'd actually be quite interested if you have examples of such algorithms.
With respect, I think you may misunderstand the meaning of "constant time" in the sense of complexity theory, i.e. O(1). Accessing an element in an array of size n is a constant time operation. See: https://stackoverflow.com/questions/7297916/why-does-accessi...
EDIT: Corrected "search" to "access"
TLDR: using optics for sorting
The normal usage of the phrase "constant time" predates CS by centuries, and it is much closer in usage to the crypto version than the complexity version.
Crypto uses the term "constant time" to mean same time for any input, while the general CS community uses O(1) to mean bounded time and also often uses complexity to hide log N terms. It also allows variable time, as long as it's bounded (and that sometimes allows hiding terms like log N or log log N...).
A good example is most algorithms treat addition as a constant time operation, but, for example, addition of indices for lookups is not constant time when inputs are unbounded. So if you compute an index by addition and ignore the logN time to do the addition, then you fudged. Yet this is commonplace in complexity theory, which models many basic operations as constant time when they are not for unbounded inputs.
For example, a "constant time" hash table operation, which often indexes arbitrarily large indices with addition, ignores the log N needed to add arbitrarily large indices.
Thus crypto uses the phrase in the more precise, centuries old usage.
This is incorrect. The paper explicitly uses "constant time" in the sense of O(1). You can see this listed throughout the paper, in various complexity analyses, beginning from Section 2.
How about 'consistent time' or 'uniform time' for non-O(1) uses?
> 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).
What the authors are doing is (in the simplest sense) adding a worst case O(1) component to the GCD algorithm in the exponent. This is fundamentally a complexity theory paper, and Bernstern and Yang are using "constant time" in the complexity theoretic sense.
Moreover this is not about clever implementation; the algorithm they present will explicitly not take the same amount of time regardless of the input. In line with the presented complexity analysis throughout the paper, the worst case running time is asymptotically bounded independently of inputs n and c.
The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies.
The nice properties they claim for their algorithm are:
1. The asymptotic running time is good. This is a complexity-theoretic claim. The asymptotic performance is of the same order as e.g. Schoenhage's earlier algorithm, so this isn't in itself any sort of breakthrough.
2. For fixed input size, the running time is constant. This is a cryptographic claim: it gives immunity to timing attacks. There have been earlier constant-time GCD and modular inverse algorithms, so again this on its own isn't any sort of breakthrough.
It isn't clear to me whether 1+2 is claimed to be new. I think it isn't: that is, there are other constant-time GCD algorithms with the same asymptotic growth of runtime.
3. The constant factors are good. This is a matter of the practicality of the algorithm. Here the authors are claiming to have done better than anyone before them.
Yes, they are. I've already made a top-level comment citing the paper's explicit definition from Section 2 and comparing it to canonical definitions from the usual literature of algorithm analysis.
> That would mean an algorithm whose running time doesn't depend on n,c.
It does not. Note the exponent, 2 + O(1). It is true that the execution time varies with the input size, but this does not preclude constant time asymptotics.
> The GCD algorithm here has the property that (I'm quoting section 1.4 here) "the number of operations is ... asymptotically n (log n)^(2+o(1))". That is not constant as n varies.
Yes it is. Constant time does not mean that execution time does not vary, in either complexity theory or cryptography.
Having a bounded exponent is simply not the same thing as "constant time"; running time that increases unlimitedly with the size of the input precisely does preclude constant-time asymptotics.
In complexity theory, "constant time" means that the execution time is bounded as the size of the input increases. The execution time of this algorithm is not bounded as the size of the input increases.
In cryptography, I don't know for sure whether "constant time" always means the same thing, but in the context of algorithms immune to timing attacks (which is the relevant context here) it means that execution time doesn't depend on the details of the input.
In this case, the algorithm does not have complexity-theory "constant time" because the runtime grows roughly like n (log n)^2. It does have cryptography "constant time" because if you fix the size of the input, the runtime does not depend on the specific numbers you put in.
I'm sorry to be so harsh here, but you have made confident wrong statements and doubled down on them when challenged. Given that your profile says "My academic background is in complexity theory", this is pretty surprising, but there's really no question that what you're saying is wrong. I'm guessing that maybe you misread something and now don't want to lose face, but you need to look again: this algorithm is not a constant-time algorithm in the complexity-theoretic sense, and it is a constant-time algorithm in the sense that the execution time doesn't depend at all on the input if you fix its size.
EDIT: To make my position clear, what I am saying is this:
1. The presented algorithm will have variable computation time, but not variable asymptotic time,
2. The algorithm uses O(1) (i.e. constant time) polynomial multiplications in the worst case, and
3. The worst case bound does not change with n nor c, though they are used in the algorithm to calibrate the divsteps such that no more than O(1) operations are required.
I will concede it's possible I'm misunderstanding the paper itself, but I don't see that here.
The algorithm presented in the paper also doesn't take a bounded number of polynomial multiplications, though I'm not sure why those should be the relevant thing to count. In section 5.4 they say they split a size-n problem into two problems whose size add up to n using O(1) polynomial multiplications of size about n, and that their algorithm takes them both to be of size ~ n/2. That means O(n) polynomial multiplications, but most of them are small so the total cost for given n is, as they say in section 5.5, Theta(log n) times the cost of polynomial multiplication provided a fast polynomial multiplication algorithm is used.
The worst-case bound, both for the number of polynomial multiplications and for the actual running time, does depend on n. (The former is of order n but, again, most of the polynomial multiplications are small; the latter is of order about n (log n)^2.)
(As for the cryptographic "constant time" notion, my understanding from the paper is that with a naive timing model -- e.g., assuming that all memory accesses take equal time -- their algorithm is exactly constant-time for fixed input size. They say in a footnote near the end of section 7: "There is considerable variation in the cycle counts, more than 3% between quartiles, presumably depending on the mapping from virtual addresses to physical addresses. There is no dependence on the secret input being inverted.")
> 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).
In particular note that last sentence. The asymptotic runtime of the presented algorithm does not depend on the inputs, n and c. This algorithm analysis is confirmed throughout the remainder of the paper, which walks through each stage of the algorithm. Now let's look at a few canonical definitions of "constant time", i.e. O(1).
From Skiena, we have:
Constant functions - f(n) = 1 - Such functions might measure the cost of adding two numbers, printing out the "Star Spangled Banner", 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.
Likewise from Sedgewick & Wayne:
Constant. A program whose running time'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'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'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 not about an implementation methodology that ensures the GCD algorithm will take exactly the same amount of time regardless of the input.
______________________
1. The Algorithm Design Manual, 2nd Edition, § 2.3.1 Dominance Relations, Page 39
2. Algorithms, 4th Edition, § 1.4 Analysis of Algorithms, Page 187
> All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c).
This means that once you have chosen a particular n and c, the time no longer varies. However, if n and c vary, the running time is definitely allowed to vary also (as the formulas n(c + n) and (c + n)(log cn)^2+o(1) clearly do).
For precision, I'll start with a good definition[1] for what "constant time" means in cryptography:
> Constant-time implementations are pieces of code that do not leak secret information through timing analysis. This is one of the two main ways to defeat timing attacks: since such attacks exploit differences in execution time that depend on secret elements, make it so that execution time does not depend on secret elements. Or, more precisely, that variations in execution time are not correlated with secret elements: execution time may still vary, but not in a way that can be traced back to any kind of value that you wish to keep secret, in particular (but not only) cryptographic keys.
Secure, constant time cryptographic algorithms need not have unvarying execution time. Now going back to complexity theory, it is also an extraordinarily common misconception that "constant time" means "the algorithm has the same execution time regardless of the size of the input." This is not the case. Big O notation doesn't even care about what always happens, it cares about what happens in the worst case. When we use "constant time" in the O(1) sense of the word, we are not precluding the possibility of an algorithm having variable execution time. Again, for precision, we are simply saying that the execution time (number of operations, etc) has an asymptotic upper bound which is independent of the input. The execution time may vary with the input, and generally speaking it will.
_________________________
1. Thomas Pornin, Why constant time crypto? https://bearssl.org/constanttime.html
Again, overloading of the term "constant time" causes pointless misunderstanding and arguments. Your statement here is wrong.
In complexity theory the term "constant time" does indeed mean the running time is bounded even with unbounded input (e.g. goes to infinity), although it could vary within this bound.
In cryptography the term "constant time" is sometimes used to mean a different concept, that the operation actually takes constant non-varying time, so that an attacker can't exploit this as a side channel to figure out the input values.
The paper seems to be using the latter meaning.
Note that I cited Thomas Pornin for my definition of constant time cryptography, who is a cryptographer in theory and implementation. It is emphatically not necessary for software to run with unvarying execution time in order for it to be "constant time" according to the cryptographic sense of the term. This will be a poor hill for you to die on, but I invite you to provide literature supporting your alternative definition.
For example, some people would say that an operation like a⨯b takes constant time or that its time complexity is O(1). However, other people (for example those implementing a bignum library) would say that the operation takes time depending on the word size of the operands. In the case of the multiplication operation, see for example [1] for a complexity analysis, to get an idea of what I mean.
[1] https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse...
What we have here in the cryptography sense is different: the running time n(c+n) clearly does depend on n; it just does not depend on the actual input. That is, it is only constant across inputs of the same size.
I am not sure how you're claiming that n(c+n) is O(1) when it's clearly Θ(n^2) (i.e. O(n^2) and Ω(n^2)).
Can you explain to me what the input is, if not c and n?
I'm really curious about your comments here. To understand them better, could you take a moment to say which of these statements you disagree with:
(1) A function f is O(1) if it is bounded. That is, if there exists a constant C such that for all n, we have f(n) < C.
(2) When we say that an algorithm (or more precisely, its running time) is O(1), we mean that the function “the algorithm's running time as a function of its input size” is O(1). In other words, let's denote the time that the algorithm takes on input I by T(I), and let us denote f(n) = max_{|I|=n} T(I) where |I| denotes the size of input I. Then we mean that f(n) = O(1). In simpler terms: that the worst-case running time does not grow without bound as a function of the input size.
(3) The algorithm in this paper, to compute the GCD of two polynomials or integers, does not have a bounded running time. (In fact, the authors describe it by the term “subquadratic”, and compare it to earlier subquadratic algorithms: “[…] a constant-time algorithm where the number of operations is subquadratic in the input size—asymptotically n(log n)^{2+o(1)}.”) That is, given any constant C, there exist inputs to this algorithm (two sufficiently large polynomials or integers) such that the running time of the algorithm is greater than C.
(4) As (3) shows that the property described in (2) does not hold, the running time of the algorithm here is not O(1).
One can argue separately whether “constant time” should be used to mean
• (the usual computational complexity sense) that the worst-case running time, i.e. the function f(n) is O(1), or
• (the cryptography sense) that T(I) does not give any exploitable information about I beyond what is known, typically |I|.
This is just an unfortunate clash of terminology across the cultures of the two fields, and IMO not an interesting thing to debate — everyone can choose whatever terminology works for them. But your claim that the two definitions are the same is puzzling, as all of (1), (2), (3), (4) seem obvious to me.
Imagine a magic sorting algorithm that always takes 1 second to check if an input is sorted, and 9 seconds to sort the input if wasn't sorted. It then returns the sorted value as output.
EG sorting "abcdefg" would check (taking 1 second) and then return (taking 0 seconds since it's sorted). Sorting "gfedcba" would check (taking 1 second) and then sort (taking 9 seconds) and return. Taking in the complete works of Shakespeare it would check (taking 1 second) and then sort (taking 9 seconds) and return.
It's O(1), yet the time varies based on the input. From a computational complexity terminology standpoint it's constant time, from a cryptographic terminology (and common intuition) standpoint it's clearly not, since it doesn't always take the same time to run.
The introduction to the paper talks about the importance of developing constant-time implementations of Euler's algorithm to avoid timing attacks, pointing out how algorithms with conditional jumps are susceptible to, for example, cache timing attacks.
As far as I understand it, a constant time algorithm, in the cryptographic sense, is one whose running time is uncorrelated with the precise secret information. If it were correlated, then timing attacks would let you infer the secret information. Presumably, if there is no random model, then the definition is that the algorithm must run in the exact same amount of time no matter the input, assuming a fixed size for the inputs. (At least one of the cited papers agrees with this definition.)
The contribution of the paper is a constant time divstep algorithm. The quote "All of these algorithms take constant time, i.e., time independent of the input coefficients for any particular (n, c)" seems to have ambiguous quantifiers and should be rewritten. It should be something like "given a fixed number of iterations n and a fixed number of input power series coefficients c, our divstep takes a constant n(c + n) simple operations, and the algorithm is constant time, i.e., the running time is not correlated with the precise inputs." Section 1.1 gives exact cycle counts for various CPUs.
Section 7 discusses how to use bit masking to actually implement it in a constant time way (in the cryptographic sense).
Anyway, divstepsx is certainly not O(1) time unless n and t are fixed constants.
Their paper shows that the algorithm takes a constant time to compute the Cth coef. of the Nth step, for a given C and N. Not that the algorithm time is independent of C and N. C and N are not the input of the GCD. The algorithm running time is constant for the input of the GCD. It is dependent on C and N.
(EDIT: ... as long as inputs have the same bit-length. Any 32-bit inputs will be handled faster than 1024-bit inputs, but any 1024-bit inputs will consume the same amount of time no matter their actual values. That is, 0x0001 and 0x000000001 are handled differently by the algorithm.)
The paper do mention this:
> However, in cryptography, these algorithms are dangerous. The central problem is that these algorithms have conditional branches that depend on the inputs. Often these inputs are secret, and the branches leak information to the attacker through cache timing, branch timing, etc.
So, yeah, this is security-centered cryptography paper. The term "constant-time" is used in a different context here.
> as long as inputs have the same bit-length. Any 32-bit inputs will be handled faster than 1024-bit inputs, but any 1024-bit inputs will consume the same amount of time no matter their actual values. That is, 0x0001 and 0x000000001 are handled differently by the algorithm
indicates the algorithm is constant-time in one sense but not the other?
People are wrong with that (1) O(1)=fast/efficient (2) I'm arguing over the definition of "constant-time".
So if it's not used to mean "constant (no matter what you vary)", then it means "constant (if you vary certain parameters and I'm not specifying which ones)". When you use a phrase with something left out and implied, then the audience has to fill it in somehow. If the audience shares your background, perhaps has been reading similar papers recently in which "constant with respect to xyz" had the xyz spelled out explicitly, this may go well; if not, it may not. In this case, people's interpretations of "the xyz we're varying" appear to range over "the entire space of integer-tuple inputs", "the size of the integers", "the bits of the integers after the leading 1", "the parts of the inputs that are considered 'secret'", and more.
So, if you say something with an implicit part left unspecified, and people fill it in with something different than what you intended... the first time this happens, I might consider it an unfortunate accident. If it happens repeatedly, it may be worth being more explicit or choosing another term. (Suggested terms: "secret-hiding", "secret-blind". "[something]-oblivious" might be another good word-formation—precedent exists in "cache-oblivious" algorithms.)
This is not the worst terminological mess we have in CS[1].
[1] My (least) favorite example is the term "dynamic programming", whose name appears to have been chosen because it sounded good and was vague enough to cover what the author wanted: "Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities." https://en.wikipedia.org/wiki/Dynamic_programming#History
It's "constant time" in the cryptographic sense, that the time to run it can't be used as a side-channel to figure out what the inputs are. A great result to be sure, but the terminology is undoubtedly confusing.
So while the terminology seems confusing, it’s not actually different. It’s just a different choice of “input” compared to typical algorithm analysis.
Yes it is. The presented algorithm is constant time in the exponent, i.e. 2 + O(1), where this exponent is not impacted by the size of the inputs n and c. Much like any other complexity analysis, an algorithm is O(1) as long as O(1) is asymptotically the "largest part" of the running time. As the size of n increases, the exponent 2+O(1) increasingly dominates execution time.
A bounded exponent of n would be the same thing as "polynomial time", but the thing that's bounded (and indeed arbitrarily close to 2 for large n) is the exponent of log n.
The running time of the algorithm presented in this paper is n (log n)^(2+o(1)). This ...
... is not constant; it increases with n, a bit faster than linearly.
... has o(1), not O(1), in the exponent; the two mean different things. O(1) means "bounded", o(1) means "tends to zero". The claim isn't that the running time is <= n times polynomial(log n) but that it's <= n times "at most approximately a quadratic polynomial in log n".
... doesn't in fact depend mostly on that exponent; the most important factor is the n, not the (log n)^(2+o(1)). If that 2 were a 100, the n factor would still (asymptotically) matter more.
For instance, suppose n=2^100 and our logs are to base 2. Then the running time of this algorithm is approximately some constant times 2^100 (that's the n factor) times 100^2 (that's the factor with log n in it). 2^100 is much, much, much bigger than 100^2.
Sometimes people actually count individual operations to form a function T(n) depending on the input n (see, for example, Knuth's books). If T(n) is the constant function, then the algorithm takes constant time in a much more literal sense.
(The "constant time" terminology bugged me when I first learned about computational complexity.)
Edit: It seems "constant time" in this paper might actually mean "the running time is uncorrelated with the precise secret value, only its size."
(Perhaps you meant factoring large semi-primes? :) )
And the article isn't claiming that the GCD code here takes the same time regardless of the input, it's saying that for two inputs of the same size the time take is the same. Time as a function of the input size is still proportional to the number of bits in the input, it's just that the routine takes the same time regardless of how many of those bits are 0, regardless of the structure of the input numbers.
========
To others commenting here, the guidelines[0] say:
Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith.