Method, software and apparatus for computing discrete logarithms modulo a prime

Abstract

A decoding apparatus having a non-transient memory in which is stored an electromagnetic signal representative of data which were encrypted relying on the difficulty of computing discrete logarithms. The decoding apparatus has a computer in communication with the memory that decodes the encrypted data in the memory by computing the data's discrete logarithm. The decoding apparatus has a display on which the decoded encrypted data are displayed by the computer. A method for decoding.

Claims

1. A method for reading an encrypted message as an electromagnetic signal representative of encrypted data comprising the steps of: entering the encrypted message as the electromagnetic signal into a computer; decrypting by the computer the encrypted message as the electromagnetic signal in a time of the order of log log p x log squared p by selecting with the computer primitives of sub-groups of a group stored in a non-transient memory, where the group is defined modulo (p1) in such a way that an exponent of any one primitive is independent on an exponent of any other primitive, thus reducing the complexity of a search for such exponents to a number of operations of the order of a sum of such exponents as opposed to their product to obtain a decrypted message as a decrypted electromagnetic signal; determining if there is any threat in the decrypted message as the decrypted electromagnetic signal; and acting on the decrypted message as the decrypted electromagnetic signal with the computer so any threats to property or individuals can be quickly acted upon to eliminate the threat before it occurs and actual damage to property or injury to individuals is prevented or mitigated.

Description

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING

(1) In the accompanying drawings, the preferred embodiment of the invention and preferred methods of practicing the invention are illustrated in which:

(2) FIG. 1 is a block diagram of the apparatus of the claimed invention.

(3) FIG. 2 is a representation of .sub.1.sup.x.sup.1.Math..sub.2.sup.x.sup.2 (mod 70) using orthogonal primitives.

DETAILED DESCRIPTION OF THE INVENTION

(4) Referring now to the drawings wherein like reference numerals refer to similar or identical parts throughout the several views, and more specifically to FIG. 1 thereof, there is shown a decoding apparatus 10. The decoding apparatus 10 comprises a non-transient memory 14 in which is stored an electromagnetic signal representative of data which were encrypted relying on the difficulty of computing discrete logarithms. The decoding apparatus 10 comprises a computer 12 in communication with the memory 14 that decodes the encrypted data in the memory 14 by computing the data's discrete logarithm. The decoding apparatus 10 comprises a display 18 on which the decoded encrypted data are displayed by the computer 12.

(5) The computer 12 may reduce the complexity of an exponential congruence which is defined modulo p, where p=2.Math.p+1, p is also a prime and p1 contains only factors which are smaller than 100,000, and executes a sequence of reversible transformations supported by the non-transient memory 14 in such a way that the exponential congruence modulo p is restated as a problem involving new relationships modulo p and a concurrent independent congruence modulo p1. The computer 12 may select primitives of sub-groups of a group stored in the non-transient memory 14, where the group is defined modulo (p1) in such a way that an exponent of any one primitive is independent on an exponent of any other primitive, thus reducing the complexity of a search for such exponents to a number of operations of the order of a sum of such exponents as opposed to their product.

(6) The present invention pertains to a method for processing an electromagnetic signal representative of encrypted data which were produced relying on the difficulty of computing discrete logarithms. The method comprises the steps of producing the electromagnetic signal by a first computer 12. There is the step of providing the signal to a second computer 22 through an input 20 of the second computer 22. The input 20 can be a keyboard in communication with the second computer 22 or a memory port, such as a USB port that receives a flash drive or a CD reader that receives a CD with the signal; or the input 20 can be a network interface card in communication with the second computer 22 having a network port which is in communication with a network 24 over which the signal is transmitted from the first computer 12. The second computer 22 obtains the signal from the network 24 through the input 20 of the second computer 22. There is the step of storing the encrypted data in a non-transient memory 14 of a second computer 22. There is the step of performing with the second computer 22 in communication with the memory 14 the computer-generated steps of decoding the encrypted data in the memory 14 by computing the data's discrete logarithms, and displaying on a display 18 the decoded data.

(7) The performing step may include the steps of reducing the complexity of an exponential congruence which is defined modulo p, where p=2.Math.p+1, p is also a prime and p1 contains only factors which are smaller than 100,000. There may be the step of executing with the computer a sequence of reversible transformations supported by a non-transient memory 14 in such a way that the exponential congruence modulo p is restated as a problem involving new relationships modulo p and a concurrent independent congruence modulo p1. There may be the step of reporting the restated problem on a display 18. The performing step may include the step of selecting with the computer primitives of sub-groups of a group stored in the non-transient memory 14, where the group is defined modulo (p1) in such a way that an exponent of any one primitive is independent on an exponent of any other primitive, thus reducing the complexity of a search for such exponents to a number of operations of the order of a sum of such exponents as opposed to their product.

(8) The present invention pertains to a computer program 16 stored in a non-transient memory 14 for decoding an electromagnetic signal which is encrypted relying on the difficulty of computing discrete logarithms. The program has the computer-generated steps of storing the encrypted data in a non-transient memory 14. There is the step of decoding the encrypted data in the memory 14 by computing the data's discrete logarithms. There is the step of displaying on a display 18 the decoded data.

(9) The decoding step may include the steps of reducing the complexity of an exponential congruence which is defined modulo p, where p=2.Math.p+1, p is also a prime and p1 contains only factors which are smaller than 100,000. There may be the step of executing with the computer a sequence of reversible transformations supported by a non-transient memory 14 in such a way that the exponential congruence modulo p is restated as a problem involving new relationships modulo p and a concurrent independent congruence modulo p1.

(10) The decoding step may include the steps of selecting with the computer primitives of sub-groups of a group stored in the non-transient memory 14, where the group is defined modulo (p 1) in such a way that an exponent of any one primitive is independent on an exponent of any other primitive, thus reducing the complexity of a search for such exponents to a number of operations of the order of a sum of such exponents as opposed to their product.

