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

21–30 of 84 posts

Re: Fast constant-time GCD algorithm and modular inversion

#21

Post by moron4hire »

mehrdadn wrote: post #6
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…

I'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...

Or maybe "fixed-time". I don't like "isochronous" because it introduces an obtuse neoligism.

Re: Fast constant-time GCD algorithm and modular inversion

#22

Post by mehrdadn »

moron4hire wrote: post #21
mehrdadn wrote: post #6

Earlier quoted context omitted.

I'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...

Or maybe "fixed-time". I don't like "isochronous" because it introduces an obtuse neoligism.

Yes, fixed-time! I like it.

Re: Fast constant-time GCD algorithm and modular inversion

#23

Post by zimpenfish »

moron4hire wrote: post #21
mehrdadn wrote: post #6

Earlier quoted context omitted.

I'd propose "uniform-time" to disambiguate? Or is there a better word? I feel like there must be...

Or maybe "fixed-time". I don't like "isochronous" because it introduces an obtuse neoligism.

> I don't like "isochronous" because it introduces an obtuse neoligism.

Obtuse, perhaps, but neologism?

http://etymology.enacademic.com/20730/isochronous meaning "equal time" dating back to the early 1700s.

Re: Fast constant-time GCD algorithm and modular inversion

#24

Post by hoseja »

nullc wrote: post #14
londons_explore wrote: post #2

Isn't constant time GCD a problem for factoring big primes?

I have an O(N) algorithm for factoring any prime: Read each digit of the prime from the input tape and write it to the output tape. :P (Perhaps you meant factoring large semi-primes? :) )

I have an O(1) then!

Re: Fast constant-time GCD algorithm and modular inversion

#25

Post by ColinWright »

hoseja wrote: post #24
nullc wrote: post #14

Earlier quoted context omitted.

I have an O(N) algorithm for factoring any prime: Read each digit of the prime from the input tape and write it to the output tape. :P (Perhaps you meant factoring large semi-primes? :) )

I have an O(1) then!

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?

Re: Fast constant-time GCD algorithm and modular inversion

#26

Post by ColinWright »

londons_explore wrote: post #2

Isn't constant time GCD a problem for factoring big primes?

Assuming you mean factoring large number, specifically semi-primes with broadly similar sized factors and no assumed structure, the answer is still no. Taking N as the number being factored and C a candidate that might contain a factor, taking GCD(N,C) is not a significant part of the process. The large part of the process is usually finding C.

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.

[0] https://news.ycombinator.com/newsguidelines.html

Re: Fast constant-time GCD algorithm and modular inversion

#27

Post by caf »

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…

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

Re: Fast constant-time GCD algorithm and modular inversion

#28

Post by twic »

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…

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

Re: Fast constant-time GCD algorithm and modular inversion

#29

Post by Yajirobe »

ColinWright wrote: post #25
hoseja wrote: post #24

Earlier quoted context omitted.

I have an O(1) then!

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.

Re: Fast constant-time GCD algorithm and modular inversion

#30

Post by throwawaymath »

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 incorrect. Refer to Section 2, "Organization of the 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).

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.

Post reply on HN