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

41–50 of 84 posts

Re: Fast constant-time GCD algorithm and modular inversion

#41

Post by throwawaymath »

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…

That's not how this works. What you're doing here is defining away the scope of the problem to make O(1) complexity analysis redundant. A bound of O(1) conventionally means that we can exploit some structural component of the input and the given problem to find a solution independent of the input size. If you redefine input size to the more narrow sense of inputs which don't have some sort of structural feature like that, then yes of course nothing is constant time. But then you're just shifting the difficulty of the problem around without much of a gain.

Re: Fast constant-time GCD algorithm and modular inversion

#42

Post by Drod718 »

throwawaymath wrote: post #38
arghwhat wrote: post #32

Earlier quoted context omitted.

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

Wouldn’t searching for an element in an arbitrary array of size n happen in O(n) time, while only accessing it is considered O(1)? I could understand the search case for something like a hash table being O(1) but does that also apply to your standard array?

Re: Fast constant-time GCD algorithm and modular inversion

#43

Post by arghwhat »

repsilat wrote: post #34
arghwhat wrote: post #31

Earlier quoted context omitted.

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

> I think it would be tough to find a suitable definition of "meaningful".

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.

Re: Fast constant-time GCD algorithm and modular inversion

#44

Post by throwawaymath »

It's pretty frustrating to see the discussion on this submission dominated by people litigating the "constant time" 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, "Organization of this paper":

> 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

Re: Fast constant-time GCD algorithm and modular inversion

#45

Post by mratsim »

Yajirobe wrote: post #29
ColinWright wrote: post #25

Earlier quoted context omitted.

Given that you have to read and then write each digit of the input I find it hard to believe that you have an O(1) algorithm - can you tell us what it is?

Take a photo of the input on the tape and print the photo.

Depending of the size of the prime you might need to take multiple photos.

Re: Fast constant-time GCD algorithm and modular inversion

#46

Post by throwawaymath »

Drod718 wrote: post #42
throwawaymath wrote: post #38

Earlier quoted context omitted.

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

Wouldn’t searching for an element in an arbitrary array of size n happen in O(n) time, while only accessing it is considered O(1)? I could understand the search case for something like a hash table being O(1) but does that also apply to your standard array?

Ah, I misspoke. I meant "access", you're correct about searching. The original link I cited for explanation still applies.

Re: Fast constant-time GCD algorithm and modular inversion

#47

Post by arghwhat »

throwawaymath wrote: post #41
arghwhat wrote: post #31

Earlier quoted context omitted.

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

That's not how this works. What you're doing here is defining away the scope of the problem to make O(1) complexity analysis redundant. A bound of O(1) conventionally means that we can exploit some structural component of the input and the given problem to find a solution independent of the input size. If you redefine input size to the more narrow sense of inputs which don't have some sort of structural feature like…

I see how you may think that, but I would argue that I am not redefining anything, as things turn nonsensical without this assumption.

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.

Re: Fast constant-time GCD algorithm and modular inversion

#48

Post by throwawaymath »

arghwhat wrote: post #47
throwawaymath wrote: post #41

Earlier quoted context omitted.

That's not how this works. What you're doing here is defining away the scope of the problem to make O(1) complexity analysis redundant. A bound of O(1) conventionally means that we can exploit some structural component of the input and the given problem to find a solution independent of the input size. If you redefine input size to the more narrow sense of inputs which don't have some sort of structural feature like…

I see how you may think that, but I would argue that I am not redefining anything, as things turn nonsensical without this assumption. 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 see how you may think that, but I would argue that I am not redefining anything, as things turn nonsensical without this assumption.

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?

Re: Fast constant-time GCD algorithm and modular inversion

#49

Post by ziedaniel1 »

throwawaymath wrote: post #44

It's pretty frustrating to see the discussion on this submission dominated by people litigating the "constant time" 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, "Organization of this paper": > We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Sectio…

I think you misread slightly.

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

Re: Fast constant-time GCD algorithm and modular inversion

#50

Post by amelius »

throwawaymath wrote: post #44

It's pretty frustrating to see the discussion on this submission dominated by people litigating the "constant time" 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, "Organization of this paper": > We start with the polynomial case. Section 3 defines division steps. Section 5, relying on theorems in Sectio…

The confusion is that the word-size of the operands plays a role.

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

Post reply on HN