(11) The present invention pertains to a method for reducing the complexity of an exponential congruence, preferably for decoding, which is defined modulo p, where p=2.Math.p+1, p is also a prime and p1 contains only factors which are smaller than 100,000. The method comprises the steps of executing with a computer a sequence of reversible transformations supported by a non-transient memory 14 in such a way that the exponential congruence modulo p is restated as a problem involving new relationships modulo p and a concurrent independent congruence modulo p1. There is the step of reporting the restated problem on a display 18.

(12) The present invention pertains to an apparatus 10 for reducing the complexity of an exponential congruence, preferably for decoding, which is defined modulo p, where p=2.Math.p+1, p is also a prime and p1 contains only factors which are smaller than 100,000. The apparatus 10 comprises a non-transient memory 14. The apparatus 10 comprises a computer in communication with the non-transient memory 14 which executes a sequence of reversible transformations supported by the non-transient memory 14 in such a way that the exponential congruence modulo p is restated as a problem involving new relationships modulo p and a concurrent independent congruence modulo p1. The apparatus 10 comprises a display 18 on which the restated problem is reported.

(13) The present invention pertains to a computer program 16 stored in a non-transient memory 14 for reducing the complexity of an exponential congruence, preferably for decoding, which is defined modulo p, where p=2.Math.p+1, p is also a prime and p1 contains only factors which are smaller than 100,000. The program comprises the computer generated steps of executing a sequence of reversible transformations supported by a non-transient memory 14 in such a way that the exponential congruence modulo p is restated as a problem involving new relationships modulo p and a concurrent independent congruence modulo p1. There is the step of reporting the restated problem on a display 18.

(14) The present invention pertains to a method for decoding. The method comprises the steps of selecting with a computer primitives of sub-groups of a group stored in a non-transient memory 14, where the group is defined modulo (p1) in such a way that an exponent of any one primitive is independent on an exponent of any other primitive, thus reducing the complexity of a search for such exponents to a number of operations of the order of a sum of such exponents as opposed to their product. There is the step of reporting the exponents on a display 18.

(15) The present invention pertains to a computer program 16 stored in a non-transient memory 14 for decoding. The program comprises the computer generated steps of selecting primitives of sub-groups of a group stored in a non-transient memory 14, where the group is defined modulo (p1) in such a way that an exponent of any one primitive is independent on an exponent of any other primitive, thus reducing the complexity of a search for such exponents to a number of operations of the order of a sum of such exponents as opposed to their product. There is the step of reporting the exponents on a display 18.

(16) The present invention pertains to an apparatus 10 for decoding. The apparatus 10 comprises a non-transient memory 14. The apparatus 10 comprises a computer in communication with the memory 14 which selects primitives of sub-groups of a group stored in the non-transient memory 14, where the group is defined modulo (p1) in such a way that an exponent of any one primitive is independent on an exponent of any other primitive, thus reducing the complexity of a search for such exponents to a number of operations of the order of a sum of such exponents as opposed to their product. The apparatus 10 comprises a display 18 in communication with the computer on which the exponents are reported.

(17) In the operation of the invention, the following is a description of the solution of (1).

II. THE CASE WHEN .SUB.0.=1. A RESTATEMENT

(18) 1) Step One. Definition of Superprimitives.

(19) In general in (1) a.sub.0 is not a primitive root of X modulo p1. It is convenient to restate (1) in such a way that on the LHS of (1) a.sub.0 be replaced by a primitive of X modulo p1.

(20) If denotes a primitive of X modulo p1, consider the process of raising both sides of (1) by .sup.l. As l increases, a.sub.0.sup..sup.l modulo p traces an orbit of primitives modulo p.

(21) If p is large, and if p=2.Math.p+1, where p is also prime, approximately half of the elements of G are elements of this orbit [2, p. 269].

(22) For some integer {tilde over (l)}, a.sub.0.sup..sup.l is also a primitive of X modulo p1. In this case, define

