The purpose of the following math problem is to hide some component
numbers into a composite number such that with the only knowledge of
the composite number and possibly the number of component numbers, we
can find a procedure ?h? that can determine if a number is a component
number, but we cannot deduce a component number unless we try all
possible numbers with procedure ?h?. The problem can be stated
formally and more precisely as follows.
Given the following 4 conditions,
1. Let X={x[1], x[2], x[3], ?, x[n]} where 1 < x[1] < x[2] < x[3] < ?
< x[n] and x[k] is in N (natural number), 1<=k<=n;
2. Let T[1] = f(T[0], x[1]), T0 is in R (real number)
T[k] = f(T[k-1], x[k]), 2<=k<=n ;
3. Let U[1] = T[n]
U[k] = s(x[k-1], U[k-1]), 2<=k<=n
It is possible that U[k] = U[k-1];
4. Let x be in N,
h(x, U[1]) = A[1] => x is in X
h(x, U[k]) = A[k] => x is in X
where A[k] = p(x[k-1], A[k-1]), 2<=k<=n, A[k] is in R
It is possible that A[k] = A[k-1];
find a specific combination of functions f, s, h, p and constants
T[0], A[1]. It?s necessary that the functions be exactly computable by
computer algorithms in short time, at most 1 millisecond, on common
personal computers. Also, it?s necessary that, with the only knowledge
of n, T[0], T[n], f, s, h, p, A[1], the time it takes to find x[k] is
O(w) where w is the size of the domain of x[k].
Otherwise, prove that such a solution does not exist.
Note: The more simple and elegant the solution is and the less
computation it requires, the better it is.
An example:
This example is to give a general idea about the potential solution.
T[0] = 1
f(T[k-1], x[k]) = T[k-1] * v(x[k]) where v(x) is a prime number and
v(x[a]) is different from v(x[b]) where 1<=a<b<=n
U[k] = U[k-1] = U[1] = T[n]
h(x, U[k]) = U[k] mod x and A[k] = A[k-1] = 0
This example is not complete; we still need to find v(x).
ARINTEL (Binh Kien Thai) |
