1
$\begingroup$

I don't really know how to phrase this question, so I'll just mention the idea. This is partially reminiscent (at least in spirit to white box crypto): Can one derive arithmetic operations from a number? Is there a formula to do that?

So, the simplest example would be:

a = 4
ops = get_operations(a)
print(ops)

/* output:
*
* b = 2
* c = 2
* return b + c
*/

The idea is to simply have a way to "derive" a mathematical operation from a value. There are obviously more than "one" operation that could be derived from the above example. The system does not have to be complete.

The flow of such a "derivation" algorithm in my head is as such:

  1. Get input (k)
  2. Randomly choose an arithmetic operand (P) where y = k (P) x and store the operand (P)
  3. Pick a random number (x) and store its value
  4. Solve for (y) and store its value
  5. Now, we have a combination of (P), (x), and (y) that, when solved, would yield the correct input (k).

My question is this: did someone research this and make a way better algorithm that what I could muster up here?

$\endgroup$
  • $\begingroup$ "a way better algorithm" - define "better", that is, by what criteria are you comparing the various possible algorithms? $\endgroup$ – poncho Jun 27 '19 at 6:33
  • $\begingroup$ "way better" means if there is a name for this topic and has it been researched before by professional mathematicians $\endgroup$ – jimmytann Jun 27 '19 at 6:45
0
$\begingroup$

Is there a formula to do that?

Your example looks like a problem about Partitions to me. A partition is a way of representing a positive number as a sum of $n$ positive integers, for example:

The partitions of the number $5$ are:

  • $5 \space (+0)$
  • $4 + 1$
  • $3 + 2$
  • $3 + 1 + 1$
  • $2 + 2 + 1$
  • $2 + 1 + 1 + 1$
  • $1 + 1 + 1 + 1 + 1$

Since partitions consider every possibility valid, the number for possible ways of any integer $n$ can grow very fast, i.e. the number of possible partitions of the number $100$ is $190,569,292$.

There exist some formulas (some more complicated or faster than others and some are only approximations).

In your example you only have an operator once, so here $4 + 1$ and $3 + 2$ would be a possiblity.


Since you mentioned "more than one operation", a possibility would also be to represent numbers as their prime factors, for example:

The prime factorization of the number 22 is:

  • $2 \times 11$

There's always only one possiblity to represent a number as it's prime factors (if you don't care about the way you write it ($2 \times 11$ is the same as $11 \times 2$)).

There are a lot of factoring algorithms, since this is still a unsolved problem (Does P = NP ?) and this problem is important for cryptography.


I assume that a problem occurs if you'd try to do this with the operators of division and subtraction, for example:

There are infinite possibilities to represent a number as a subtraction, for example:

For the number $5$:

  • $6 - 1$
  • $7 - 2$
  • $8 - 3$
  • $9 - 4$
  • $\ldots$
| improve this answer | |
$\endgroup$
0
$\begingroup$

I could think of two things: Tweakable Block Cipher, and Tweakable Compression Function.

  1. Tweakable Block Cipher:

More info here.

A Tweakable Block Cipher is defined with the prototype: $f : D \times K \times T \rightarrow D $ where $D$ is the block of data to be encrypted/decrypted with the key $K$ using the block cipher function $f$, that can be efficiently parameterized with $T$.

  1. Tweakable Compression Function:

I assume you mean binary operations when you say operation (binary in the sense that there are 2 operands).

Basically, we just build a compression function from a tweakable block cipher using Davies–Meyer construct or any other method to turn a block cipher into a compression function.

$g : D \times D \times T \rightarrow D$

f <- blockcipher(d, key, tweak);
g <- compressionfunc(a, b, tweak){ return blockcipher(a, b, tweak) xor a; }
| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.