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

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.

I. FIELD OF THE INVENTION

The present invention considers the exponential congruence
a0x≡y0(modp)  (1)
where p is prime and a0is a primitive root modulo p. Since a0is primitive, x and y0are in a one-to-one correspondence for integer values in the range 1≤x, y0≤p−1 [3]. Let G denote the set of integers {1, 2, . . . , p−1} and let |G| denote their number. Given p and a0and given y0in G, it is desired to find x modulo p−1. The integer x is usually referred to as the discrete logarithm of y0in base a0modulo p. (As used herein, references to the “present invention” or “invention” relate to exemplary embodiments and not necessarily to every embodiment encompassed by the appended claims.)

BACKGROUND OF THE INVENTION

Pohlig and Hellman discussed the significance of this problem for cryptographic systems [3]. It was concluded by Pohlig and Hellman that, if p−1 has only small prime factors, x can be computed in a time of the order of log2p. However, if p−1 has a large prime factor p′, the search for x requires a time of the order p′·log p and may be untractable. As an illustration, Pohlig and Hellman presented two large primes of the form p=2·p′+1, where p′ is also prime and where
p′=213·5·7·11·13·17·19·23·29·31·37·41·43·47·53·59+1  (2)
or
p′=2121·52·72·112·13·17·19·23·29·31·37·41·43·47·53·59+1  (3)

In general, let p=2·p′+1, where p′ is prime and
p′−1=2ε0·q1ε1·q2ε2· . . . ·qiεi· . . . ·qhεh,  (4)
where ε0≥1 and, for 1≤i≤h, qidenotes an odd prime and εi>0. Also, for 1≤i<h, 2<qi<qi+1.
NOTE 1: Pohlig and Hellman observed that q1≠3. In fact p=2·p′+1=2·(p′−1)+3. Since p is prime, it must be gcd (3, p′−1)=1.
NOTE 2: Let X denote the set of elements of G which are relatively prime to p−1 and let A denote the set of primitive roots modulo p. Then |X|=|A|=φ(p−1) , where φ(n) denotes the Euler totient function.
NOTE 3: The elements of X form a commutative (abelian) group under the operation of multiplication modulo p−1. An integer m≥1 has a primitive root if and only if m=1, 2, 4, pdor 2·pd, where p is prime number and a is a positive integer [1, p. 211]. When X is cyclic, there exist integers ρ which are primitive roots of X modulo p−1. When primitive roots of X exist, let Y denote the set of elements of X which are primitive roots of X modulo p−1.
NOTE 4: Section VIII below shows that, when p′−1 can be described as in (4), X is cyclic only if ε0<3

BRIEF SUMMARY OF THE INVENTION

The present invention introduces an algorithm which, when p=2·p′+1, p′ is prime and p′−1 contains only small prime factors, produces the solution of (1) in a time of the order of loglog p·log2p.

The present invention pertains to a decoding apparatus. The decoding apparatus comprises 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 comprises 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 comprises a display on which the decoded encrypted data are displayed by the computer.

The present invention pertains to a method for processing an electromagnetic signal representative of encrypted data which were produced relying on the difficulty of computer discrete logarithms, comprising a first computer. The method comprises the steps of storing the encrypted data in a non-transient memory of a second computer. There is the step of performing with the second computer in communication with the memory the computer-generated steps of decoding the encrypted data in the memory by computing the data's discrete logarithms, and displaying on a display the decoded data.

The present invention pertains to a computer program stored in a non-transient memory 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. There is the step of decoding the encrypted data in the memory by computing the data's discrete logarithms. There is the step of displaying on a display the decoded data.

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·p′+1, p′ is also a prime and p′−1 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 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 p−1. There is the step of reporting the restated problem on a display.

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, 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. There is the step of reporting the exponents on a display.

DETAILED DESCRIPTION OF THE INVENTION

Referring now to the drawings wherein like reference numerals refer to similar or identical parts throughout the several views, and more specifically toFIG.1thereof, there is shown a decoding apparatus10. The decoding apparatus10comprises a non-transient memory14in which is stored an electromagnetic signal representative of data which were encrypted relying on the difficulty of computing discrete logarithms. The decoding apparatus10comprises a computer12in communication with the memory14that decodes the encrypted data in the memory14by computing the data's discrete logarithm. The decoding apparatus10comprises a display18on which the decoded encrypted data are displayed by the computer12.

