Refuting the Pseudo Attack on the REESSE1+ Cryptosystem
RefutePseudoAttack
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem* 
Shenghui Su 1, 2, and Shuwang Lü 3 
1 College of Computer Science, Beijing University of Technology, Beijing 100022, P.R.China 
2 School of Info Engi, University of Science & Technology Beijing, Beijing 100083, P.R China 
sheenway@126.com 
3 School of Graduate, Chinese Academy of Sciences, Beijing 100039, P.R.China 
swlu@ustc.edu.cn 
Abstract: We illustrate through example 1 and 2 that the condition at theorem 1 in [8] dissatisfies necessity, and 
the converse proposition of fact 1.1 in [8] does not hold, namely the condition Z / M – L / Ak < 1 / (2 Ak
2) is not 
sufficient for f (i) + f (j) = f (k). Illuminate through an analysis and ex.3 that there is a logic error during deduction 
of fact 1.2, which causes each of fact 1.2, 1.3, 4 to be invalid. Demonstrate through ex.4 and 5 that each or the 
combination of qu+1 > qu ∆ at fact 4 and table 1 at fact 2.2 is not sufficient for f (i) + f (j) = f (k), property 1, 2, 3, 4, 5 
each are invalid, and alg.1 based on fact 4 and alg.2 based on table 1 are disordered and wrong logically. Further, 
manifest through a repeated experiment and ex.5 that the data at table 2 is falsified, and the example in [8] is 
woven elaborately. We explain why Cx ≡ Ax W
 f(x) (% M) is changed to Cx ≡ (Ax W
 f(x))δ (% M) in REESSE1+ v2.1. 
To the signature fraud, we point out that [8] misunderstands the existence of T –1 and Q –1 % (M – 1), and forging 
of Q can be easily avoided through moving H. Therefore, the conclusion of [8] that REESSE1+ is not secure at 
all (which connotes that [8] can extract a related private key from any public key in REESSE1+) is fully 
incorrect, and as long as the parameter Ω is fitly selected, REESSE1+ with Cx ≡ Ax W
 f(x) (% M) is secure. 
Keywords: Public key cryptosystem; Security; Lever function; Continued fraction; Sufficient condition 
1  Introduction 
  In April 2001, we put forward the REESSE1 public-key encryption scheme [1]. In September 2003, we 
proposed the REESSE1 public-key cryptosystem which is an extension of the first version, and includes 
both encryption and signature [2]. In May 2005, it was argued that the lever function ℓ(.) is necessary and 
sufficient for the security of the REESSE1 encryption [3]. In [3], the continued fraction method of analyzing 
the key transforms Cx ≡ Ax W and Cx ≡ Ax W 
(x) (% M) with x ∈ [1, n] and ℓ (x) ∈ Ω was mentioned earlier 
than in any other publications. In November 2006, an abbreviation of the REESSE1+ cryptosystem was 
submitted to eprint.iacr.org [4]. 
  As is pointed out in [4], the set Ω = {5δ, …, (n + 4)δ | δ ≥ 1} is not unique, and other Ω may be 
selected ― Ω = {n + 1, …, n + n} with ℓ (i) + ℓ (j) ≠ ℓ (k) ∀ i, j, k ∈ [1, n] for example. Clearly, Ω is a 
security dominant parameter, and just like p and q in the RSA cryptosystem. 
  In May 2005, [5] pointed out that the REESSE1 signature scheme was insecure, which is right. 
  In July 2005, [6] thought unreasoningly that the REESSE1 encryption scheme was insecure, which is 
wrong, and rebutted thoroughly by us in [7]. Moreover, [7] illuminated definitely that the idea of the 
continued fraction analysis of REESSE1 did not originate from [6] (naturally also not from [8]), ant the 
idea firstly formally appeared in our 2004 application for a national fund project [7]. What needs to be 
pointed out further is that the authors of [8] are the related reviewers of our 2004 application. 
In December 2006, [8] thought unreasoningly again that the REESSE1+ public-key cryptosystem is not 
secure at all, which connotes any private key in REESSE1+ can be extracted by [8]. It is of flubdub and gulf. 
                                                        
* Received 05 April 2007, and revised 19 December 2009. 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
The ancients said ‘stop an advancing army with troops, and stop onrushing water with earth’. 
In what follows, the function f in [8] is namely the function ℓ in [4], namely f (i), f (j), f (k) in [8] are 
equivalent to ℓ (i), ℓ (j), ℓ (k), unless otherwise specified, the sign  represents ‘M – 1’, the sign % does 
‘modulo’, and unattached (x) does x-th expression. 
  In short, there exist 6 grave faults in [8]: 
   The converse proposition of fact 1.1 does not hold. 
  Clearly, fact 1.1 implies that if f (i) + f (j) = f (k), then Z / M – p u / q u < 1 / (2 qu
2) with L / Ak = p u / q u. 
We will prove by a counterexample that the former is only sufficient, but not necessary, namely if Z / M 
– p u / q u < 1 / (2 q u
2), then f (i) + f (j) = f (k) do not necessarily hold, and also namely Z / M – p u / q u < 1 / (2 q u
for f (i) + f (j) = f (k) is only necessary, but not sufficient. 
   Fact 1.2, 1.3 and 4 do not always hold. 
  Even if they hold, fact 1.2, 1.3 and 4 each are insufficient for f (i) + f (j) = f (k), and further, property 1, 2, 
3, 4 and 5 are invalid. Note fact 4 is essentially equivalent to each of fact 1.2 and 1.3. 
   The converse proposition of fact 2.2 does not hold, namely table 1 is insufficient for f (i) + f (j) = f (k). 
   Both algorithm 1 based on fact 4 and algorithm 2 based on table 1 are disordered & wrong logically. 
   To achieve so-called “breaking”, the example in [8] was woven elaborately, and table 2 was falsified, 
namely its authors intendedly mutilated the two tuple data to cause indeterminacy. 
   The inverse T –1 %  does not exist, and Q –1 %  not necessarily exist. 
Additionally, the case of Ω = {5 + δ, …, (n + 4) + δ | δ ≥ n – 4} with f (i) + f (j) ≠ f (k) ∀ i, j, k ∈ [1, n] is 
not analyzed at all. 
  Therefore, the cryptanalysis of the REESSE1+ cryptosystem by [8] is a type of pseudo-attack and 
balderdash leading to which the most radical reason is that the authors of [8] are not aware of the 
indeterminacy of the lever function ℓ (.) namely f (.), as is mentioned in [4]: 
   if the order of W is d < , then there is W f (x) ≡ W f (x) + d (% M), and when f (i) + f (j) = f (k), we see that 
f (i) + d + f (j) + d ≠ f (k) + d; 
   when f (i) + f (j) ≠ f (k), there exist Ci ≡ Ai′ W ′
), Cj ≡ Aj′ W ′
(j), and Ck ≡ Ak′ W ′
) (% M) such that f ′(i) 
+ f ′ (j) ≡ f ′ (k) (% ) with Ak′ ≤ ṕ , where ṕ is the maximal prime allowed. 
Another vital reason is that [8] always regarded necessary conditions for f (i) + f (j) = f (k) as sufficient 
and necessary conditions, and [8] did not consider the whole space of private keys or public keys. 
2  Theorem 1 vs the REESSE1+ Cryptosystem 
2.1  Condition at Theorem 1 in [8] Dissatisfies Necessity 
  Theorem 1 in [8] is retailed as follows: 
  Theorem 1: Let α be a real number, and let r / s be a rational with gcd(r, s) = 1 and |α – r / s| < 1 / (2s2). 
