4
$\begingroup$

If we suppose that we can start with any function we like, can we work "backwards" and differentiate the function to create an integral that is hard to solve?

To define the question better, let's say we start with a function of our choosing, $f(x)$. We can then differentiate the function with respect to $x$ do get $g(x)$: $g(x) = f'(x)$

This, in turn, implies, under appropriate conditions, that the integral of $g(x)$ is $f(x)$: $\int_a^b { g(x) dx } = [f(x)]_a^b$

I'm wondering what conditions are appropriate to allow one to easily get a $g(x)$ and $f(x)$ that assure that $f(x)$ can't be easily found from $g(x)$.

SUMMARY OF THE QUESTION

Can we get a function, $g(x)$, that is hard to integrate, yet we know the solution to? It's important that no one else should be able to find the solution, $f(x)$, given only $g(x)$. Please help!

POSSIBLE EXAMPLE

This question/integral seems like it has some potential.

DEFINITION OF HARDNESS

The solution to the definite integral can be returned with the most $n$ significant digits correct. Then it is hard to do this if the time it takes is an exponential number of this time.

In other words, if we get the first $n$ digits correct, it would take roughly $O(e^n)$ seconds to do it.

  • 0
    If the encoded message is to consist of a numerical value of a definite integral, then you're vulnerable to at least two kinds of attacks: (1) the attacker succeeds in performing the indefinite integral, or (2) the attacker is able to analyze the expression well enough to do adaptive integration http://en.wikipedia.org/wiki/Adaptive_quadrature , which only requires figuring out where the function has bad behavior. Neither of these seems hard enough that I would trust them for crypto.2012-07-23

4 Answers 4

2

I interpret your question as follows:

Is there any differentiable function $f$ and pair of real numbers $a,b$ such that computing the integral $\int_a^b f'(x)dx$ to $n$ bits of precision given $a,b,f'$ is substantially harder than computing $f(b)-f(a)$ to the same precision?

The answer to this is no, in the sense that if $f(b)-f(a)$ can be computed in $O(h(n))$ then the integral can be computed in $O(h(n))$ as well, assuming $\lim\limits_{n\to\infty} h(n)=\infty$. One way to do this would be to simply enumerate all functions with finite-length definitions and differentiate them until one is found with derivative $f'$. One might object that it is impossible to determine whether two strings of symbols produce the same function, but there are only countably many algorithms for symbolic differentiation. Any algorithm used to differentiate $f$ must be a provably correct implementation of differentiation, and one can enumerate these by enumerating the list of all algorithms and of all proofs using the standard pairing function and checking each pair (algorithm,proof) to see if the proof proves the correctness of the algorithm. We can thus enumerate all pairs (function, provably correct differentiation algorithm). Thus we get the function $f$. This is obviously done in constant time w.r.t. $n$, and so if we can compute $f(b)-f(a)$ in $O(h(n))$ we can compute the integral in $O(h(n))+O(1)=O(h(n))$.

  • 0
    @ZhenLin True, but any algorithm that he could use would have to be provably correct, and there is a computable enumeration of all algorithms that can be proven to correctly implement differentiation.2012-07-23
6

This seems off what you are asking, but you should know it since it changes what you want. Volterra came up with an example of a function on, as I recall, the open interval $(0,1)$ which has a derivative at every point. The derivative is bounded but discontinuous on a Cantor set of positive measure. As a result, the derivative does not have an integral: possession of a definite Riemann integral is equivalent to the set of points of discontinuity being of measure zero. The example is in Counterexamples in Analysis by Gelbaum and Olmsted. I will see if I can find something on line. HERE

EDIT: the Volterra derivative does not have an indefinite integral either. This comes late in the Beamer talk by Bressoud referenced on WickedPedia.

3

Here is an example (by Harold Davenport) of a function that is hard to integrate:

$\int{2t^6+4t^5+7t^4-3t^3-t^2-8t-8\over (2t^2-1)^2\sqrt{t^4+4t^3+2t^2+1}}\,dt\ .$ The primitive is given by (check it!) $\eqalign{&-2\log(t^2+4t+2)-\log(\sqrt2+2t)\cr&+ \log\left(\sqrt2 t+2\sqrt2-2\sqrt{t^4+4t^3+2t^2+1}\,\right)\cr &-5\log(2t^2-1)-5\log\left(2\sqrt2 t+4\sqrt2 -t^2-4t-6\right) \cr&+ 5\log\left(\bigl(4\sqrt2+19\bigr)\sqrt{t^4+4t^3+2t^2+1}\right. \cr &\qquad\qquad\left. - 16\sqrt2 t^2 -8\sqrt2 t +6\sqrt2 -29t^2-38t+5\right)\cr}$ $\eqalign{ &+ 2\log\left(\bigl(10\sqrt2+17\bigr)\sqrt{t^4+4t^3+2t^2+1}\right.\cr &\qquad\qquad\left.+4\sqrt2 t^2+16\sqrt2 t -2\sqrt2-11t^2-44t-39\right) \cr &+ {1\over2}\log\left(\bigl(731\sqrt2 t+71492\sqrt2-70030t-141522\bigr) \sqrt{t^4+4t^3+2t^2+1} \right.\cr &\qquad\qquad-40597\sqrt2t^3-174520\sqrt2t^2-122871\sqrt2 t+50648\sqrt2\cr&\qquad\qquad\left.+90874t^3+ 403722t^2+ 272622t-61070 \vphantom{\sqrt{t^4}}\right)\cr & + {(2t+1)\sqrt{t^4+4t^3+2t^2+1}\over 4t^2-2}\ .\cr}$

  • 0
    I posted a related question to this question and answer here: http://math.stackexchange.com/questions/176000/is-it-possible-to-get-an-easy-answer-for-int-frac-px-qx1-2-rx2012-07-28
2

Find two large primes $p$ and $q$, call their product $N$; then it's easy for you to compute $\int_{J(N)}1\,dx$, where $J(N)$ is the interval between the prime factors of $N$, but for anyone else to compute the integral, she would have to factor $N$ first.

  • 0
    Well yes, but the hard part is finding the endpoints rather than doing the integration.2012-07-27