(23) $\begin{array}{cc}\{\begin{array}{c}{a}_0^{{}^{\stackrel{\_}{i}}}a\left(\mathrm{mod}p\right)\\ y_0^{{}^{\stackrel{}{i}}}y\left(\mathrm{mod}p\right)\end{array}.& \left(5\right)\end{array}$
Then
a.sup.xy(mod p).(6)

(24) An integer which is a primitive root of p and also a primitive of X modulo p1 will be referred to as a superprimitive of p.

(25) Table I shows the superprimitives of a set of small primes (.sub.02).

(26) Table II shows some relevant variables for such primes.

(27) TABLE-US-00001 TABLE I p Superprimitives of p 11 7 23 7, 17, 19 47 5, 11, 15, 19, 33, 43 59 11, 31, 37, 39, 43, 47, 55 107 5, 21, 31, 45, 51, 55, 65, 67, 71, 73, 103 167 5, 13, 15, 35, 39, 43, 45, 53, 55, 67, 71, 73, 79, 91, 101, 103, 105, 117, 125, 129, 135, 139, 143, 145, 149, 155, 159, 163 263 29, 57, 67, 85, 87, 97, 115, 119, 127, 130, 139, 141, 161, 171, 185, 197, 213, 219, 227, 229, 237, 241, 247, 251, 255, 257, 259 347 5, 7, 17, 19, 45, 63, 65, 69, 79, 91, 97, 101, 103, 111, 123, 125, 141, 145, 153, 155, 165, 171, 175, 191, 193, 203, 215, 217, 221, 223, 231, 239, 245, 247, 283, 301, 307, 335, 343, 359 7, 21, 35, 53, 63, 71, 97, 103, 105, 109, 113, 119, 137, 143, 157, 159, 163, 167, 175, 189, 197, 209, 211, 213, 223, 251, 257, 263, 265, 269, 271, 277, 291, 293, 299, 309, 311, 313, 315, 319, 327, 329, 339, 341, 343, 349, 353, 355 383 33, 35, 47, 53, 61, 83, 89, 91, 95, 99, 105, 111, 123, 127, 131, 141, 145, 151, 157, 167, 179, 181, 183, 187, 233, 247, 249, 253, 267, 285, 297, 307, 315, 337, 355, 359, 365, 367, 369, 379 479 13, 19, 37, 39, 41, 43, 47, 53, 57, 59, 65, 79, 95, 117, 119, 123, 129, 143, 149, 159, 171, 177, 179, 185, 191, 205, 209, 223, 227, 235, 237, 265, 281, 285, 295, 317, 325, 333, 351, 353, 357, 369, 379, 387, 391, 395, 423, 429, 433, 447, 449, 451, 461, 463, 467, 469, 473, 475 503 19, 29, 37, 53, 55, 57, 71, 87, 107, 109, 111, 127, 133, 137, 139, 159, 163, 165, 167, 191, 193, 203, 213, 215, 239, 269, 277, 295, 305, 307, 313, 321, 327, 333, 341, 347, 349, 371, 381, 385, 399, 409, 417, 419, 437, 453, 457, 461, 467, 471, 475, 479, 481, 485, 487, 489, 495, 499 587 5, 11, 13, 19, 23, 41, 45, 85, 99, 103, 105, 111, 117, 125, 127, 131, 139, 157, 171, 173, 183, 187, 207, 213, 215, 221, 227, 231, 241, 245, 251, 259, 265, 263, 273, 275, 291, 295, 321, 323, 325, 327, 335, 337, 341, 365, 367, 369, 373, 391, 399, 403, 405, 415, 427, 435, 467, 473, 475, 483, 487, 497, 523, 539, 541, 557, 559, 583

(28) TABLE-US-00002 TABLE II p |A| = |X| |Y| |A Y| |A|/(A Y) 11 4 2 1 4.0000 23 10 4 3 3.3333 47 22 10 6 3.6666 59 28 12 7 4.0000 107 52 24 11 4.7273 167 82 40 28 2.9286 263 130 48 26 5.0000 347 172 84 39 4.4103 359 178 88 48 3.7083 383 190 72 40 4.7500 479 238 96 58 4.1034 503 250 100 58 4.3103 587 292 144 68 4.2941
NOTE 1: If .sub.02, X is cyclic and there exist an integer which is a primitive root of X modulo p1. If p is large, to determine it is sufficient to select any random integer and to verify that a) is an element of X, which means that it is relatively prime to p1, and b) is an element of Y, which means that it is relatively prime to (p1)=p1. The process of producing p should not be long, because, if p is large, the probability that two integers be prime to one another is 6/.sup.2 [2, p. 269]. Thus, the probability that an integer chosen at random be prime to p1 and p1 is approximately (6/.sup.2).sup.2 or 1/2.7055.
NOTE 2: The ratio |A|/|(AY)| is relevant because it is related to the number of trials which should be expected when is employed in the search for a.
NOTE 3: The ratio |A|/|(AY)| may grow when p increases. As an example, when p=6466463=2.Math.p+1 and p=2.Math.5.Math.7.Math.11.Math.13.Math.17.Math.19+1, |A|/|A Y|=7.7931.
NOTE 4: Comparing the data for p.sub.2=6466463 and p.sub.1=587, observe that, when p.sub.1 is replaced by p.sub.2, the ratio |A|/|(AY)| is multiplied by a factor of 7.7931/4.2941, which is less than 2, while 6466463 is greater than 587.sup.2.

(29) 2) Step Two

(30) In general in (6) y is not a primitive root modulo p. It is convenient to restate (6) in such a way that the RHS of (6) be a primitive modulo p. This can be accomplished by multiplying both sides of (6) by a, a sufficient number of times until the desired condition is satisfied. If after {tilde over (r)} iterations this condition is satisfied, let

(31) $\begin{array}{cc}\{\begin{array}{c}b{a}^{\tilde{r}}.Math.y\left(\mathrm{mod}p\right)\\ sx+\tilde{r}\left(\mathrm{mod}\left(p-1\right)\right)\end{array}.& \left(7\right)\end{array}$
Then
a.sup.sb(mod p).(8)

(32) After this restatement the search for x is conducted in a smaller, more structured environment. Since b is a primitive modulo p and a is a primitive of X modulo p1, s is relative prime to p1 and can be represented as follows

(33) $\begin{array}{cc}\{\begin{array}{c}s{a}^t\left(\mathrm{mod}\left(p-1\right)\right)\\ a^{a^{}}b\left(\mathrm{mod}p\right)\end{array},& \left(9\right)\end{array}$
where t denotes an integer and 0t<(p1).

(34) 3) Step Three

(35) Consider the process of raising the second of (9) to a.sup.u modulo p. Let d denote the least positive residue modulo p of the corresponding RHS of (9). As u increases, the integer d describes an orbit of primitives modulo p. It is desired that d be also a primitive of X modulo p1. If, after operations this condition is satisfied, define
a.sup.a.sup.d(mod p)(10)
where

(36) $\begin{array}{cc}\{\begin{array}{c}vt+\tilde{u}\left(\mathrm{mod}\left(p-1\right)\right)\\ d{b}^{a^{\tilde{u}}}\left(\mathrm{mod}p\right)\end{array}.& \left(11\right)\end{array}$

(37) Consider the integer d.sup.d.sup.w, where w denotes an integer. Since d is a primitive modulo p and a primitive of X modulo p1, when w varies d.sup.d.sup.w traces an orbit which contains all the primitives modulo p, including a.

(38) Therefore, there does exist an integer w such that
ad.sup.d.sup.w(mod p).(12)

(39) 4) Conclusion

(40) The exponential congruence (1) is referred to as a one-way transaction, meaning that, when x is known, it is easy to compute a.sub.0.sup.x modulo p, while, when y.sub.0 is known, the computation of x may be untractable. The restatement introduced by this section produces the congruences (10) and (12), which have similar structure and comparable complexity.

(41) In order to determine the relationship between and w, raise (12) to a.sup. modulo p. It will be
a.sup.a.sup.d.sup.a.sup..sup..Math.d.sup.w(mod p)(13)
whence, by (10),
a.sup..Math.d.sup.w1(mod p1)(14)
or
a.sup.d.sup.w(mod p1).(15)
As a conclusion: and w are exponents of known superprimitives of p, a and d, respectively. The integers a.sup. and d.sup.w are related in a congruence which is defined modulo p1.
NOTE 1: In general, given (1), the integers a and d which result from the proposed restatements are not unique.
NOTE 2: In principle, it would be possible to explore the case when a is a superprimitive of p and p1. As an example, 19 is a superprimitive of 47 and 23. However, not all primes have superprimitives modulo p and modulo p1.

III. ORTHOGONAL PRIMITIVES when .SUB.0.=1

(42) Refer to (15). Let V denote the set of integers and w (1, wp1) which are candidate solutions of (10), (12), and (15) and let |V| denote their number.

(43) A) It is desired to represent V as the direct product of distinct subsets of V, each one associated with one of the factors (q.sub.i.sup..sup.1 or 2.sup..sup.0) of p1.