Then r / s is a convergent of the continued fraction expansion of α.                                
  Here, |α – r / s| represents the absolute value of (α – r / s). 
  The proof of theorem 1 is referred to [9]. 
  The condition |α – r / s| < 1 / (2s2) is only sufficient for r / s to be a convergent of the continued fraction of 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
α, but not necessary. Namely if r / s is a convergent of the continued fraction of α, |α – r / s| < 1 / (2s2) does 
not necessarily hold. 
  An example is taken. 
  Example 1. 
  Let r / s = 2 / 13, and then 1 / 2s2 = 1 / (2 × 132) = 0.002958579882. 
  Let α = 2039 / 13001, and then 
2039 / 13001 – 2 / 13 = 0.002987935839 > 0.002958579882 = 1 / (2 × 132). 
  On the other hand, the continued fraction of 2039 / 13001 is 1 / (6 + (1 / (2 + 1 / (1 + … 1 / 3)))). 
  Thus, 2 / 13 is a convergent of the continued fraction of 2039 / 13001, which illustrates |α – r / s| < 1 / (2s2) 
is not necessary for r / s to be a convergent of the continued fraction of α. 
2.2  Ak Will Emerge But Is Undecidable If f (i) + f (j) = f (k) 
Assume that ṕ is the maximum prime in the cryptosystem, {A1, …, An} is a coprime sequence with 0 < 
∀Ax ≤ ṕ, M > ∏ 
x = 1 Ax is a prime, and Cx ≡ Ax W
(x) (% M) for x = 1, …, n is a public key [4], where n ≥ 6, 
and f (x) ∈ Ω = {5δ, …, (n + 4)δ | δ = 1} = {5, …, n + 4}. 
  Assume f (k) = f (i) + f (j) with i ≠ k, j ≠ k , and i, j, k ∈ [1, …, n]. Let 
Z ≡ Ci Cj Ck
–1 (% M). 
  Then 
Z ≡ Ai Aj (Ak) 
–1 (% M) 
Z (Ak) ≡ Ai Aj (% M) 
Z (Ak) – L M = Ai Aj, 
where L is a positive integer. 
  Dividing the either side of the above equation by (M Ak) yields 
Z / M – L / Ak = Ai Aj / (M Ak).                       (1) 
  Due to M > ∏ n   x = 1 Ax and every Ax ≥ 2, we have 
Z / M – L / Ak < 1 / (2 
2).                       (1′) 
  Obviously, when n > 2 + 1, (1′) may have a variant, namely 
Z / M – L / Ak < 1 / (2 Ak
2).                         (1″) 
  In terms of theorem 1, L / Ak is a convergent of the continued fraction of Z / M. 
Let p0 / q0, p1 / q1, …, pt / qt be the convergent sequence of continued fraction of Z / M, and  
L / Ak = p u / q u. 
  Note that if pu / qu satisfies (1″), then pu + 1 / qu + 1, pu + 2 / qu + 2, …, pt / qt also likely satisfies (1″). 
