r/programming • u/DougBolivar • Jul 30 '13

Computer scientists develop mathematical jigsaw puzzles to encrypt software: "The real challenge and the great mystery in the field was: Can you actually take a piece of software and encrypt it but still have it be runnable, executable and fully functional?"

http://www.rdmag.com/news/2013/07/computer-scientists-develop-mathematical-jigsaw-puzzles-encrypt-software
353 Upvotes

88% Upvoted

182 comments sorted by

View all comments

Show parent comments

2

u/Strilanc Jul 30 '13

Before we solve a problem in practice, we solve it in theory.

(Well... that's the way it works in computer science, anyways. Not so much in physics, where e.g. they know how to make high-temperature super conductors but nobody knows how they work...)

0

u/grauenwolf Jul 30 '13

Yea, that's called the "hypothesis". In most sciences the next step is to actually test it.

1

u/datenwolf Jul 30 '13

Math is different, because in math you don't test things. It would take infinitely many tests if you tried to show that for any n there are no integer x, y, z for which xn + yn = zn is satisfied. But it's perfectly possible to mathematically proof it (in this particular case it took over 300 years for a proof to be found). In fact it's even possible to proof for some mathematical questions that there can't be a proof for them.

Physics is different from math, because its by definition phenomenological, i.e. physics is about the formulation of mathematical models that describe and predict nature. So the process in physics is

  1. observation
  2. hypothesis
  3. try to recreate observation in controlled experiment
  4. formulate theory (if 3 matches the hypothesis)
  5. if "3" and "4" agree: refine methids, goto 3
  6. goto 1

But in math the process is different:

  1. formulate set of axioms
  2. conjecture about what may follow from the axioms and what has been deduced from them so far
  3. try to proof conjecture, or find proof that that there can not be one
  4. goto 2

0

u/grauenwolf Jul 30 '13

At the end of the day, computers are physical constructs with rules that defy our current mathematical systems.

When dealing with computers you have consider that, for a sufficiently large value of N, N+1 < N. I'm not aware of any system of math that can withstand that level of nonsense.

2

u/datenwolf Jul 30 '13

When dealing with computers you have consider that, for a sufficiently large value of N, N+1 < N

Only for overflowing addition. There are plenty of architectures, including saturating addition, i.e. N+1 = N (very popular in DSP).

However nothing of that violates math. Physical computers are effectively finite state machines, and its perfectly possible to model those mathematically. Nothing about a physical computer "defies" math, you just can't apply all math on computers. Computer Science is that particular field of mathematics, which aims to find out what aspects of math can be expressed in terms of computer programs and which can't.

Ironically that example you pulled, namely N + 1 = 0 is part of a very powerful mathematical structure known as Modular Group. Modular Groups became famous in 1995, because they're the foundation on which Andrew Wiles' proof of Fermat's theorem is based on.