Computers for mathematics: theoretical solution versus constructive solution.

In this article the role of technology and its pivotal--in many cases, indispensable--role in solving real-world problems is underscored. It is demonstrated that the existence of a solution to a problem, which has been proven by any means, does not guarantee a constructive solution of the problem.

In general, the problems are divided into two categories, namely, type I and type II. For any given type I problem, there is an algorithm for constructing the solution. Type I problems are divided into two classes [I.sub.1] and [I.sub.2]. [I.sub.1] includes those problems, for which the existing algorithm is a polynomial one, and [I.sub.2] includes NP-complete problems, for which no polynomial time algorithms are known. For Type 11 problems, there are not any known algorithms to construct the solution, that is, one may be able to find the solution(s) by trial and error (heuristic). In this article the crucial and positive effects of technology in constructing the solution to Type II problems are surveyed. Also NP-complete problems and their role for constructing Public-Key Cryptosystems, and different existing Digital Schemes along with the role of technology and the advances in the field are discussed. Finally Mathematica (version 4) is being used to approximate or to construct the solutions to some of the T ype 11 and Type I problems.

SOLUTION TO A WELL-POSED PROBLEM 

In this work it is assumed that the existence of solutions to a problem have been proven by some methods, and one is seeking to construct these solutions. The problems can be divided in two types, Type I, and Type II. Problems of Type I are those for which there is an algorithm for finding the solution. In intuitive terms, an algorithm is a computational or decision-making procedure that can be completely automated (for example, programmed on a computer). Type I problems are divided into two classes [I.sub.1] and [I.sub.2]. The solutions to Type [I.sub.1] problems are found in a limited time. In other words one can find a solution to any given problem of this type in a limited time. Type [I.sub.2] problems are those for which applying the algorithm could take indefinitely long (unlimited time). This means that there are problems of this type, for which finding solution can take forever using the algorithm. For Type II problems there is no known algorithm for constructing the solution. For a problem of this ty pe, one can choose a heuristic approach to find a solution. Heuristic approaches to a problem are by no means guaranteed to work or to be correct, but suggest a course of action or suggest what is true (trial and error process).

Most of the real world problems involve problems of Type [I.sub.2] and Type II. In fact the security of all Public Key Cryptosystems, and Digital Schemes depends on the fact that there are not any known polynomial time algorithms for Type [I.sub.2] problems or NP-complete problems. In practice, one can call a cryptosystem "computationally secure," if the best known method of breaking the system requires an unreasonably large amount of computer time. This definition or any other (possibly nonequivalent) definition only provides security relative to either computer time or some other problem(s), not an absolute proof of security. So the advances in technology, such as cheap availability of strong processors, can undermine the security of existing Cryptosystems. So as technology advances, the needs for strengthening the existing Cryptosystems and creating new ones based on Type [I.sub.2] problems increases. In what follows we describe several Public Key Cryptosystems and their connections with different NP-compete problems.

NP-COMPLETE PROBLEMS AND PUBLIC KEY CRYPTOSYSTEMS

The Security of RSA Cryptosystein, from the last names of inventors, Rivest, Shamir, and Adleman (1978) depends solely on the lack of existence of a known polynomial time algorithm for factorization of integers, while the security of Diffie & Hellman (1976), ElGamal (1985), and Massey (1988) revolved around the fact that computing the discrete logarithm in finite fields is an NP-complete problem. Also the security of [KS.sup.*] Cryptosystem from the last names of inventors, Khadivi and Schaff (2001) relied on several NP-complete problems. We should mention that the security of the Knapsack Cryptosystem is based on the fact that the super increasing knapsack problem (Merkle & Helman, 1978) is an NP-complete problem.

EXAMPLES

Some examples of Type [I.sub.1] problems are as follows:

Finding the Greatest Common Divisor and the Least Common Multiple is of Type [I.sub.1]. One can use the Euclidean Algorithm to find the greatest common divisor of two polynomial in F[X], for any field F.

For example the G.C.D.(34359738367, 2^64-1)=1, G.C.D.(2x^4+2x^3+x+1 x^4+x^3+2x+2)=2+2x+x^3+x^4 in [Z.sub.3][x], and G.C.D.(2x^4+2x^3+x+1,x^4+x^3+2x+2)=1+x in [Z.sub.5][x], Mathematica returned the results in a fraction of a second.

Finding the derivative of a diferentiable function is of Type [I.sub.1] A special example is finding the derivative of f(x)=(1+x^2) ^sin(cos(pi * x))-2.

Simplification of Mathematical Statements are of Type [I.sub.1] As an example one can show that

100!/1073741823=43441891469508054127309611719157799

41847785144736844084559557040227975608305633087042846156316

9251669864447275856433377609515008000000000000000000000000/49981.

The following theorems provide Type [I.sub.2] problems. It should be mentioned that the theoretical solution(s) for this type of problems exist.