Therefore, there likely exist multiple values of L / Ak by (1″), and Ak is undetermined. 
However, if we do not know in advance whether f (i) + f (j) = f (k), then even if Z / M – p u / q u < 1 / (2 q u
we can not decide f (i) + f (j) = f (k). Namely Z / M – p u / q u < 1 / (2 q u
2) is only necessary for f (i) + f (j) = f (k), 
but not sufficient, which will be discussed further in what follows. 
3  Conditions at Fact 1.1 and 4 Each Are Insufficient for f (i) + f (j) = f (k) 
Because fact 4 is essentially equivalent to each of fact 1.2 and 1.3, if the condition at fact 4 is 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
insufficient for f (i) + f (j) = f (k), the conditions at fact 1.2 and 1.3 each are also insufficient. 
The condition qu+1 > qu ∆ = qu (M / (2∏ 
x=n-2 prime 〈x〉))
2 at fact 4 connotes (1″) at fact 1.1 because (1″) 
is the precondition of qu+1 > qu ∆ which is the dominant basis of alg.1
 [8]. 
3.1  Converse Proposition of Fact 1.1 does not Hold and (1″) Is Insufficient for f (i) + f (j) = f (k) 
  Fact 1.1 in [8] is retailed as follows: 
  Fact 1.1 [8]: If f (i) + f (j) = f (k), there exists a qu such that qu = Ak in {p0 / q0, p1 / q1, …, pt / qt}, the 
convergent sequence of continued fraction expansion of Z / M with Z ≡ Ci Cj Ck
–1 % M.                
  Due to f (i) + f (j) = f (k), Z / M = L / Ak + Ai Aj / (M Ak), M > ∏ 
x = 1 Ax and Ax ≥ 2, we have 
Z / M – L / Ak = Ai Aj / (M Ak) < Ai Aj / (Ak ∏ 
x = 1 Ax). 
Further, 
Z / M – L / Ak < 1 / (2 Ak
2).                         (1″) 
  Let Z / M = [0; a1, a2, …, at] is the continued fraction expansion of Z / M. 
  By theorem 1, ∃ u ∈ [1, t] makes Z / M – p u / q u < 1 / (2 q u
  Let L / Ak = pu / qu, where 
pu / qu = a0 + 1 / (a1 + 1 / (a2 + … + 1 / (au – 1 + 1 / au))).                   (2) 
  Notice that it is possible that ∃ h > 0 makes Z / M – p u + h / q u + h < 1 / (2 q u + h
2), and moreover not fact 1.1 
but its converse is the inner logical base of alg.1 in [8]. 
  Through a counterexample, we will prove that the converse proposition of fact 1.1 does not hold, that is, 
the condition Z / M – p u / q u < 1 / (2 q u
2) is insufficient for f (i) + f (j) = f (k). 
  Example 2. 
  For convenience in computing, let n = 6, {Ax} = {11, 10, 3, 7, 17, 13}, δ = 1, and M = 510931. 
  Arbitrarily select W = 17797, f(1) = 9, f(2) = 6, f(3) = 10, f(4) = 5, f(5) = 7, and f(6) = 8. 
  From Cx ≡ Ax W
 f(x) (% M), we obtain 
  {Cx} = {113101, 79182, 175066, 433093, 501150, 389033}, 
and its inverse sequence 
  {Cx
–1} = {266775, 236469, 435654, 149312, 434038, 425203}. 
  Randomly select i = 1, j = 3, and k = 5. In this case, f(5) = 7 ≠ f(1) + f(3) = 9 + 10. Compute  
Z ≡ C1 C3 C5
                                       ≡ 113101 × 175066 × 434038  
                                       ≡ 186640 (% 510931). 
  Presume that W in C1 C3 is just neutralized by W
 –1 in C5
–1, then  
186640 ≡ A1 A3 A5
–1 (% 510931). 
  According to (1),  
186640 / 510931 – L / A5 = A1 A3 / (510931 A5). 
  By the Euclidean algorithm, a1, a2, a3, … are found out, and thus the continued fraction of 
186640 / 510931 = 1 / (2 + 1 / (1 + 1 / (2 + 1 / (1 + 1 / (4 + … + 1 / 3))))). 
  Heuristically let 
p 4 / q 4 = L / A5 = 1 / (2 + 1 / (1 + 1 / (2 + 1 / 1))) = 4 / 11, 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
which indicates that probably A5 = 11. On this occasion, there is 
186640 / 510931 – 4 / 11 = 0.0016575801 
                                               < 1 / (2 A5
2) = 1 / (2 × 112) = 0.0041322314. 
  The above expression satisfies (1″), namely the condition at theorem 1, and thereby A5 = 11 less than the 
maximum in {Ax} is deduced, which is in direct contradiction to factual A5 = 17. 
  So the condition Z / M – p u / q u < 1 / (2 q u
2) is not sufficient for f (i) + f (j) = f (k), namely the converse 
proposition of fact 1.1 does not hold. 
3.2  Each of Fact 1.2, 1.3 and 4 does not Hold 
  Fact 1.2 in [8] is retailed as follows: 
  Fact 1.2 [8]: There is sharp increase from qu to qu+1 since qu+1 ≥ (Ak M / (2Ai Aj))
1/ 2. 
  The derivation of fact 1.2 in [8] is retailed as follows: 
  Let L / Ak be the u-th convergent, i.e., qu = Ak and pu = L, i.e., pu / qu = L / Ak. Then we know that 
|Z / M – pu+1 / qu+1| < Ai Aj / (Ak M) = 1 / (2 ((Ak M / (2Ai Aj))
2)2).              (2′) 
  According to theorem 1 and convergence of sequence {p0 / q0, p1 / q1, …, pt / qt}, we obtain that 
qu+1 ≥ (Ak M / (2Ai Aj))
2 = Ak (M / (2Ai Aj Ak))
2.                    (3) 
                                                                                     
  Is the above derivation right? See the following analysis. 
  Clearly, by the definition of a finite continued fraction, (2′) holds. In addition, in terms of [9], pu+1 are 
qu+1 are coprime, and there is qu+1 ≥ Ak = qu, which is a judgment foundation. 
If f (i) + f (j) = f (k), then there is |Z / M – pu / qu| < 1 / (2 qu
2) with L / Ak = pu / qu. Furthermore, through 
practical observations, in most cases, there is also 
|Z / M – pu+1 / qu+1| < 1 / (2 qu+1
2).                         (3′) 
  According to (2′) and (3′), we have either 
|Z / M – pu+1 / qu+1| < 1 / (2 qu+1
2) < 1 / (2 ((Ak M / (2Ai Aj))
2)2),             (3″) 
|Z / M – pu+1 / qu+1| < 1 / (2 ((Ak M / (2Ai Aj))
2)2) < 1 / (2 qu+1
2).             (3′′′) 
  If (3″) holds, there exists qu+1 ≥ Ak (M / (2Ai Aj Ak))
2, which also indicates qu+1 ≥ Ak = qu. 
  If (3′′′) holds, there exists Ak (M / (2Ai Aj Ak))
2 ≥ qu+1. Notice that in this case, qu+1 ≥ Ak = qu is still 
possible. 
  Therefore, qu+1 ≥ Ak (M / (2Ai Aj Ak))
2, namely fact 1.2 does not necessarily hold, which indicates that 
there is a logic error during the derivation of (3) in [8]. 
  Moreover, from (2′) and (3′) we can judge that when n is large enough ― 80 for example, the 
probability that (3′′′) holds is greater than one that (3″) holds. 
  Now, we review fact 1.3 in [8]. It is retailed as follows: 
  Fact 1.3 [8]: Due to fact 1.2, there is also a sharp increase from au to au+1, since qv+1 = av+1 qv + qv –1 for v 
= 1, 3, …, t. Here av s are items of Z / M determined by (2).                                       
  Obviously, because fact 1.2 does not hold, fact 1.3 does not also hold. 
  Further, because fact 1.2, namely (3) does not hold, naturally, fact 4 in [8] does not also hold, that is, qu+1 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
> qu (M / (2∏ 
x=n-2 prime 〈x〉))
2 is not always valid. 
  Observe an example once more. 
In example 3, suppose that the bit-length of a plaintext block is 8, and two bits of a block correspond to 
three items of a coprime sequence {Ax}, which means that the encryption algorithm is optimized through a 
compact binary sequence. In practice, we do just so. 
Apparently, the length of {Ax} is 3 × (8 / 2) = 12. 
Example 3. 
  Let {Ax} = {{23, 11, 17}, {41, 29, 26}, {15, 19, 37}, {31, 7, 43}}, and  
M = 2022169 > 31 × 37 × 41 × 43 = 2022161. 
  Randomly select W = 1507351, f (1) = 6, f (2) = 14, f (3) = 9, f (4) = 11, f (5) = 12, f (6) = 10, f (7) = 8, f (8) 
= 16, f (9) = 5, f (10) = 13, f (11) = 15, and f (12) = 7. 
  From Cx ≡ Ax W
(x) (% M), we obtain {Cx} = 
{{572402, 1930240, 374715}, {25128, 265158, 350520}, 
{1674837, 1231458, 1448214}, {110225, 1198155, 757620}}, 
and {C6
–1, C7
–1} = {93176, 1591882}. Let 
Z ≡ (C4 C12) (C6
–1)  
                                    ≡ (25128 × 757620) (93176 × 1591882) 
                                ≡ 776394 × 1123251  
                                    ≡ 689616 (% 2022169). 
  Then, 689616 / 2022169 – L / (A6 A7) = (A4 A12) / (2022169 A6 A7). 
  Further, the continued fraction of 689616 / 2022169 is  
1 / (2 +1 / (1 + 1/ (13 + 1/ (1 + (1/ (3 + 1/ (2 + 1/ (2 + 1/ (2 + 1/ (97 + 4 / 9)))))))))). 
  Heuristically let 
L / (A6 A7) = 1 / (2 +1 / (1 + 1/ (13 + 1/ (1 + (1/ (3 + 1 / 2))))) 
                           = 133 / 390, 
which indicates that probably A6 A7 = 390. Because the discriminant 
689616 / 2022169 – 133 / 390 = 2.235477262e-6 
                                                < 1 / (2 × 3902) = 3.287310979e-6 
satisfies the condition at theorem 1 in [8], A6 A7 = 390 is deduced out.  
  The integer 390 may be factorized into the pairs (2, 195), (3, 130), (5, 78), (6, 65), (10, 39), (13, 30), or 
(15, 26), where the elements of (10, 39), (13, 30), and (15, 26) are less than maximal number in {Ax}. Thus, 
true (A6, A7) = (26, 15) is included in 6 potential cases. Here, au = 2 and also au + 1 = 2, and there is no sharp 
increase from au to au+1. 
  Additionally, this example also illustrates that when one attempts to infer the suitable factors of the 
product Ak 1 Ak 2 by f (i) + f (j) = f (k1) + f (k2) with every f (x) ∈ Ω = {n + 1, …, 2n}, indeterminacy is 
increased remarkably. 
3.3  Condition at Fact 4 Is Insufficient for f (i) + f (j) = f (k) 
In [6], the attackers attempted to seek Ak dominantly by the converse proposition of fact 1.1, and 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
however, disturbing values of Ak are too many to determine the original value of Ak. Therefore, in [8], the 
attackers attempted to diminish indeterminacy of Ak through fact 4 which connotes fact 1.1, and is 
equivalent to each of fact 1.2 and 1.3. 
To say the least, even if fact 4 is valid sometimes, we can prove by a counterexample that the condition 
at fact 4 is insufficient for f (i) + f (j) = f (k). 
  Example 4. 
  Still let n = 6, {Ax} = {11, 10, 3, 7, 17, 13}, and M = 510931 > 11 × 10 × 3 × 7 × 17 × 13 = 510510. 
  Arbitrarily select W = 17797, f(1) = 9, f(2) = 6, f(3) = 10, f(4) = 5, f(5) = 7, and f(6) = 8. 
  From Cx ≡ Ax W
 f(x) (% M), we obtain {Cx} = {113101, 79182, 175066, 433093, 501150, 389033}, 
and its inverse sequence {Cx
–1} = {266775, 236469, 435654, 149312, 434038, 425203}. 
  Randomly select i = 1, j = 3, and k = 6. In this case, f(6) = 8 ≠ f(1) + f(3) = 9 + 10. Compute  
Z ≡ C1 C3 C6
                                       ≡ 113101 × 175066 × 425203  
                                       ≡ 425865 (% 510931). 
  Presume that W in C1 C3 is just neutralized by W
 –1 in C6
–1, then  
425865 ≡ A1 A3 A6
–1 (% 510931). 
  According to alg.1 in [8],  
425865 / 510931 – L / A6 = A1 A3 / (510931 A6). 
  Compute the continued fraction of186640 / 510931 being  
1 / (1 + 1 / (5 + 1 / (159 + 1 / 535))). 
  Heuristically let 
L / A6 = 1 / (1 + 1 / 5) = 5 / 6, 
which indicates that probably A6 = 6. Further, can verify that 
425865 / 510931 – 5 / 6 = 0.000174518 
                                               < 1 / (2 × 62) = 0.0138889 
satisfies the condition at theorem 1 in [8]. 
  Let u = 2, and qu = Ak = A6 = 6.  
  Then pu+1/ qu+1 = p3 / q3 = 1 / (1 + 1 / (5 + 1 / 159)) = 796 / 955, and 
Ak (M / (2Ai Aj Ak))
2 = 6 (510931 / (2 × 11 × 3 × 6))1/ 2  
= 6 × 35.9197  
= 215.5186. 
  In addition, evidently prime〈1〉 = 2, prime〈2〉 = 3, prime〈3〉 = 5, prime〈4〉 = 7, prime〈5〉 = 11, prime〈6〉 = 
13, prime〈7〉 = 17, and prime〈8〉 = 19 which are according to [8]. 
  Then, by fact 4 in [8], m = 7, and ∆ = (M / (2∏ m   x=n -2 prime〈x〉))
2 = (15)1 / 2 = 3.8729. 
  Thus, qu+1 = 955 > Ak (M / (2Ai Aj Ak))
2 = 216 satisfies fact 1.2 namely (3), au+1 = 159 > au = 5 satisfies 
fact 1.3, and qu+1 = 955 > qu ∆ ≈ 24 satisfies fact 4 and alg.1. 
  By the condition at fact 4, A6 = 6 < max A = 221 is deduced, namely alg.1 will output {1, 3, 6, 6}. 
However, it is in direct contradiction to true A6 = 13, which show the condition at fact 4 is not sufficient for 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
f (i) + f (j) = f (k), and every Ax will likely be evaluated to at least two eligible values (see example 5). 
Because the condition at fact 4 is insufficient for f (i) + f (j) = f (k), property 1, 2, 3, 4 and 5 are invalid. 
Further, the run result of alg.1 regarding an arbitrary public key {C1, …, Cn} as an input will contain 
enormous disturbing data as n ≥ 80, and it is infeasible that alg.2 find out the original coprime sequence 
{Ax} in polynomial time (see example 5), which manifests that alg.1 and 2 are invalid. 
4  Example in [8] Is Woven Elaborately and Data at Table 2 Is Falsified 
4.1  Example in [8] Illustrates Nothing about Breaking 
  It is easily understood that according to fact 1.1 and 4, the authors of [8] can weave an example 
consistent with alg.1 and 2 since 
   the lever function value {f (1), …, f (n)} may be known in advance; 
   the coprime sequence {A1, …, An} may be selected elaborately in advance; 
   the condition Z / M – L / Ak < 1 / (2 Ak
2) at fact 1.1 is necessary for f (i) + f (j) = f (k); 
   the condition qu+1 > qu (M / (2∏ 
x=n-2 prime 〈x〉))
2 at fact 4 is necessary for f (i) + f (j) = f (k) sometime. 
  However, as is indicated in the above rebutment, a consistent example does not illustrates that a related 
{Ax} can be extracted accurately from an arbitrary public key {Cx} when {f (x)} and {Ax} are unknown in 
advance. The authors of [8] at most broke “their own REESSE1+”, which diverted themselves, but not our 
REESSE1+ with choice parameters. It is well understood that even though a cryptosystem is RSA or ECC, 
its parameter is must also selected; otherwise the cryptosystem is insecure. 
  The example in [8] is neither readable nor verifiable in short time, and the proportion of n to log2 M is 
not also proper, which contravenes the optimization principle for the modulus M in the REESSE1+ 
cryptosystem. An obvious truth is that if M is too large, the length of a public key will increase rapidly. 
Therefore, M should be as small as possible while at least meets M > ∏ n   x = 1 Ax meantime. Selection of the 
sequence {Ax} in [8] also contravenes the optimization principle. 
  The intent for [8] to select such a large M that n is out of proportion to log2 M seems to want to increase 
the necessity of the conditions at fact 1.1 and 4 for f (i) + f (j) = f (k). However, it can not increase the 
sufficiency of the conditions. 
4.2  Data at Table 2 Is Falsified for a Compatible Effect 
  In above paragraphs, we illustrate that the condition Z / M – L / Ak < 1 / (2 Ak
2) at fact 1.1, namely  (1″) 
is insufficient for f (i) + f (j) = f (k). Property I will make us better understand it. 
  Property I: Let Cx ≡ Ax W
(x) (% M), where every x ∈ [1, n], Ax ≤ ṕ, f (x) ∈ {5, …, n + 4}, M > ∏ 
x = 1 Ax 
is a prime. Then, ∀ i, j, k ∈ [1, n], even if f(i) + f(j) ≠ f(k),  
  1) there always exist 
Ci ≡ A′i W ′ 
f ′ (i), Cj ≡ A′j W ′ 
f ′ (j), and Ck ≡ A′k W ′ 
f ′ (k) (% M) 
such that f ′ (i) + f ′ (j) ≡ f ′ (k) (% ) with A′k ≤ ṕ.  
  2) Ci, Cj, Ck make (1″) hold with A′k ≤ ṕ in all probability. 
  Proof:  
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
  Let Οd be an oracle for a discrete logarithm. 
  Suppose that W ′ ∈ [1, ] is a generator of ( * M , ·). 
  In terms of group theories, ∀ A′k ∈ {2, …, ṕ}, the equation  
Ck ≡ A′k W ′ 
(k) (% M) 
has a solution. f ′(k) may be taken through Οd. 
  ∀ f ′(i) ∈ [1, ], and let f ′(j) ≡ f ′(k) – f ′(i) (% ).  
  Then, from Ci ≡ A′i W ′
(i) and Cj ≡ A′j W ′
(j) (% M), we can obtain many distinct pairs (A′i, A′j), where A′i, 
A′j ∈ (1, M), and f ′(i) + f ′(j) ≡ f ′(k) (% ). 
  2) 
  Let 