The computer12may reduce the complexity of an exponential congruence which is defined modulo p, where p=2·p′+1, p′ is also a prime and p′−1 contains only factors which are smaller than 100,000, and executes a sequence of reversible transformations supported by the non-transient memory14in 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 p−1. The computer12may select primitives of sub-groups of a group stored in the non-transient memory14, 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.

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 computer12. There is the step of providing the signal to a second computer22through an input20of the second computer22. The input20can be a keyboard in communication with the second computer22or 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 input20can be a network interface card in communication with the second computer22having a network port which is in communication with a network24over which the signal is transmitted from the first computer12. The second computer22obtains the signal from the network24through the input20of the second computer22. There is the step of storing the encrypted data in a non-transient memory14of a second computer22. There is the step of performing with the second computer22in communication with the memory14the computer-generated steps of decoding the encrypted data in the memory14by computing the data's discrete logarithms, and displaying on a display18the decoded data.

The performing step may include the steps of reducing the complexity of an exponential congruence which is defined modulo p, where p=2·p′+1, p′ is also a prime and p′−1 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 memory14in 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 p−1. There may be the step of reporting the restated problem on a display18. The performing step may include the step of selecting with the computer primitives of sub-groups of a group stored in the non-transient memory14, 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.

The present invention pertains to a computer program16stored in a non-transient memory14for 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 memory14. There is the step of decoding the encrypted data in the memory14by computing the data's discrete logarithms. There is the step of displaying on a display18the decoded data.

The decoding step may include the steps of reducing the complexity of an exponential congruence which is defined modulo p, where p=2·p′+1, p′ is also a prime and p′−1 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 memory14in 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 p−1.

The decoding step may include the steps of selecting with the computer primitives of sub-groups of a group stored in the non-transient memory14, 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.

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·p′+1, p′ is also a prime and p′−1 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 memory14in 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 p−1. There is the step of reporting the restated problem on a display18.

The present invention pertains to an apparatus10for reducing the complexity of an exponential congruence, preferably for decoding, which is defined modulo p, where p=2·p′+1, p′ is also a prime and p′−1 contains only factors which are smaller than 100,000. The apparatus10comprises a non-transient memory14. The apparatus10comprises a computer in communication with the non-transient memory14which executes a sequence of reversible transformations supported by the non-transient memory14in 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 p−1. The apparatus10comprises a display18on which the restated problem is reported.

The present invention pertains to a computer program16stored in a non-transient memory14for reducing the complexity of an exponential congruence, preferably for decoding, which is defined modulo p, where p=2·p′+1, p′ is also a prime and p′−1 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 memory14in 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 p−1. There is the step of reporting the restated problem on a display18.

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 memory14, 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. There is the step of reporting the exponents on a display18.

The present invention pertains to a computer program16stored in a non-transient memory14for decoding. The program comprises the computer generated steps of selecting primitives of sub-groups of a group stored in a non-transient memory14, 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. There is the step of reporting the exponents on a display18.

The present invention pertains to an apparatus10for decoding. The apparatus10comprises a non-transient memory14. The apparatus10comprises a computer in communication with the memory14which selects primitives of sub-groups of a group stored in the non-transient memory14, 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. The apparatus10comprises a display18in communication with the computer on which the exponents are reported.

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

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

In general in (1) a0is not a primitive root of X modulo p−1. It is convenient to restate (1) in such a way that on the LHS of (1) a0be replaced by a primitive of X modulo p−1.

If ρ denotes a primitive of X modulo p−1, consider the process of raising both sides of (1) by ρl. As l increases, a0ρlmodulo p traces an orbit of primitives modulo p.

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

For some integer {tilde over (l)}, a0ρlis also a primitive of X modulo p−1. In this case, define

An integer which is a primitive root of p and also a primitive of X modulo p−1 will be referred to as a superprimitive of p.

Table I shows the superprimitives of a set of small primes (ε0≤2).

Table II shows some relevant variables for such primes.

TABLE IIp|A| = |X||Y||A ∩ Y||A|/(A ∩ Y)114214.00002310433.333347221063.666659281274.00001075224114.72731678240282.928626313048265.000034717284394.410335917888483.708338319072404.750047923896584.1034503250100584.3103587292144684.2941
NOTE 1: If ε0≤2, X is cyclic and there exist an integer ρ which is a primitive root of X modulo p−1. 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 p−1, and b) ρ is an element of Y, which means that it is relatively prime to φ(p−1)=p′−1. 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/π2[2, p. 269]. Thus, the probability that an integer chosen at random be prime to p−1 and p′−1 is approximately (6/π2)2or 1/2.7055.
NOTE 2: The ratio |A|/|(A∩Y)| 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|/|(A∩Y)| may grow when p increases. As an example, when p=6466463=2·p′+1 and p′=2·5·7·11·13·17·19+1, |A|/|A ∩Y|=7.7931.
NOTE 4: Comparing the data for p2=6466463 and p1=587, observe that, when p1is replaced by p2, the ratio |A|/|(A∩Y)| is multiplied by a factor of 7.7931/4.2941, which is less than 2, while 6466463 is greater than 5872.