(44) B) It is desired to partition and process independently the corresponding sets of candidate solutions.

(45) To reach these aims:

(46) A) The number of significant candidate elements associated with each of such sets is (q.sub.i.sup..sup.1) . Then the total number of candidate elements, say |V|, would be

(47) $\begin{array}{cc}\left|V\right|=\left(p^{}-1\right)=2^{{}_0-1}.Math.\underset{i=1}{\overset{h}{.Math.}}\left(q_i^{{}_i}\right).& \left(16\right)\end{array}$

(48) The candidate elements associated to (q.sub.i.sup..sup.1), say .sub.l.sup..sup.1, are relatively prime to q.sub.i and can be represented as the elements of a cyclic group having .sub.i as its generator.

(49) Notice that, thus far, nothing has been stated concerning the divisibility of .sub.i by q.sub.j when ij.

(50) B) Consider the case when and w are represented as the direct product of their component subgroups. In the case when .sub.0=1, .sub.01=0. In order to process independently the cyclic subsets of V, consider the case when the primitive of the cycle i is defined as follows:

(51) $\begin{array}{cc}{}_i=1+{}_i.Math.\left(p-1\right)/q_i^{{}_i}={}_i+{}_i.Math.q_i^{{}_i}& \left(17\right)\end{array}$
where .sub.i denotes any primitive modulo q.sub.i and (.sub.i, .sub.i) denotes a pair of integers. Given .sub.i, the pair (.sub.i, .sub.i) can be any one of the solution pairs of the following:
.sub.i1+.sub.i.Math.q.sub.i.sup..sup.1=.sub.i.Math.(p1)/q.sub.i.sup..sup.1.(18)
Given any solution pair ({tilde over ()}.sub.i, {tilde over ()}.sub.i), its substitution into (17) produces .sub.i modulo (p1). After this restatement, .sub.i is relatively prime to (p1).

(52) Consider the case when p1 has a structure of the form (2) or (3), that is a) 5 is the smallest odd prime divisor of p1, and b) each divisor q.sub.i is the smallest odd prime greater than q.sub.i1.

(53) Under these conditions, all the odd prime divisors of (p1), with the exception of 3, are also divisors of (p1). It is possible to select .sub.i in such a way that .sub.i is not a multiple of 3. In this case, .sub.i.sup..sup.1 is relatively prime with (p1) and (p1).

(54) Thus, when p1 has the structure of (8) and (10) and is relatively prime with (p1) and 3, it is possible to represent and w as follows