Z ≡ Ci Cj Ck
 ≡ A′i A′j W ′ 
(i) + f ′
 (A′k W ′ 
(k))–1 (% M) 
with f ′(i) + f ′(j) ≡ f ′(k) (% ) but f(i) + f(j) ≠ f(k). 
  Further, there is A′i A′j ≡ Ci Cj Ck
 A′k (% M). 
  It is easily seen from the above equations the values of W′ and f ′(k) do not influence the value of A′i A′j. 
  If A′k ∈ [2, ṕ] changes, A′i A′j also changes. Thus, ∀ i, j, k ∈ [1, n], the number of value of A′i A′j is ṕ – 1. 
  Let M = 2 q ṕ 2 A′k, where q is a rational number. 
  According to (1), 
Z / M – L / A′k = A′i A′j / (M A′k) = A′i A′j / (2q ṕ
  When A′i A′j ≤ q ṕ
 2, there is  
Z / M – L / A′k ≤ q ṕ
 2 / (2 q ṕ 2 A′k
2) = 1 / (2 A′k
which satisfies (1″). 
  Assume that the value of A′i A′j distributes uniformly on (1, M). Then, the probability that A′i A′j makes (1″) 
hold is 
P∀ i,  j,  k ∈ [1, n] = (q ṕ
 2 / (2 q ṕ 2)) (1 / 2 + … + 1 / ṕ)) 
                                  ≥ (1 / 2)(2 (ṕ – 1) / (ṕ + 2)) 
                                  = 1 – 3 / (ṕ + 2). 
  It is seen that the probability is very large.                                                 
  According to property I.2, for a certain Ck ∈ {C1, …, Cn} and ∀ Ci, Cj ∈ {C1, …, Cn}, Ak will have 
roughly n2 values by (1″) namely the condition at fact 1.1, including the repeated, and considering the 
symmetry, almost every value has at least one counterpart. 
Of course, if the condition at fact 4, namely qu+1 > qu ∆ which connotes (1″) is used as a constraint, the 
number of values of Ak = qu will decrease. Example 4 already shows that even though f(i) + f(j) ≠ f(k), an 
eligible Ak can still be found. 
Notice that when i, j, k all fix on, it is fully possible that L / Ak has multiple satisfactory values, which 
implies multiple convergents of the continued fraction of Z / M likely meet (1″) and even qu+1 > qu ∆ . 
To clarify the matter thoroughly, we program by alg.1 in MS Visual C++, make an executable file, 
repeat the experiment regarding the public key at the example in [8] as input, and obtain the following 
output which is classified the same as in [8]: 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
Ak Tuples (i, j, k) 
A1 = 9 (9, 9, 1) 
A2 = 253 (7, 5, 2), (9, 6, 2), (5, 7, 2), (6, 9, 2) 
A3 = 16127 (10, 7, 3), (7, 10, 3) 
A4 = 3 (8, 3, 4), (3, 8, 4) 
A4 = 205 (9, 3, 4), (6, 5, 4), (5, 6, 4), (7, 7, 4), (3, 9, 4) 
A4 = 152391460756 (8, 7, 4), (7, 8, 4) 
A6 = 53022327 (4, 3, 6), (3, 4, 6) 
A6 = 318461273008612 (4, 3, 6), (3, 4, 6) 
A6 = 4471789987666990 (5, 3, 6), (3, 5, 6) 
A6 = 1572955621791218 (5, 5, 6) 
A8 = 2809 (5, 5, 8), (9, 7, 8), (7, 9, 8) 
A10 = 49 (9, 5, 10), (5, 9, 10) 
A10 = 1894 (9, 6, 10), (6, 9, 10) 
A10 = 6957 (9, 7, 10), (7, 9, 10) 
Table I: Output of the program by alg. 1 given the public key at the example in [8] 
Obviously, table 2 in [8] misrepresented A3 = 16127 as A4 = 16127, and A6 = 53022327 as A10 = 
53022327. What gets worse is that table 2 mutilated the two tuple data (4, 3, 6, 318461273008612) and (3, 
4, 6, 318461273008612), which is a type of data falsification. These two tuple data illustrate that for fixed i, 
j, k, the L / Ak may have several satisfactory values, namely the several convergents of the continued 
fraction of Z / M meet fact 4 meantime, which reflects the insufficiency of the condition qu+1 > qu ∆ further, 
increases the indeterminacy of Ak greatly, and weakens the reliability of alg.1 in [8] greatly. 
4.3  Example in [8] Is Woven Elaborately and Alg.2 in [8] Is Invalid 
In the above, it is mentioned that at most the authors of [8] broke “their own REESSE1+”, because the 
example in [8] is woven elaborately, and the parameters {Ax} and {f (x)} are selected deliberately. 
If we use another set of parameters for producing a public key as the input of the program by alg.1, the 
output result will contains so many disturbing data that the original sequence {A1, …, An} can not be 
distinguished in polynomial time. 
Example 5. 
Let n = 10, {Ax} = {437, 221, 77, 43, 37, 29, 41, 31, 15, 2}, and  
M = 13082761331670077 > ∏ n   x = 1 Ax = 13082761331670030. 
  Arbitrarily select W = 944516391, f(1) = 11, f(2) = 14, f(3) = 13, f(4) = 8, f(5) = 10, f(6) = 5, f(7) = 9, f(8) 
= 7, f(9) = 12, f(10) = 6. 
  According to Cx ≡ Ax W
 f(x) (% M), we obtain {Cx} = {3534250731208421, 12235924019299910, 
8726060645493642, 10110020851673707, 2328792308267710, 8425476748983036, 6187583147203887, 
10200412235916586, 9359330740489342, 5977236088006743}. 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
Input the public key {Cx} into the program by alg.1, and obtain ∆ = 506, max A = 58642670, and the 
following tuples greater than 100: 
Ak Tuples (i, j, k) 
A1 = 187125 (1, 1, 1) 
A1 = 121089 (2, 1, 1), (1, 2, 1) 
A1 = 77 (5, 3, 1), (3, 5, 1) 
A1 = 23 (8, 6, 1), (6, 8, 1), (10, 10, 1) 
A1 = 437 (10, 6, 1), (6, 10, 1) 
A2 = 1251 (1, 1, 2) 
A2 = 187125 (2, 1, 2), (1, 2, 2) 
A2 = 121089 (2, 2, 2) 
A2 = 17 (8, 4, 2), (6, 5, 2), (5, 6, 2), (10, 7, 2), (4, 8, 2), (7, 10, 2) 
A2 = 221 (10, 4, 2), (7, 6, 2), (6, 7, 2), (8, 8, 2), (4, 10, 2) 
A2 = 77 (9, 8, 2), (8, 9, 2) 
A2 = 4204 (10, 10, 2) 
A3 = 187125 (3, 1, 3), (1, 3, 3) 
A3 = 12 (7, 1, 3), (1, 7, 3) 
A3 = 121089 (3, 2, 3), (2, 3, 3) 
A3 = 77 (6, 4, 3), (4, 6, 3), (10, 8, 3), (8, 10, 3) 
A3 = 11 (10, 4, 3), (7, 6, 3), (6, 7, 3), (8, 8, 3), (4, 10, 3) 
A3 = 2113 (8, 7, 3), (7, 8, 3) 
A3 = 769 (9, 8, 3), (8, 9, 3) 
A4 = 187125 (4, 1, 4), (1, 4, 4) 
A4 = 121089 (4, 2, 4), (2, 4, 4) 
A4 = 76 (10, 6, 4), (6, 10, 4) 
A4 = 56 (10, 9, 4), (9, 10, 4) 
A5 = 187125 (5, 1, 5), (1, 5, 5) 
A5 = 630269 (6, 1, 5), (1, 6, 5) 
A5 = 121089 (5, 2, 5), (2, 5, 5) 
A5 = 41 (8, 2, 5), (2, 8, 5) 
A5 = 97 (4, 3, 5), (3, 4, 5) 
A5 = 37 (6, 6, 5), (10, 6, 5), (6, 10, 5) 
A6 = 187125 (6, 1, 6), (1, 6, 6) 
A6 = 121089 (6, 2, 6), (2, 6, 6) 
A7 = 187125 (7, 1, 7), (1, 7, 7) 
A7 = 121089 (7, 2, 7), (2, 7, 7) 
A7 = 3 (9, 3, 7), (3, 9, 7) 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
A8 = 187125 (8, 1, 8), (1, 8, 8) 
A8 = 34945619 (6, 2, 8), (2, 6, 8) 
A8 = 121089 (8, 2, 8), (2, 8, 8) 
A9 = 187125 (9, 1, 9), (1, 9, 9) 
A9 = 121089 (9, 2, 9), (2, 9, 9) 
A9 = 5 (6, 4, 9), (4, 6, 9), (10, 8, 9), (8, 10, 9) 
A9 = 15 (8, 6, 9), (6, 8, 9), (10, 10, 9) 
A10 = 259970 (4, 1, 10), (1, 4, 10) 
A10 = 187125 (10, 1, 10), (1, 10, 10) 
A10 = 121089 (10, 2, 10), (2, 10, 10) 
A10 = 7629 (8, 3, 10), (3, 8, 10) 
Table II: Output of the program by alg. 1 given the public key at example 5 
From table II, we observe that 
Ak from 5 tuples is A2 = 221 or A3 = 11, 
Ak from 4 tuples is A3 = 77 or A9 = 5, 
Ak from 3 tuples is A1 = 23, A5 = 37, or A9 = 15, 
Ak from 2 tuples is A1 = 77, A2 = 77, A3 = 12, A4 = 56, A5 = 41, or A7 = 3 etc, and 
Ak from 1 tuples is A1 = 187125, A2 = 1251, A2 = 121089, or A2 = 4204. 
Among these Ak′s, there exist at least 2
 n – 5 compatible combinations. 
For instance, arbitrarily select compatible A3 = 11, A9 = 5, A1 = 23, A5 = 41, and A2 = 1251, and find out 
f(3) = 14, f(9) = 13, f(1) = 12, f(5) = 11, and f(2) = 10 by Table 1 in [8]. 
Again for instance, arbitrarily select compatible A3 = 11, A9 = 5, A5 = 37, A7 = 3, and A1 = 187125, and 
find out f(3) = 14, f(9) = 13, f(5) = 12, f(7) = 11, and f(1) = 10 by Table 1 in [8]. 
Therefore, if keep Ω = {5, .., n + 4} unvaried, we may select fit {Ax} and W so as to make the time 
complexity of the continued fraction attack by qu+1 > qu ∆ and table 1 get to at least O(2 
n), which elucidates 
that the example woven elaborately in [8] has no practical meaning, and alg.2 in [8] is invalid. 
However, we had best select fit Ω while let {Ax} and W random so as to avoid attack by (1′) (see sect.5.1). 
4.4  Distribution of Tuples Relating Ak does not Follow Table 1 in [8] 
In addition, from table II we also observe that A2 = 17 involves 6 tuples, and A5 = 37 involves 3 tuples 
(but in fact, 6 tuples is impossible, and f(5) = 10), which indicates that the distribution of tuples relating Ak 
does not follow table 1 in [8]. Besides, considering A3 = 11 from 5 tuples, A9 = 5 from 4 tuples etc, we see 
that table 1 is insufficient for f (i) + f (j) = f (k), that is, the converse proposition of fact 2.2 does not hold. 
5  Why Is Cx ≡ Ax W f(x) (% M) Changed to Cx ≡ (Ax W f(x))δ (% M) in REESSE1+ v2.1 
5.1  Lever Set Ω Needs to Be Complicated When Cx ≡ Ax W
 f(x) (% M) 
In REESSE1, Cx ≡ Ax W
 f(x) (% M) with f (x) ∈ Ω = {5, …, n + 4}. 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
In REESSE1+, Cx ≡ Ax W
 f(x) (% M) with f (x) ∈ Ω = {5δ, …, (n + 4)δ | δ ≥ 1}, {5 + δ, …, (n + 4) + δ | δ 
≥ n − 4}, {5, 7, …, 19, 53, 55, …} etc. 
If let W′ = W δ (% M), we see that {5δ, …, (n + 4)δ | δ ≥ 1} is substantially the same as {5, …, n + 4}. 
Although [8] by Z / M – L / Ak < 1 / (2 Ak
2) and qu+1 > qu ∆ can not break REESSE1+ with Cx ≡ Ax W
 f(x) 
(% M) and Ω = {5δ, …, (n + 4)δ | δ ≥ 1}, attack by Z / M – L / Ak < 1 / (2 
2), namely (1′) will filter out 
the most of disturbing data as n is large, which makes REESSE1+ be faced with danger. Therefore, in 
REESSE1+ with Cx ≡ Ax W
 f(x) (% M), Ω needs to be complicated, namely had best select Ω = {5, 7, …, 19, 
53, 55, …} which is an odd set of 2n elements such that  ∀ e1, e2 ∈ Ω, e1 ≠ e2,  ∀ e1, e2, e3 ∈ Ω, e1 + e2 
≠ e3,  ∀ e1, e2, e3, e4 ∈ Ω, e1 + e2 + e3 ≠ e4. 
5.2  Key Transform Cx ≡ Ax W
 f(x) (% M) Needs to Be Strengthened When Still Ω = {5, …, n + 4} 
In REESSE1+ with Cx ≡ Ax W
 f(x) (% M) and f (x) ∈ Ω = {5, 7, …, 19, 53, 55, …}, because the elements 
of Ω are relatively large, decryption speed will decrease greatly. 
To keep Ω = {5, …, n + 4} unvaried, the key transform should be strengthened, so in REESSE1+ v2.1, 
we let Cx ≡ (Ax W
 f(x))δ (% M). In this way, REESSE1+ v2.1 is not only secure but also swift. 
6  Attack on the Signature Is an Eisegesis 
6.1  T –1 %  does not Exist and Q –1 %  not Necessarily Exist 
  Section 4 of the original [8] deduces U ≡ ((Q / H) 1 / S  (GW) –1δ δ (δ + 1) – 1 / S) Q T (% M), which is right. 
  However, (GW) –1δ δ (δ + 1) – 1 / S ≡ ((Q / H) – S – 1  – 1) U (Q T) – 1 (% M) further given in [8] is wrong because 
T –1 %  with T |  does not exist, and neither does Q –1 %  exist when gcd(Q, ) > 1. In the signature 
algorithm, it is easy to let gcd(Q, ) > 1. 
  Denote x = (GW) –1δ δ (δ + 1) – 1 / S (% M). 
  Then, the trivial solution to x Q T ≡ U ((Q / H) 1 / S) – Q T (% M) does not exist when gcd (T,  / T) > 1. 
  Due to stipulating T ≥ 2 n in the key generation algorithm, the time complexity of finding out a random 
solution to x Q T ≡ U ((Q / H) 1 / S) – Q T is at least max (O(2 n – 1), O(M / (Q T))) through the probabilistic 
algorithm [10]. 
  If a solution to x Q T ≡ U ((Q / H) 1 / S) – Q T is found through the discrete logarithm method, the probability 
that the solution is just equal to (GW) –1δ δ (δ + 1) – 1 / S (% M) is at most 1 / 2 n. 
  If denote x = ((GW) –1δ δ (δ + 1) – 1 / S) T (% M), then x Q ≡ U ((Q / H) 1 / S) – Q T (% M). 
  When gcd (Q, ) > 5 and M / Q > 2 n, seeking a solution to x Q ≡ U ((Q / H) 1 / S) – Q T is also at least the 
discrete logarithm problem. 
6.2  Forging Attack in [8] May Be Easily Avoided through Turning D | (δ Q – W) to D | (δ Q – WH) 
  In REESSE1+ [4], we definitely pointed out that Q ≠ Q1, where Q is produced currently, and Q1 is any of 
signature foreparts produced ever before. Of course, Q ≠ Q1 implied that the linear combination of Q1 with 
Q2 should be excluded from signature foreparts. However, such exclusion is infeasible in polynomial time. 
  Therefore, in practical applications, it is suggested as a shortcut that users move the parameter H in Q ≡ 
(R G0) 
 Hδ (% M) into D | (δ Q – W), and make D | (δ Q – W) become D | (δ Q – WH). In this wise, the 
Refuting the Pseudo Attack on the REESSE1+ Cryptosystem                           http://arxiv.org/pdf/0704.0492 
forgery attack in [8] is easily avoided, namely Q′ can not be forged out at least in polynomial time. 
  Notice that correspondingly, the λ S in the signature algorithm and the discriminant in the verification 
algorithm should also be adjusted. 
7  Conclusion 
  The above rebuttal shows that each or the combination of (1″), qu+1 > qu ∆, and table 1 is not sufficient 
for f (i) + f (j) = f (k), there exist logic errors in the deduction of (3), and alg.1 based on fact 4 and alg.2 
based on table 1 are not valid. Additional, the signature forgery attack in [8] is easily avoided. Hence, the 
conclusion of [8] that REESSE1+ is not secure at all (which connotes that [8] can extract a related private 
key from any public key in REESSE1+) is completely incorrect, as long as Ω is fitly selected, REESSE1+ 
with Cx ≡ Ax W
 f(x) (% M) is secure, and the private key attack in [8] like [6] is a pseudo attack.. 
The authors of [8] attempt to convince people or credulous one of their opinion through an example 
woven elaborately, and their purpose is to want to suffocate REESSE1+, suppress us, and elevate 
themselves. Especially, [8] like [6] does not list the origin of idea of the continued fraction analysis of 
REESSE1, and falsifies the data at table 2, which violates scientific research ethics and honestness. 
We welcome unmalicious, co-promotive, and normal academic criticism which is utterly necessary. 
References 
[1] Shenghui Su, The REESSE1 Public-key Encryption Algorithms, Int. C1: H04L 9/14, ZL01110163.6, Chinese Patent, Apr. 
2001. 
[2] Shenghui Su, The REESSE1 Public-key Cryptosystem, Computer Engineering & Science, Chinese, v25(5), 2003, 
pp.13-16. 
[3] Shenghui Su, Yixian Yang and Bingru Yang, The Necessity and Sufficiency Analysis of the Lever Function in the 
REESSE1 Encryption Scheme, Acta Electronica Sinica, Chinese, v34(10), 2006, pp.1892-1895. (Received May 13, 2005) 
[4] Shenghui Su and Shuwang Lü, The REESSE1+ Public-key Cryptosystem, http://eprint.iacr.org/2006/420.pdf. 
[5] Shengli Liu, Fangguo Zhang and Kefei Chen, Cryptanalysis of REESSE1 Digital Signature Algorithm, CCICS 2005, 
Xi’an, China, May 2005. 
[6] Shengli Liu, Fangguo Zhang and Kefei Chen, Cryptanalysis of REESSE1 Public Encryption Cryptosystem, Information 
Security, Chinese, n7, 2005, pp.121-124. 
[7] Shenghui Su, Refuting the Pseudo Attack on the REESSE1 Public-key Algorithms for Encryption, Computer Engineering 
and Applications, Chinese, v42(20), 2006, pp.129-133. 
[8] Shengli Liu and Fangguo Zhang, Cryptanalysis of REESSE1+ Public Key Cryptosystem, http://eprint.iacr.org/2006/ 
480.pdf, Dec. 22, 2006. 
[9] Kenneth H. Rosen, Elementary Number Theory and Its Applications (5th ed.), Boston: Addison-Wesley, 2005, ch. 12. 
[10] Henri Cohen, A Course in Computational Algebraic Number Theory, Berlin: Springer-Verlag, 2000, ch. 1, 3. 
Remark 
The first version of this paper was sent to the authors of [8] via email on Mar. 6, 2007, and the draft of this 
revised version was sent to the authors of [8] via email between Oct. 23 and Nov. 12, 2009 repeatedly. 
The authors of [8] revised section 5 of [8] on Mar. 12, 2007 after they read this paper and the eprint.iacr.org′s 
demand that [8] should be withdrawn or modified, but the modification avoided the heavy and chose the light.