2) Step Two

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

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 p−1, s is relative prime to p−1 and can be represented as follows

{s≡at(mod⁢(p-1))aa′≡b⁡(mod⁢p),(9)
where t denotes an integer and 0≤t<φ(p−1).

3) Step Three

Consider the process of raising the second of (9) to aumodulo 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 p−1. If, after ũ operations this condition is satisfied, define
aaν≡d(modp)  (10)
where

Consider the integer ddw, where w denotes an integer. Since d is a primitive modulo p and a primitive of X modulo p−1, when w varies ddwtraces an orbit which contains all the primitives modulo p, including a.

Therefore, there does exist an integer w such that
a≡ddw(modp).  (12)

The exponential congruence (1) is referred to as a “one-way” transaction, meaning that, when x is known, it is easy to compute a0xmodulo p, while, when y0is 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.

In order to determine the relationship between ν and w, raise (12) to aνmodulo p. It will be
aaν≡daν·dw(modp)  (13)
whence, by (10),
aν·dw≡1(modp−1)  (14)
or
aν≡d−w(modp−1).  (15)
As a conclusion: ν and w are exponents of known superprimitives of p, a and d, respectively. The integers aνand dware related in a congruence which is defined modulo p−1.
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 p−1. As an example, 19 is a superprimitive of 47 and 23. However, not all primes have superprimitives modulo p and modulo p−1.

Refer to (15). Let V denote the set of integers ν and w (1≤ν, w≤p′−1) which are candidate solutions of (10), (12), and (15) and let |V| denote their number.

A) It is desired to represent V as the direct product of distinct subsets of V, each one associated with one of the factors (qiε1or 2ε0) of p′−1.

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

To reach these aims:

A) The number of significant candidate elements associated with each of such sets is φ(qiε1) . Then the total number of candidate elements, say |V|, would be

The candidate elements associated to φ(qiε1), say ρlν1, are relatively prime to qiand can be represented as the elements of a cyclic group having ρias its generator.

Notice that, thus far, nothing has been stated concerning the divisibility of ρiby qjwhen i≠j.

B) Consider the case when ν and w are represented as the direct product of their component subgroups. In the case when ε0=1, ε0−1=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:

ρi=1+λi·φ⁡(p-1)/qiεi=σi+μi·qiεi(17)
where σidenotes any primitive modulo qiand (λi, μi) denotes a pair of integers. Given σi, the pair (λi, μi) can be any one of the solution pairs of the following:
σi−1+μi·qiε1=λi·φ(p−1)/qiε1.  (18)
Given any solution pair ({tilde over (λ)}i, {tilde over (μ)}i), its substitution into (17) produces ρimodulo φ(p−1). After this restatement, ρiis relatively prime to φ(p−1).

Consider the case when p′−1 has a structure of the form (2) or (3), that isa) 5 is the smallest odd prime divisor of p′−1, andb) each divisor qiis the smallest odd prime greater than qi−1.

Under these conditions, all the odd prime divisors of φ(p′−1), with the exception of 3, are also divisors of φ(p−1). It is possible to select σiin such a way that ρiis not a multiple of 3. In this case, ρiν1is relatively prime with φ(p−1) and φ(p′−1).

Thus, when p′−1 has the structure of (8) and (10) and ν is relatively prime with φ(p−1) and 3, it is possible to represent ν and w as follows

The congruences (20) define the orthogonality between ρiand ρj, for i≠j, and validate the definition of ρioffered by (17).

Notice that the definitions (17) imply that

In fact,

ρiφ⁡(qiεi)=(σi+μi·qiεi)φ⁡(qiεi)≡1+χi·qiεi(mod⁢qiεi)(22)
and also, for all positive integers n,

ρin=(1+λi·φ⁡(p-1)/qiεi)n=1+ψi·φ⁡(p-1)⁢qiεi(23)
for some χiand Ψiintegers. Combining (22) and (23), (21) follows.
Refer to Section I of the Appendix.

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

φ⁡(p-1)qiεi
modulo p−1.
It will be

This congruence establishes a relationship between νiand wiwhich does not depend on any of the values of νjand wj, for i≠j . In fact, given {tilde over (v)}i, the condition (26) defines {tilde over (w)}imodulo φ(qiε1).

NOTE 1: In (26), let wi, mdenote the value of wiwhen νi≡0(mod φ(qiε1)). Then

αiσivi,m≡δi-1(mod⁢p-1).(28)
NOTE 2: Consider the case when all the νj's are congruent to zero modulo φ(qjεj). In this case, from (15),

Likewise, consider the case when all the wj's are congruent to zero modulo φ(qj249j). In this case

Then
aU≡d−1(modp−1).  (34)
NOTE 3: Consider the case when all the νj's other than νiare congruent to zero modulo φ(qjεj) .
Assume {tilde over (ν)}i≢0 (mod φ(qiεi)) and νj≡0 (mod φ(qjεj)) for i≠j . In this case, using (31), it will be

Assume wj≢0 (mod qiεi) for j≢i. In this case, using (32), it will be

There exists a linear relationship between viand wimodulo φ(qjεj).

V. THE TRIAD

Given a pair (a, d), after the determination of the corresponding relationships (vi, wi), it is interesting to explore comparable relationships for a pair (d, g), where g is a superprimitive modulo p.

Raising the first of (43) to σivi(D, G)and the second to σiwi(A, D)modulo p−1 yields

{αiσivi(A,D)+vi(D,G)·δiσiwi(A,D)+vi(D,G)≡1⁢(mod⁡(p-1))δiσiwi(A,D)+vi(D,G)·γiσiwi(A,D)+wi(D,G)≡1⁢(mod⁡(p-1))(45)whenceαiσivi(A,D)+vi(D,G)≡γiσiwi(A,D)+wi(D,G)(mod⁡(p-1)).(46)
This congruence establishes a relationship between νiand wiwhich does not depend on any of the values of νjand wj, for i≠j. However, this relationship does not identify the value of νiwhich is consistent with (6).
NOTE 1: In general, in (27) wi, mdepends on the pair (a, d). Therefore, it will be necessary to distinguish wi, m(A, D) from wi, m(D, G). The same observation applies to vi, m(A, D) and vi, m(D, G).
NOTE 2: a and d are primitives modulo p−1. Therefore, they are relatively prime with φ(p−1). When a or d are raised to a divisor of φ(p−1), such as φ(p−1)/qiε1, they produce primitives modulo φ(p−1) for the sets {σiv1} and {σiw1}, respectively.

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

It should be emphasized the fact that (14) is defined modulo (p−1) 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 p−1 and the domain modulo p.

To this end, this Section introduces the notion of “Invertible Superprimitive”.

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 νiand wiwhich does not depend on any of the values of νjand wj, for i≠j.

Similarly,
g2·w≡1(mod(p−1)) .  (52)
Then
2·ν≡0(mod φ(p−1))  (53)
and
2·w≡0(mod φ(p−1)).  (54)
NOTE 1: In (53) and (54), v and w cannot be represented as in (19), because, by (17), ρimust be relative prime to φ(p−1). Thus (19) is applicable only if

{g⁢c⁢d⁡(v,φ⁡(p-1))=1g⁢c⁢d⁡(w,φ⁡(p-1))=1.(55)
NOTE 2: Compare (56) with (46). The congruence (46) establishes a necessary condition which relates vi(A, G) and wi(A, G). For g≡a−1(mod p), (46) constrains the values of v(A, G) and w(A, G) to be congruent to each other modulo φ(p−1) and also to be congruent to zero modulo φ(p−1).

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

APPENDIX A

NOTES ON ORTHOGONAL PRIMITIVES

I. AN EXAMPLE FOR p−1 CONTAINING ONLY SMALL PRIMES

Let
ax≡b(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 p−1=70=2·5·7.
Let

The order of X is φ(70)=φ(5)·φ(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=C1(2)×C2(12).  (A.3)

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

For σ1≡3(mod 5) and σ2≡5(mod 7) , it will be

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

(a14)3x2≡b14(mod⁢71).(A.10)
Then (A.7) produces x.
Therefore, in the example, x2and x1can be determined independently of each other.
FIG.1shows the elements of X as intersections of vertical and horizontal straight lines through 61x2(mod 70) and 43x1(mod 70), respectively.

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

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

Different selections of the primitives σ1and σ2would cause appropriate permutations of the vertical and horizontal lines, respectively.

APPENDIX B

THE ORDER OF σ032 4·ODD+1 MODULO 2ε0

When σ0=4·ODD+1, the order of σ0modulo 2ε0equals 2ε0−2:

Consider the case when σ0=4·ODD+1. Then

Notice that the integer σ0,0≡−1+2ε0−1cannot be produced as a power of σ0.

By using the methods described herein, the encrypted data in the memory is decoded in a time of an order of log log p·log2p 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.

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.

REFERENCES, all of which are incorporated by reference herein.