(55) $\begin{array}{cc}\{\begin{array}{c}\underset{i=1}{\overset{h}{.Math.}}{}_j^{{}_i}\left(\mathrm{mod}\left(p-1\right)\right)\\ w\underset{l=1}{\overset{h}{.Math.}}{}_i^{w_i}\left(\mathrm{mod}\left(p-1\right)\right),\end{array}& \left(19\right)\end{array}$
where .sub.i and w.sub.i denote integers defined modulo (q.sub.i.sup..sup.1).
It will be

(56) $\begin{array}{cc}\{\begin{array}{c}\frac{\left(p-1\right)}{q_i^{{}_i}}.Math.{}_j\frac{\left(p-1\right)}{q_i^{{}_i}}\left(\mathrm{mod}\left(p-1\right)\right)\mathrm{for}ij\\ \frac{\left(p-1\right)}{q_i^{{}_i}}.Math.{}_j\frac{\left(p-1\right)}{q_i^{{}_i}}.Math.{}_j\left(\mathrm{mod}\left(p-1\right)\right)\mathrm{for}i=j.\end{array}& \left(20\right)\end{array}$

(57) The congruences (20) define the orthogonality between .sub.i and .sub.j, for ij, and validate the definition of .sub.i offered by (17).

(58) Notice that the definitions (17) imply that

(59) $\begin{array}{cc}{}_i^{\left(q_l^{{}_l}\right)}1\left(\mathrm{mod}\left(p-1\right)\right).& \left(21\right)\end{array}$

(60) In fact,

(61) 0$\begin{array}{cc}{}_i^{\left(q_i^{{}_i}\right)}={\left({}_i+{}_i.Math.q_i^{{}_i}\right)}^{\left(q_i^{{}_i}\right)}1+{}_i.Math.q_i^{{}_i}\left(\mathrm{mod}{q}_i^{{}_i}\right)& \left(22\right)\end{array}$
and also, for all positive integers n,

(62) $\begin{array}{cc}{}_i^n={\left(1+{}_i.Math.\left(p-1\right)/q_i^{{}_i}\right)}^n=1+{}_i.Math.\left(p-1\right)q_i^{{}_i}& \left(23\right)\end{array}$
for some .sub.i and .sub.i integers. Combining (22) and (23), (21) follows.
Refer to Section I of the Appendix.

IV. THE RELATIONSHIP BETWEEN .SUB.i .AND w.SUB.i .MODULO (q.SUB.i..SUP...SUP.i) WHEN .SUB.0.=1

(63) Using orthogonal primitives (17), consider raising (15) to

(64) $\frac{\left(p-1\right)}{q_i^{{}_i}}$
modulo p1.
It will be

(65) $\begin{array}{cc}{\left(a^{\frac{\left(p-1\right)}{q_i^{{}_i}}}\right)}^{{}_i^{v_i}}{\left(d^{\frac{\left(p-1\right)}{q_i^{{}_i}}}\right)}^{-{}_i^{w_i}}\left(\mathrm{mod}\left(p-1\right)\right).& \left(24\right)\end{array}$

(66) Let

(67) $\begin{array}{cc}\{\begin{array}{c}{}_i{a}^{\frac{\left(p-1\right)}{q_i^{{}_i}}}\left(\mathrm{mod}\left(p-1\right)\right)\\ {}_i{d}^{\frac{\left(p-1\right)}{q_i^{{}_i}}}\left(\mathrm{mod}\left(p-1\right)\right)\end{array}.& \left(25\right)\end{array}$

(68) Then

(69) $\begin{array}{cc}{}_i^{{}_i^{v_i}}{}_i^{-{}_i^{w_i}}\left(\mathrm{mod}\left(p-1\right)\right).& \left(26\right)\end{array}$

(70) This congruence establishes a relationship between .sub.i and w.sub.i which does not depend on any of the values of .sub.j and w.sub.j, for ij . In fact, given {tilde over (v)}.sub.i, the condition (26) defines {tilde over (w)}.sub.i modulo (q.sub.i.sup..sup.1).

(71) NOTE 1: In (26), let w.sub.i, m denote the value of w.sub.i when .sub.i0(mod (q.sub.i.sup..sup.1)). Then

(72) $\begin{array}{cc}{}_i^{-1}{}_i^{{}_i^{w_{i,m}}}\left(\mathrm{mod}p-1\right).& \left(27\right)\end{array}$
Likewise, let .sub.i, m denote the value of .sub.i when w.sub.i0(mod (q.sub.i.sup..sup.1)). Then

(73) $\begin{array}{cc}{}_i^{{}_i^{v_{i,m}}}{}_i^{-1}\left(\mathrm{mod}p-1\right).& \left(28\right)\end{array}$
NOTE 2: Consider the case when all the .sub.j's are congruent to zero modulo (q.sub.j.sup..sup.j). In this case, from (15),

(74) $\begin{array}{cc}{a}^{-1}{d}^{\underset{j=1}{\overset{h}{.Math.}}{}_j^{w_{j,m}}}\left(\mathrm{mod}p-1\right).& \left(29\right)\end{array}$
Let

(75) $\begin{array}{cc}W=\underset{j=1}{\overset{h}{.Math.}}{}_j^{w_{j,m}}.& \left(30\right)\end{array}$
Then
a.sup.1d.sup.W(mod p1).(31)

(76) Likewise, consider the case when all the w.sub.j's are congruent to zero modulo (q.sub.j.sup.249.sup.j). In this case

(77) 0$\begin{array}{cc}{a}^{\stackrel{h}{\underset{j=1}{.Math.}}{}_j^{{}_{j,m}}}{d}^{-1}\left(\mathrm{mod}p-1\right).& \left(32\right)\end{array}$

(78) Let

(79) $\begin{array}{cc}U=\underset{j=1}{\overset{h}{.Math.}}{}_j^{v_{j,m}}.& \left(33\right)\end{array}$

(80) Then
a.sup.Ud.sup.1(mod p1).(34)
NOTE 3: Consider the case when all the .sub.j's other than .sub.i are congruent to zero modulo (q.sub.j.sup..sup.j) .
Assume {tilde over ()}.sub.i0 (mod (q.sub.i.sup..sup.i)) and .sub.j0 (mod (q.sub.j.sup..sup.j)) for ij . In this case, using (31), it will be

(81) $\begin{array}{cc}{a}^{-{}_{\mathrm{.Math.}}^{{\stackrel{~}{}}_i}}{d}^{{}_{\mathrm{.Math.}}^{{\tilde{w}}_i}.Math.\left(W/{}_{\mathrm{.Math.}}^{w_{\mathrm{.Math.},m}}\right)}\left(\mathrm{mod}p-1\right).& \left(35\right)\end{array}$
By (31)

(82) $\begin{array}{cc}{d}^{W.Math.{}_{\mathrm{.Math.}}^{v_i}}{d}^{W/{}_{\mathrm{.Math.}}^{w_{\mathrm{.Math.},m}}}.Math.d^{{}_{\mathrm{.Math.}}^{w_i}}\left(\mathrm{mod}p-1\right).& \left(36\right)\end{array}$
Then
.sub.i.sup.w.sup.l, m.Math..sub.i.sup.v.sup.i.sub.i.sup.w.sup.i(mod (p1)),(37)
or
w.sub.i, m+v.sub.iw.sub.i0(mod (q.sub.i.sup..sup.i)).(38)
NOTE 4: In a similar fashion, consider the case when all the w.sub.j other then w.sub.i are congruent to zero modulo (q.sub.j.sup..sup.j).

(83) Assume w.sub.j0 (mod q.sub.i.sup..sup.i) for ji. In this case, using (32), it will be

(84) $\begin{array}{cc}{a}^{{}_{\mathrm{.Math.}}^{{}_i}}.Math.U/{}_i^{V_{\mathrm{.Math.},m}}{d}^{-{}_{\mathrm{.Math.}}^{w_i}}& \left(39\right)\end{array}$
By (32)
.sub.i.sup.v.sup.l.sub.i.sup.v.sup.l, m.Math..sub.i.sup.w.sup.l(40)
or
v.sub.iw.sub.i+v.sub.i, m(mod (q.sub.j.sup..sup.j)).(41)

(85) Compare (38) and (41):
w.sub.i, m=v.sub.i, m(mod (q.sub.j.sup..sup.j)).(42)
As a conclusion:

(86) There exists a linear relationship between v.sub.i and w.sub.i modulo (q.sub.j.sup..sup.j).

V. THE TRIAD

(87) Given a pair (a, d), after the determination of the corresponding relationships (v.sub.i, w.sub.i), it is interesting to explore comparable relationships for a pair (d, g), where g is a superprimitive modulo p.

(88) Let (v.sub.i(A, D), w.sub.i(A, D)) denote the pair (v.sub.i, w.sub.i) associated with the pair (a, d).

(89) Likewise, let (v.sub.i(D, G), w.sub.i(D, G)) denote the pair (v.sub.i, w.sub.i) associated with the pair (d, g).

(90) Then, by (26),

(91) $\begin{array}{cc}\{\begin{array}{c}{}_i^{{}_i^{v_i\left(A,D\right)}}.Math.{}_i^{{}_i^{w_i\left(A,D\right)}}1\left(\mathrm{mod}p-1\right)\\ {}_i^{{}_i^{v_i\left(D,G\right)}}.Math.{}_i^{{}_i^{w_i\left(D,G\right)}}1\left(\mathrm{mod}p-1\right)\end{array},& \left(43\right)\end{array}$$\mathrm{where}$$\begin{array}{cc}{}_i{g}^{\frac{\left(p-1\right)}{q_i^{{}_i}}}\left(\mathrm{mod}\left(p-1\right)\right).& \left(44\right)\end{array}$

(92) Raising the first of (43) to .sub.i.sup.v.sup.i.sup.(D, G) and the second to .sub.i.sup.w.sup.i.sup.(A, D) modulo p1 yields

(93) $\begin{array}{cc}\{\begin{array}{c}{}_i^{{}_i^{v_i\left(A,D\right)+v_i\left(D,G\right)}}.Math.{}_i^{{}_i^{w_i\left(A,D\right)+v_i\left(D,G\right)}}1\left(\mathrm{mod}\left(p-1\right)\right)\\ {}_i^{{}_i^{w_i\left(A,D\right)+v_i\left(D,G\right)}}.Math.{}_i^{{}_i^{w_i\left(A,D\right)+w_i\left(D,G\right)}}1\left(\mathrm{mod}\left(p-1\right)\right)\end{array}& \left(45\right)\end{array}$$\mathrm{whence}$$\begin{array}{cc}{}_i^{{}_i^{v_i\left(A,D\right)+v_i\left(D,G\right)}}{}_i^{{}_i^{w_i\left(A,D\right)+w_i\left(D,G\right)}}\left(\mathrm{mod}\left(p-1\right)\right).& \left(46\right)\end{array}$
This congruence establishes a relationship between .sub.i and w.sub.i which does not depend on any of the values of .sub.j and w.sub.j, for ij. However, this relationship does not identify the value of .sub.i which is consistent with (6).
NOTE 1: In general, in (27) w.sub.i, m depends on the pair (a, d). Therefore, it will be necessary to distinguish w.sub.i, m (A, D) from w.sub.i, m (D, G). The same observation applies to v.sub.i, m (A, D) and v.sub.i, m (D, G).
NOTE 2: a and d are primitives modulo p1. Therefore, they are relatively prime with (p1). When a or d are raised to a divisor of (p1), such as (p1)/q.sub.i.sup..sup.1, they produce primitives modulo (p1) for the sets {.sub.i.sup.v.sup.1} and {.sub.i.sup.w.sup.1}, respectively.

VI. INVERTIBLE SUPERPRIMITIVES

(94) 1) Introduction

(95) Thus far, given a pair (a, d), the relationships between the sets {.sub.i} and {w.sub.i} have been based on the condition (14).

(96) It should be emphasized the fact that (14) is defined modulo (p1) and is only a necessary condition for the solution of (10) and (12). It does not produce the solution of (10) and (12) because no adequate link has been produced between the domain modulo p1 and the domain modulo p.

(97) To this end, this Section introduces the notion of Invertible Superprimitive.

(98) 2) Definition

(99) A superprimitive of p is defined as invertible if its inverse modulo p is also a superprimitive of p. In general, only some of the superprimitives are invertible. Table III shows the invertible superprimitives of the set of primes which are included in Tables I and II. This congruence establishes a relationship between .sub.i and w.sub.i which does not depend on any of the values of .sub.j and w.sub.j, for ij.

(100) TABLE-US-00003 TABLE III Number of Invertible Number of Invertible p Superprimitives of p Superprimitives Superprimitives Superprimitives Ratio 11 7 1 0 0. 23 7, 17, 19 17, 19 3 2 0.666667 47 5, 11, 15, 19, 33, 43 5, 19 6 2 0.333333 59 11, 31, 37, 39, 43, 47, 55 11, 43 7 2 0.285714 107 5, 21, 31, 45, 51, 55, 65, 67, 71, 73, 103 21, 51 11 2 0.181818 167 5, 13, 15, 35, 39, 43, 45, 53, 55, 67, 71, 73, 79, 5, 35, 43, 67, 101, 105, 28 10 0.357143 91, 101, 103, 105, 117, 125, 129, 135, 139, 143, 125, 129, 145, 163 145, 149, 155, 159, 163 263 29, 57, 67, 85, 87, 97, 115, 119, 127, 130, 139, 29, 97, 115, 127, 141, 26 12 0.461538 141, 161, 171, 185, 197, 213, 219, 227, 229, 197, 219, 241, 247, 237, 241, 247, 251, 255, 257, 259 251, 257, 259 347 5, 7, 17, 19, 45, 63, 65, 69, 79, 91, 97, 101, 103, 17, 69, 79, 103, 39 8 0.205128 111, 123, 125, 141, 145, 153, 155, 165, 171, 123, 171, 245, 283 175, 191, 193, 203, 215, 217, 221, 223, 231, 239, 245, 247, 283, 301, 307, 335, 343, 359 7, 21, 35, 53, 63, 71, 97, 103, 105, 109, 113, 157, 197, 209, 213, 48 16 0.333333 119, 137, 143, 157, 159, 163, 167, 175, 189, 223, 257, 269, 271, 197, 209, 211, 213, 223, 251, 257, 263, 265, 277, 293, 299, 339, 269, 271, 277, 291, 293, 299, 309, 311, 313, 341, 343, 353, 355 315, 319, 327, 329, 339, 341, 343, 349, 353, 355 383 33, 35, 47, 53, 61, 83, 89, 91, 95, 99, 105, 111, 359, 367 40 2 0.05 123, 127, 131, 141, 145, 151, 157, 167, 179, 181, 183, 187, 233, 247, 249, 253, 267, 285, 297, 307, 315, 337, 355, 359, 365, 367, 369, 379 479 13, 19, 37, 39, 41, 43, 47, 53, 57, 59, 65, 79, 95, 19, 47, 53, 177, 235, 58 12 0.206897 117, 119, 123, 129, 143, 149, 159, 171, 177, 265, 325, 353, 433, 179, 185, 191, 205, 209, 223, 227, 235, 237, 449, 451, 463 265, 281, 285, 295, 317, 325, 333, 351, 353, 357, 369, 379, 387, 391, 395, 423, 429, 433, 447, 449, 451, 461, 463, 467, 469, 473, 475 503 19, 29, 37, 53, 55, 57, 71, 87, 107, 109, 111, 19, 53, 133, 193, 213, 58 14 0.241379 127, 133, 137, 139, 159, 163, 165, 167, 191, 295, 305, 307, 409, 193, 203, 213, 215, 239, 269, 277, 295, 305, 417, 467, 475, 485, 307, 313, 321, 327, 333, 341, 347, 349, 371, 489 381, 385, 399, 409, 417, 419, 437, 453, 457, 461, 467, 471, 475, 479, 481, 485, 487, 489, 495, 499 587 5, 11, 13, 19, 23, 41, 45, 85, 99, 103, 105, 111, 11, 85, 111, 117, 215, 69 16 0.231884 117, 125, 127, 131, 139, 157, 171, 173, 183, 221, 241, 275, 291, 187, 207, 213, 215, 221, 227, 231, 241, 245, 321, 341, 415, 427, 251, 259, 265, 263, 273, 275, 291, 295, 321, 435, 475, 523 323, 325, 327, 335, 337, 341, 365, 367, 369, 373, 391, 399, 403, 405, 415, 427, 435, 467, 473, 475, 483, 487, 497, 523, 539, 541, 557, 559, 583
Consider the case when a denotes an invertible superprimitive, and let g denote its inverse modulo p. Then, for some integers and w, the conditions (10) and (12) take the following forms:
a.sup.a.sup.a.sup.1(mod p)(47)
and
g.sup.1g.sup.g.sup.w(mod p).(48)
Therefore,
a.sup.a.sup..sup.+11(mod p)(49)
whence
a.sup.+10(mod p1)(50)
or
a.sup.2.Math.1(mod(p1))(51)

(101) Similarly,
g.sup.2.Math.w1(mod(p1)) .(52)
Then
2.Math.0(mod (p1))(53)
and
2.Math.w0(mod (p1)).(54)
NOTE 1: In (53) and (54), v and w cannot be represented as in (19), because, by (17), .sub.i must be relative prime to (p1). Thus (19) is applicable only if

(102) $\begin{array}{cc}\{\begin{array}{c}gcd\left(v,\left(p-1\right)\right)=1\\ gcd\left(w,\left(p-1\right)\right)=1.\end{array}& \left(55\right)\end{array}$
NOTE 2: Compare (56) with (46). The congruence (46) establishes a necessary condition which relates v.sub.i(A, G) and w.sub.i(A, G). For ga.sup.1(mod p), (46) constrains the values of v(A, G) and w(A, G) to be congruent to each other modulo (p1) and also to be congruent to zero modulo (p1).

(103) These properties will be fundamental in the search for a solution of the problem.

APPENDIX A

NOTES ON ORTHOGONAL PRIMITIVES

(104) I. AN EXAMPLE FOR p1 CONTAINING ONLY SMALL PRIMES

(105) Let
a.sup.xb(mod 71),(A.1)
where a and b are primitive roots modulo 71.
Then x is an element of the set X, containing all the integers which are relatively prime to p1=70=2.Math.5.Math.7.
Let

(106) $\begin{array}{cc}\begin{array}{c}p-1=2.Math.q_1.Math.q_2\\ =2.Math.5.Math.7.\end{array}& \left(A\text{.2}\right)\end{array}$

(107) The order of X is (70)=(5).Math.(7)=24. The exponent of X is e(X)=1 cm(4, 6)=12. Then X can be described as the direct product of a cyclic subgroup of order 2 and a cyclic subgroup of order 12 as follows:
X=C.sub.1(2)C.sub.2(12).(A.3)

(108) Also, the elements of X can be represented by using orthogonal primitives. In this case, given a selection of .sub.1(mod 7) and .sub.2(mod 5), .sub.1(mod 70) and .sub.2(mod 70) can be computed by letting

(109) $\begin{array}{cc}{}_1=1+{}_1.Math.\frac{p-1}{q_1}={}_1+{}_1.Math.q_1& \left(A.4\right)\end{array}$$\mathrm{and}$$\begin{array}{cc}{}_2=1+{}_2.Math.\frac{p-1}{q_2}={}_2+{}_2.Math.q_2.& \left(A.5\right)\end{array}$

(110) For .sub.13(mod 5) and .sub.25(mod 7) , it will be

(111) 0$\begin{array}{cc}\{\begin{array}{c}{}_{1}43\left(\mathrm{mod}70\right)\\ {}_{2}61\left(\mathrm{mod}70\right).\end{array}& \left(A\text{.6}\right)\end{array}$
Then
x43.sup.x.sup.1.Math.61.sup.x.sup.2(mod70).(A.7)

(112) Given a pair (a, b), to solve (A.1), observe that, by (A.3) and (A.4),

(113) $\begin{array}{cc}\{\begin{array}{c}\frac{70}{7}.Math.{}_1\frac{70}{7}.Math.{}_1.Math.\left(\mathrm{mod}70\right)\\ \frac{70}{7}.Math.{}_2\frac{70}{7}\left(\mathrm{mod}70\right).\end{array}& \left(A\text{.8}\right)\end{array}$

(114) Therefore, raising (A.1) to 10 (modulo 71) yields

(115) $\begin{array}{cc}{\left(a^{10}\right)}^{5^{x_1}}{b}^{10}\left(\mathrm{mod}71\right).& \left(A\text{.9}\right)\end{array}$

(116) Likewise, raising (A.1) to 14 (modulo 71) yields

(117) $\begin{array}{cc}{\left(a^{14}\right)}^{3^{x_2}}{b}^{14}\left(\mathrm{mod}71\right).& \left(A\text{.10}\right)\end{array}$
Then (A.7) produces x.
Therefore, in the example, x.sub.2 and x.sub.1 can be determined independently of each other.
FIG. 1 shows the elements of X as intersections of vertical and horizontal straight lines through 61.sup.x.sup.2(mod 70) and 43.sup.x.sup.1(mod 70), respectively.

(118) It is apparent that the elements on a vertical line (constant x.sub.2) are congruent to one another modulo 14=2.Math.7. Likewise, the elements on a horizontal line are congruent to one another modulo 2.Math.5=10.

(119) Also, each elements of X is the product of its horizontal and vertical components.

(120) Different selections of the primitives .sub.1 and .sub.2 would cause appropriate permutations of the vertical and horizontal lines, respectively.

APPENDIX B

THE ORDER OF .SUB.0.32 4.Math.ODD+1 MODULO 2.SUP...SUP.0

(121) When .sub.0=4.Math.ODD+1, the order of .sub.0 modulo 2.sup..sup.0 equals 2.sup..sup.0.sup.2:

(122) $\begin{array}{cc}{}_0^{2^{{}_0-2}}1\left(\mathrm{mod}{2}^{{}_0}\right).& \left(B\text{.1}\right)\end{array}$

(123) Consider the case when .sub.0=4.Math.ODD+1. Then

(124) $\begin{array}{cc}\{\begin{array}{c}{}_{0}4.Math.\left(2.Math.k+1\right)+1\left(\mathrm{mod}{2}^{{}_0}\right)\\ 1+2^2+8.Math.k\left(\mathrm{mod}{2}^{{}_0}\right)\\ {}_0^{2}1+2^3+16.Math.k_1\left(\mathrm{mod}{2}^{{}_0}\right)\\ {}_0^{4}1+2^4+32.Math.k_2\left(\mathrm{mod}{2}^{{}_0}\right)\\ \mathrm{.Math..Math..Math..Math..Math..Math..Math..Math..Math..Math..Math.}\\ {}_0^{2^{{}_0-3}}1+2^{{}_0-1}\left(\mathrm{mod}{2}^{{}_0}\right)\\ {}_0^{2^{{}_0-2}}1\left(\mathrm{mod}{2}^{{}_0}\right).\end{array}& \left(B\text{.2}\right)\end{array}$
(k, k.sub.1, k.sub.2 integers).

(125) Notice that the integer .sub.0,01+2.sup..sup.0.sup.1 cannot be produced as a power of .sub.0.

(126) By using the methods described herein, the encrypted data in the memory is decoded in a time of an order of log log p.Math.log.sup.2p by computing the data's discrete logarithm. This speed is important, which only the operation of the second computer performing the second computer generated steps can achieve, because by having this speed for factoring, the signal representative of an encrypted message can be effectively decrypted and deciphered in real time so any threat to property or individuals can be quickly acted upon to eliminate the threat before it occurs and actual damage to property or injury to individuals is prevented or mitigated. In other words, for an encrypted message to be effectively understood, it must by decrypted fast enough that any threat identified in the signal can be stopped. The present invention with the use of the second computer allows for this capability. Here, it is inherent that to save lives if required, the second computer is required.

(127) There may be the step of obtaining the electromagnetic signal representative of a message from a telecommunications network, or a data network or an Internet or a non-transient memory. Law enforcement departments, such as Homeland Security, the FBI, the CIA, NSA, state and local Police or the Military have the well-known capability of obtaining or intercepting messages sent encrypted by a first computer operated by a potential terrorist or criminal as an electromagnetic signal, such as by smart phone or computer or internet, or stored in the memory of a smart phone or computer, or a flash drive. The encrypted electromagnetic signal can be extracted from such messages or memories and operated upon by the techniques described herein to decrypt the encrypted messages and read them to determine whether there is any violation of law or threat to property or individuals. Of course, the intended recipient of the encrypted message by the first computer has the key so the recipient can decrypt the encrypted message the recipient has received and understand it. It is the object of this invention, and the problem this invention solves, to allow a recipient of the encrypted message who does not have the key to read it, to determine what the key is by the techniques described here to compute the data's discrete logarithm, and then using the determined key, decrypting the encrypted message, reviewing what the decrypted message says, and acting as necessary to protect property damage or bodily injury or any type of crime, as deemed appropriate.

(128) Although the invention has been described in detail in the foregoing embodiments for the purpose of illustration, it is to be understood that such detail is solely for that purpose and that variations can be made therein by those skilled in the art without departing from the spirit and scope of the invention except as it may be described by the following claims.

REFERENCES, all of which are incorporated by reference herein.

(129) [1] T. M. Apostol, Introduction to Analytic Number Theory, New York, NY: Springer-Verlag, 1976. [2] G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, Oxford, UK: Clarendon Press, 1979. [3] S. C. Pohlig, M. E. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and its Cryptographic Significance, IEEE Trans, Inform. Theory, Vol IT-24, pp. 106-110, 1978.