1
$\begingroup$

I am currently trying to find a way to generate different (preferably quadratic) function as part of a encryption algorithm such that :

f(x) = natural number (where x is also a natural number)

So far, the only functions that I could think of would be straight line functions, which isn't the best thing to use in encryption.

Would there be a method to generate such a function (or does such a quadratic function even exist)? If no, are there any other kind of functions that could produce the sought after results?

I don't have the best background in mathematics (a student of computer science) so a thorough explanation would be greatly appreciated.

$\endgroup$

1 Answer 1

0
$\begingroup$

Any polynomial with integer coefficients will generate integer outputs for integer inputs.

I assume that you have specific function values which you need to satisfy (i.e., $f(x)$ and $x$ are not necessarily arbitrary integers.)

If you have simple enough function values such that a quadratic function fits the data points, just take the quadratic form $y=Ax^2 + Bx+C$ and vary its parameters.

However, if you have a more complex set of data points to match a polynomial to, you interpolate a polynomial from the data points.

You say you don't have the best background in mathematics, so something like the Lagrange interpolating polynomial might seem a bit off-putting, but it is quite intuitive once you spend some time thinking about it.

In the meantime, you can use WolframAlpha's own interpolating polynomial calculator to generate functions that match your data points.

My final note is on Cantor pairing functions. This quadratic function maps two natural numbers to one; it encodes two natural numbers in a second.

Furthermore you can prove that any function value of a Cantor pairing function has two unique associated numbers, it is a one-to-one correspondence.

This might be of interest to you. As long at the order $N$ of the key set and the set which you are encoding is the same, there should be $N/2$ pairing function values which encode the "key" data set.

$\endgroup$
1
  • $\begingroup$ Thank you! The Cantor pairing function did almost exactly what I was looking for, but I will go spend some time trying to understand interpolating polynomials $\endgroup$
    – eclmist
    Jan 26, 2016 at 3:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .