Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fast constant-time GCD algorithm and modular inversion

gcd.cr.yp.to

Post reply on HN
Print view View original

31–40 of 84 posts

Re: Fast constant-time GCD algorithm and modular inversion

#31

Post by arghwhat »

caf wrote: post #27
arghwhat wrote: post #17

Earlier quoted context omitted.

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). 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 d…

This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). 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).

> 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.

Re: Fast constant-time GCD algorithm and modular inversion

#32

Post by arghwhat »

twic wrote: post #28
arghwhat wrote: post #17

Earlier quoted context omitted.

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). 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 d…

> This is standard terminology within programming and cryptography 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.

> Within cryptography, yes, but in programming in general, absolutely not.

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.

Re: Fast constant-time GCD algorithm and modular inversion

#33

Post by xurukefi »

minitech wrote: post #15
b-3-n wrote: post #7

I was a bit disappointed to see that the "constant time" was a click bait. Should be "fixed time" - or similar - instead.

It’s not click bait. It’s standard terminology.

I disagree. "Constant time" means O(1), which this isn't.

Re: Fast constant-time GCD algorithm and modular inversion

#34

Post by repsilat »

arghwhat wrote: post #31
caf wrote: post #27

Earlier quoted context omitted.

This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). 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).

> 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 r…

I think it would be tough to find a suitable definition of "meaningful". When searching for an element in an ordered list, how many items are meaningful? One if it's present, zero otherwise? Always log(n)? Always n?

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?

Re: Fast constant-time GCD algorithm and modular inversion

#35

Post by contravariant »

arghwhat wrote: post #17
waterhouse wrote: post #3

It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). 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 d…

It might be standard notation, but not only is O(1) misleading as it misrepresents the dependency on the problem size, it is also the wrong symbol as it hides the exact thing it's trying to convey.

Re: Fast constant-time GCD algorithm and modular inversion

#36

Post by razorunreal »

arghwhat wrote: post #32
twic wrote: post #28

Earlier quoted context omitted.

> This is standard terminology within programming and cryptography 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.

> Within cryptography, yes, but in programming in general, absolutely not. 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 meaningfu…

So binary search is not logn time because it only reads logn values from the input? To know which parts are not read you basically have to run the algorithm. I find your definition unhelpful.

Re: Fast constant-time GCD algorithm and modular inversion

#37

Post by throwawaymath »

arghwhat wrote: post #17
waterhouse wrote: post #3

It seems "constant-time" isn't used to mean "the time taken is O(1) regardless of the size of the input n", but rather, "for a given input size, the algorithm is carefully written to do the same amount of work no matter what the specific bits of the input are, to defeat timing attacks". This took me a bit of time to figure out. To illustrate the kind of thing it's talking about, consider the naive algorithm for compu…

This is standard terminology within programming and cryptography. This is the only practical definition to use, as cryptography commonly deals with arbitrarily sized inputs, which can of course not all run in O(1). 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 d…

> 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:

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.

Re: Fast constant-time GCD algorithm and modular inversion

#38

Post by throwawaymath »

arghwhat wrote: post #32
twic wrote: post #28

Earlier quoted context omitted.

> This is standard terminology within programming and cryptography 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.

> Within cryptography, yes, but in programming in general, absolutely not. 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 meaningfu…

> I cannot think of any algorithms with arbitrary sized inputs that have truly constant execution time.

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"

Re: Fast constant-time GCD algorithm and modular inversion

#39

Post by tanderson92 »

arghwhat wrote: post #32
twic wrote: post #28

Earlier quoted context omitted.

> This is standard terminology within programming and cryptography 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.

> Within cryptography, yes, but in programming in general, absolutely not. 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 meaningfu…

Depending on how expansive your idea of the model of ‘computation’ is, there is this old paper: http://zero.sci-hub.tw/1814/0efc01f09f718e409481a47ff90e98fc...

TLDR: using optics for sorting

Re: Fast constant-time GCD algorithm and modular inversion

#40

Post by throwawaymath »

OskarS wrote: post #18
minitech wrote: post #15

Earlier quoted context omitted.

It’s not click bait. It’s standard terminology.

To clarify: it's not "constant time" in the sense of having O(1) time complexity with regards to the size of the inputs, which is what most people mean by "constant time" (which is obviously not possible in this case: there's never going to be a GCD algorithm that can work as fast on 100-bit integers as on 1,000,000,000-bit integers). It's "constant time" in the cryptographic sense, that the time to run it can't be u…

> it's not "constant time" in the sense of having O(1) time complexity with regards to the size of the inputs

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.

Post reply on HN