The Fundamental Theorem of Arithmetic (FTAR) states that any natural number n can be written uniquely (except for the order of factors) as a product of prime numbers. It is customary to write this factorization as a product of distinct primes to the appropriate powers, listing the primes in increasing order. For example:

4200=2^3*3*5^2*7,

1111122222223333344445555566667777788899999=3

^2*13^3*13711*3449863l*2007708621258793772669830074802849,and 1111122222223333344445555566667777788899999=1493^2*282241*5743382747* 307506539925806346613.

These are Type [I.sub.2] problems and Mathematica provides the factorization in a fraction of a second, however Mathematica was not able to factor 111111111111111111111111112222222222222333333333444444444444 5555577777777777777577 in more than seventy-two hours as expected, which is categorized as Type [I.sub.2] problem. Computing the log of 42 in base 24 in [F.sub.229345007] is also of Type [I.sub.2] Note that 47^5=229345007.

The following theorems provide uncountably many Type II problems.

The Fundamental Theorem of Algebra (FTAL) states that if f(x) is a polynomial of degree n, where n is a positive integer, then f has at least one zero in the Complex numbers system, and f(x) can be written of n linear factor with coefficients in Complex numbers system. This is of Type H. For example:

x^4+x^2+1 1 = (1-x+x^2)(1+x+x^2), and

X^5+3x^4-7x^3+2x^2-12x+13(-1+x)(-13-x-3x^2+4x^3+x^4).

Also x^5+3x^4-7x^3+2x^2-12x+13(5+x)(6+x)(3+2x+6x^2+x^3) in [Z.sub.7][x]. Also the solution set to x^4-5x^4+4x^3-3x^2+2 = 0 is {-0.5, 1, 0.25(1+I*Sqrt(15)), 0.25(1+I*Sqrt(15)) }. All of these problems were done in a fraction of a second by Mathematica, however Mathematica was not able to give any solution of closed form to:

109x^37-l6x^5-172x^4-x^2+x-23 = 0. The software was able to give just one solution of closed form to 109x^37-l6x^5-l72x^4-x^2+x-78 = 0, and that was {1} as expected. Notice that the solution set to f(x) = 0 must be found, if one needs to find factorization of f (x) over the Complex number system as mandated by FTAL.

The Fundamental Theorem of Calculus (FTC) states that if F(t) has a continuous derivative in an open interval I, then for a and b in I,

[[integral].sub.[a,b]] F'(t)=F(b)-F(a).

This is of Type II. A special case of this theorem is [[integral].sub.[0.4,1]] (e^x*sin x-x^x+x^x^x)dx.

Differential Equations are of Type II. As an example one can mention dx/dt= cos t+sin x ; x(-6)0.3.

CONCLUSIONS

It should be mentioned that most of the widely used existing software are not even capable of solving simple Type II problems or Type I problems, yet these problems occur in many applications in our daily life. This is one of the reasons why there is a need to develop new software and hardware capable of doing mathematical calculations faster. Obviously, software and hardware developers must have a very deep knowledge of theoretical solutions and difficulties in constructing the solution(s).

Thus, mathematics must not only be taught precisely at all levels to motivate critical thinking, but also presented as an essential tool to tackle and solve important real world problems. In particular, the teacher who uses technology in teaching mathematics should raise awareness of the distinctions between theoretical and constructive solutions, and emphasize its use in "non-feasible" (i.e., Type [I.sub.2] and Type II) problems, which dominate current applications and research activities. Traditionally, technology use in teaching mathematics has concentrated on Type I problems and "cookbook recipes." It is time for a shift of emphasis to more vital and relevant problems.

Note

The author with the collaboration of Mr. Joseph Schaff invented this Cryptosystem, while he was offering short courses and seminars for the engineers and staff of Naval Air Warfare Center Aircraft Division in Patuxent River, Maryland on Cryptography. This will be a patented Cryptosystem. The research opportunity for this invention was made available through Summer Faculty Research Program. This author wishes to thank Dr. Asha Varma, the coordinator of the program, for her support during the research period and her encouragement to request a patent for the KS Cryptosystem.

References

Rivest, R., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Comm. ACM, 21, 120-126.

Diffie, W., & Heliman, M.E. (1976). New directions in Cryptography, IEEE Transactions on Information Theory, IT-22, 644-654.

ElGamal, T. (1985). A public key cryptosystem and signature scheme based on discrete logarithms, IEEE Transactions on Information Theory, IT-31, 469-473.

Massey, J.L. (1988). An Introduction to contemporary cryptology, Proceedings of IEEE, 76, 533-549.

Khadivi, M., & Schaff, J.B. (2001). [KS.sup.*] cryptosystem, Navy Case No. 82663

Merkle, R. & Helman, M. (1978). Hiding information and signature in trapdoor Knapsacks, IEEE Transactions on Information Theory, IT-24, 525-530.