Belgian programmer solves MIT’s 20-year-old time capsule cryptographic puzzle

Re:Belgian programmer solves MIT’s 20-year-old time capsule ... by martinhath on Tuesday April 30, 2019 @05:00AM (#19786230)

The reason this isn't the same is that addition is associative, so you can parallelize it like this: `((1+1)+1)+1 = (1+1)+(1+1)`.

A fast way to calculate something like `g^x` for some large `x` is to iteratively square:

  g^1
  g^2
  g^4
  ...
  g^(2^i)

and the puzzle is designed so that `i` is large (`79_685_186_856_218`)

Of course, this doesn't prove that computing `g^x` is sequential, but it does show why it is different than computing `1+1+...+1`.

[ Parent | on HN ]

Re:Belgian programmer solves MIT’s 20-year-old time capsule ... by thaumasiotes on Tuesday April 30, 2019 @01:36PM (#19790087)

Doesn't this suggest that computing 2^i is just as hard?

You can compute g^(2^i) by just multiplying g's in the same way that you can compute 2^i by adding 1s, and multiplication is as associative as addition is. Specifying that you want g^(2^i) rather than g^k for some arbitrary k looks like a way of ensuring that a partial product computed in parallel (say, g^3) will be of nearly no value, because every partial product that helps compute the total will already be produced by the single agent doing squares.

So why compute g^(2^i) rather than just 2^i? Is 2^i in fact hard to compute? (In binary representation, it certainly isn't, but maybe 3^i is?)

[ Parent | on HN ]

Re:Belgian programmer solves MIT’s 20-year-old time capsule ... by martinhath on Wednesday May 01, 2019 @07:57AM (#19796251)

Using the doubling trick you can compute `2^i` in `log i` time, so you can compute `2^(2^i)` in `log 2^i = i` time. Let `i` be big enough, and you've got a "difficult" problem.'

[ Parent | on HN ]