Security Level of Cryptography —Integer Factoring Problem (Factoring N = p2 q)
December 2001

Contents
Summary2

Detailed Evaluation

3

1 The Elliptic Curve Method

3

1.1

The ECM applied to N = pd q . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Running time estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52 The Lattice Factoring Method

7

3 Factoring Using Jacobi Symbols

8

4 Conclusions: Recommended parameter sizes for N = pd q

9References

101Summary

Integers of the form N = pd q have found many application in cryptography. For example,
Okamoto et al. use N = p2 q to give a fast digital signature scheme [12, 10, 3],Okamoto and Uchiyama [13] use N = p2 q to build an elegant public-key system, andTakagi [16] shows how to use N = pd q to speed-up RSA decryption.
This report analyzes the effectiveness of various factoring techniques for factoring integersof the form N = p2 q (and more generally integers of the form N = pd q). We study theeffectiveness of three factoring techniques:
1. The Elliptic Curve Method (ECM) [7] augmented by Okamoto and Peralta [11],2. The Lattice Factoring Method (LFM) [1], and3. Factoring N = p2 q using Jacobi symbols.
Our conclusion is that the LFM method and the Jacobi symbol method cannot currently be
used to attack N = p2 q when N is at least 1024-bits long. On the other hand, the ECM methodwith the improvements of Okamoto and Peralta poses a threat that should be addressed. Whenusing N = p2 q one would like to ensure that the modulus size is sufficiently large to provide
the same level of security as 1024-bit standard RSA. Hence, our conclusions are three fold:
1. 1024-bit integers of the form N = p2 q provide adequate security in the short term.
However, within 5 to 10 years the safety margins provided by such integers will likely
become unacceptable.
2. To provide security comparable to standard 1024-bit RSA it is recommended to use atleast a 1280-bit N = p2 q modulus. We estimate that the running time for ECM on sucha modulus is comparable to the running time of the Number Field Sieve on 1024-bit RSA(note that we are ignoring memory-space considerations).
3. 1024-bit integers of the form N = p3 q should be considered insecure and should not be
used in deployed systems. They are susceptible to a factoring attack using the ECM
method.
We also show that integers of the form N = p2 q have more structure than standard RSA
integers. We show that this structure may lead to new factoring algorithms specifically targetedat N = p2 q. Hence, factoring N = p2 q might be much easier than factoring N = pq of thesame size. Currently we cannot exploit this extra structure of N = p2 q to design new factoringalgorithms. Therefore this should be viewed as a theoretical threat rather than a real attack.

2

Detailed Evaluation

The report is organized as follows. We begin by analyzing the effectiveness of the Elliptic
Curve Method (ECM) for factoring integers of the form N = pd q. We mostly focus on square
integers N = p2 q. We then estimate the running time of the ECM and deduce some bounds
on the size of N = p2 q for proper security. Next, we consider the Lattice Factoring Method(LFM) and show that it does not pose a threat to sufficiently large square integers. Finally, in
Section 3 we discuss a hypothetical approach to factoring square integers using Jacobi symbols
and conclude that factoring such numbers could be easier than factoring general RSA integers.
Note that we do not explicitly analyze the performance of the Number Field Sieve (NFS)
on integers of the form N = pd q. The NFS will take the same amount of time to factor N = p2 q
as it will to factor N = pq of the same size. Hence, the NFS does not pose a threat to N = p2 q
beyond the threat that it poses to standard RSA integers. Throughout the report we use an
estimated running time of the NFS on a standard 1024-bit RSA integer to assess the securityof integers N = p2 q and N = p3 q for various sizes of N .
Notation: Whenever we√write N = p2 q we assume that p and q are primes of approximately
we write N = p3 q we assume p and q are primes
the same size, i.e. p, q ≈ 3 N . Similarly, when√4of approximately the same size, i.e. p, q ≈ N .

1

The Elliptic Curve Method

The Elliptic Curve factoring Method (ECM) [7] is a general-purpose factoring algorithm that
performs well when the smallest prime factor is relatively small. Hence, it is√natural to analyze
its performance on N = p2 q since p and q are relatively small, i.e. p, q  N . When p is thesmallest prime factor of N the asymptotic running time of ECM is:
L1/2,√2 (p) = exp (1.41 + o(1)) ln(p)1/2 (ln ln(p))1/2(1)
The term o(1) tends to 0 as p tends to infinity. Several practical speed-ups to the ECM givean (approximately) constant factor improvement [8] over this asymptotic running time.
The ECM requires little memory-space to run. Asymptotically ECM only requires linear
space. Other factoring methods such as the NFS require large amounts of memory size (thoughsub-exponential in the size of the number being factored). Hence, a pure time comparison
between ECM and NFS is a bit inaccurate since for a large factoring project (e.g. factoring
RSA-1024) the space requirements of NFS are prohibitive. In our estimates we make a note ofthe difference in space requirements, but mostly rely on running-time for comparison between
different techniques.
The current record in ECM factoring belongs to Miyamoto [15] who succeeded in findinga 183-bit factor of a 372-bit number. This project took about 13 days using a single 800MhZ
Pentium III. We will use this result as a base point for estimating the running-time of ECM
on large integers N = pd q.
3

1.1

The ECM applied to N = pd q

We briefly describe a simple variant of the ECM method and then discuss its adaptation to
integers of the form N = pd q.
Let B1 , B2 be two smoothness bounds. Typically B1 is set to B1 = L1/2,√2/2 (p) and B2 ischosen as some larger value, e.g. B2 = 10B1 . The ECM algorithm factors an integer N = pd q
by iterating the following steps until N is factored:
2 and choose random a, b ∈ Z such that
Init: Pick a random point T = (x0 , y0 ) ∈ ZN
N

y02 = x30 + ax0 + b(mod N )We refer to the set of points (x, y) ∈ Z2N satisfying y 2 = x3 + ax + b (mod N ) as anelliptic curve E/ZN . If we reduce a, b modulo q we get an elliptic curve E/Fq . It is
well known that the set of points on E/Fq forms an Abelian group. There is a naturalmap φq : E/ZN → E/Fq defined by φq ((x, y)) = (x mod q, y mod q). Let mq be the(unknown) order of φq (T ) in the group E/Fq . Similarly, let mp be the (unknown) orderof φp (T ) in the group E/Fp .
Power: Let L ∈ Z be the product of all prime powers less than B1 . Compute R = L·T ∈ E/ZN
by using the addition law on the curve E : y 2 = x3 + ax + b. This step takes timeO(B1 log B1 log2 N ).
Search: Suppose mq is a small multiple of a B1 -smooth number. More precisely, suppose
mq = M · m where M has no prime factor larger than B1 and m < B2 . Then the pointφq (R) ∈ E/Fq has order dividing m on the curve E/Fq . Since m < B2 we know thatφq (R) has order less than B2 in E/Fq . We assume that φp (R) ∈ E/Fp has order muchlarger than B2 on E/Fp .
Now, suppose we had two integers α1 , α2 ∈ [0, B2 ] such that α1 = α2 mod m. Let
R1 = (x1 , y1 ) = α1 R and R2 = (x2 , y2 ) = α2 R. Then φq (R1 ) = φq (R2 ), but φp (R1 ) 6=
±φp (R2 ). Hence, x1 = x2 mod q, but x1 6= x2 mod p. We then obtain the factorizationof N by simply computing gcd(x1 − x2 , N ) = q.
Since m is not known√ to us the question is how to find such α1 , α2 . The simplest approachis to pick k = 2d B2 e random integers α1 , . . . , αk ∈ [0, B2 ]. Then the birthday paradox
implies that with high probability there exists 0 ≤ u, v ≤ k such that αu = αv mod m.
To find the pair u, v we compute Ri = (xi , yi ) = αi R for all i = 1, . . . , k. We know thatgcd(xu − xv , N ) = q. Hence, given x1 , . . . , xk ∈ ZN we need to find u, v satisfying thisgcd relation. Naively we can do this by trying all pairs 0 ≤ u, v ≤ k. This takes timeO(B2 log2 N ).
Montgomery and Silverman [9] and Pollard proposed better algorithms for this last stepusing FFT. Their algorithm takes√ x1 , . . . , xk ∈ 2ZN as input and finds a pair u, v so thatgcd(xu − xv , N ) = q in time O( B2 log B2 log N ). Asymptotically this is much fasterthan the naive method. Unfortunately, the constants hidden by the big-O are relatively
large making this method less attractive.
The three steps above are repeated until N is factored. The expected number of iterations is
L1/2,√2/2 (p).
4

The Okamoto-Peralta improvement: When N = p2 q Okamoto and Peralta [11] propose
an improvement to the Search step in the above algorithm. Recall that the problem to solve
is given x1 , . . . , xk ∈ ZN find a pair u, v satisfying gcd(xu − xv , N ) = q. To do so, define thesignature of an element x ∈ Fq as  
x
x+1
x+b
,
,...,
∈ {±1, 0}b+1
sig(x) =qqq
 
where b = blog2 qc and xq is the Legendre symbol of x mod q. It is conjectured that sig(x)uniquely defines x ∈ Fq , namely if x 6= y then sig(x) 6= sig(y).
The main point of the Okamoto-Peralta improvement is that when N = p2 q we can efficiently compute the signature of x1 , . . . , xk ∈ ZN even though q is unknown. To see thisobserve that when N = p2 q the Jacobi symbol of x ∈ Z∗N satisfies
x
N


=

x
p2

    2    
x
x
x
x
·
=
·
=
q
p
q
q



Hence, we can compute the signature of xi mod q by computing the Jacobi symbols xiN+j
for j = 1, . . . , b. Once we compute the signatures of all the xi ’s modulo q we can easily findu, v such that sig(xu ) = sig(xv ) mod q in time O(k log√ k). Then xu = xv mod q. Hence, when
N = p2 q the third step of ECM now takes time O( B2 log B2 log2 N ) where the constant in
the big-O notation is quite small. This means we can use a much larger value of B2 . Okamoto
and Peralta claim that this method speeds up the ECM by approximately a factor of 50 for
the parameter sizes we are interested in.
Potential defense against Okamoto-Peralta: We note that the Okamoto-Peralta improvement only applies when ECM is close to finding the prime factor q of N = p2 q. Hence,for proper security it may make sense to increase the size of q by a few bits at the cost of
reducing the size of p. For example, it may make sense to increase the size of q by 10 bits andreduce the size of p by 5 bits. This has no effect on the size of N = p2 q, but it nullifies the
Okamoto-Peralta improvement to ECM since finding q is now harder.
ECM improvements for N = pd q: The Okamoto-Peralta improvement for N = p2 q generalizes to N = pd q. To do so one defines the signature of x mod N using the d’th power
residue symbol [4, p. 204]. For a given x ∈ ZN one computes the signature of x mod q using
the Eisenstein reciprocity law [4, p. 207]. We do not give the details here.

1.2

Running time estimates

As mentioned earlier, the current record in ECM factoring belongs to Miyamoto [15] who
succeeded in finding a 183-bit factor of a general 372-bit number in 13 days using a single
800MhZ Pentium III. We will use this result as a base point for estimating the running-timeof ECM on large integers N = pd q.

5

We estimate the running time of ECM for factoring (1) 1024-bit N = p2 q, (2) 1280-bit
N = p2 q, and (3) 1024-bit N = p3 q. Our estimates show that 1024-bit N = p3 q is insecureby today’s standards and should not be used in deployed systems. 1024-bit N = p2 q is not asstrong as standard 1024-bit RSA, but may leave sufficient safety margins for short term use.
However, within five to ten years 1024-bit N = p2 q is likely to become unacceptable. On theother hand 1280-bit N = p2 q seems to offer similar security to 1024-bit standard RSA and canbe adequately deployed.
1. Factoring 1024-bit N1 = p2 q: Here the prime factor q is of order 1024/3 = 342-bits.
We use Equation 1 to compare the running for factoring such N1 with the result of Miyamoto.
The direct ratio of running times is:
L1/2,√2 (2342 )L1/2,√2 (2183 )= 7.76 · 106

Note that we are ignoring the o(1) term in Equation 1. Instead, we manually adjust ourestimate to take into account that arithmetic modulo a 1024-bit number takes longer thanarithmetic modulo a 372-bit number (the size of the modulus used by Miyamoto). Assuming
all arithmetic operations take quadratic time, we need to add a factor of (1024/372)2 = 7.57
to the estimate. This implies that finding a 342-bit factor of a 1024-bit modulus should takeapproximately 5.88 · 107 times the work of finding a 183-bit factor of a 372-bit modulus. To beconservative we include the factor of 50 improvement in ECM running time due to OkamotoPeralta. Hence, factoring a 1024-bit N1 = p2 q should take approximately 42000 years on asingle 800MhZ Pentium III.
We compare the effort of factoring N1 using ECM to the effort of factoring RSA-155, a
512-bit integer [2]. RSA-155 was factored using the Number Field Sieve in 3.7 months using
about 300 machines. We see that factoring N1 using ECM takes about 460 times the work offactoring RSA-155 using NFS. These numbers are only an estimate based on the asymptotic
formulas and could be off by as much as a factor of 10. So, suppose that finding a 342-bit factor
using ECM is 4000 times the effort of factoring RSA-155 using NFS. This safety margin might
be acceptable today, but may not be acceptable in 5 to 10 years given the rate of advance inboth hardware performance and hardware availability. We note that factoring a regular 1024bit RSA modulus N = pq would take 3.1 · 106 times the work of factoring RSA-155 (assuming
no memory-space constraints) which is a much larger safety margin than we have for 1024-bit
N = p2 q.
2. Factoring 1024-bit N2 = p3 q: Here the prime factor q is of order 1024/4 = 256-bits. We
use Equation 1 to compare the running time for factoring such N2 with the result of Miyamoto.
The direct ratio of running times is:
L1/2,√2 (2256 )L1/2,√2 (2183 )= 2486As before we adjust our estimate by a factor of 7.57 to take into account that arithmetic modulo
a 1024 bit number takes longer than arithmetic modulo a 372-bit number. Hence, factoring a1024-bit N2 = p3 q should take approximately 670 years on a single 800MhZ Pentium III.
6

This comes out to be approximately 7.2 times the effort it took to factor RSA-155 (a 512 bit
integer) using NFS. These numbers are only an estimate based on the asymptotic formulas andcould be off by as much as a factor of 10. So, suppose that finding a 256-bit factor using ECM
is 72 times the effort of factoring RSA-155 using NFS. This safety margin is far smaller thanthe margin provided by comparable standards. In fact, these calculations show that factoring1024-bit N2 = p3 q is within reach of a large factoring project today. Hence, 1024-bit numbersof the form N2 = p3 q should not be used in deployed systems.
3. Factoring 1280-bit N3 = p2 q: Here the prime factor q is of order 1280/3 = 426-bits.
We use Equation 1 to compare the running for factoring such N3 with the result of Miyamoto.
The direct ratio of running times is:
L1/2,√2 (2426 )L1/2,√2 (2183 )= 8.8 · 109

As before we adjust our estimate by a factor of (1280/372)2 = 12 to take into account thatarithmetic modulo a 1280-bit number takes longer than arithmetic modulo a 372-bit number.
To be conservative we also include the factor of 50 improvement in ECM running time due toOkamoto-Peralta. Hence, factoring a 1280-bit N3 = p2 q should take approximately 7.6 · 107
years on a single 800MhZ Pentium III using ECM. This is approximately 8 · 105 times thework of factoring RSA-512 which provides comparable security to that provided by standard
1024-bit RSA N = pq.
Remark: We note that our estimates in this section are based on asymptotic behavior. We
neglected some low order terms, but tried to be conservative where appropriate. The effectof the Okamoto-Peralta improvement is a bit difficult to predict. We used a factor of 50 toestimate the improvement for 1024-bit N = p2 q since that seems to be a conservative estimate.

2

The Lattice Factoring Method

The special structure of N = p2 q makes it susceptible to another factoring method called theLattice Factoring Method (LFM) [1]. The LFM is designed to factor very large integers of theform N = pd q for large value of d, e.g. d ≈ 20. However, the method has some implications tointegers of the form N = p2 q and N = p3 q. We state the following theorem that easily follows
from Lemma 3.3 of [1]:Theorem 2.1 Let N = pd q be an n-bit integer where blog2 pc = blog2 qc = n/(d + 1). Then2
the LFM factoring algorithm will factor N in time O(2n/(d+1) n4 ).
For square integers N = p2 q we get a factoring algorithm whose running time is dominatedby the term 2n/9 . For N = p3 q we get an algorithm whose running time is dominated by theterm 2n/16 . These dominant terms determine the number of iterations needed for the algorithm
to work. In each iteration the algorithm runs the LLL lattice bases reduction algorithm.
7

Therefore, the running time for each iteration is non-trivial. We use the experiments givenin [1] and assume that each iteration takes one hour on a 400MhZ Pentium II. As before weanalyze the running time of the LFM algorithm for (1) 1024-bit N = p2 q, (2) 1024-bit N = p3 q,
and (3) 1280-bit N = p2 q.
1024-bit N = p2 q: the expected number of iterations is 21024/9 = 2113 . The number of iterations alone is already too large to carry out. Considering that each iteration takes one
hour makes this algorithm completely infeasible.
1024-bit N = p3 q: the expected number of iterations is 264 . Taking one hour per iteration thealgorithm will take 1016 years on a single machine. This number is beyond the reach ofcomputers for the next 20 years. Hence, the LFM method is ineffective against 1024-bit
N = p3 q.
1280-bit N = p2 q: Here again the number of iterations is too large to carry out. The algorithm will require an expected 2142 iterations. Again this is beyond the reach of computers
for the next 20 years.
In summary, the LFM method works well for very large numbers of the form N = pd qwith large d, but is ineffective against 1024-bit integers (or longer) of the form N = p2 q andN = p3 q.

3Factoring Using Jacobi Symbols

We conclude this report with an observation that suggests that integers of the form N = p2 q
might be easier to factor than factoring N = pq. In other words, we show that N = p2 q might
be susceptible to a class of integer factorization algorithms that do not apply to N = pq.
We begin with the observation of Okamoto-Peralta [11]. Let N = p2 q and x ∈ Z∗N .
Okamoto and Peralta showed that we can easily determine whether
residue  x is a quadraticxx
modulo q without knowing q. This follows from the fact that q = N . Hence, x is axquadratic residue
in
F
if
and
only
if
the
Jacobisymbolis 1. Furthermore, the JacobiqNxsymbol N is easy to compute.
Using our ability to determine whether x is a quadratic residue modulo q can potentiallygive rise to a new class of factoring algorithms for N = p2 q. Let `1 , `2 , . . . , `k be the ksmallest odd integer primes (3, 5, . . .). If `i is a quadratic residue modulo q then q satisfies
certain congruence relations modulo 4`i . For example, if 3 is a quadratic residue modulo qthen q mod 12 ∈ {1, −1}. If 5 is a quadratic residue modulo q then q mod 20 ∈ {1, 9, 11, 19}.
Generally, every time we learn the Legendre symbol of ` mod q we learn that q mod 4` is oneof ` − 1 possible values. By using many small primes in this way we collect more and morecongruence information about q. The question is whether it is possible to recover q from all
this information. One can show that all this congruence information uniquely determines q,
but it is currently an open problem to find q given this information.
We can collect this information about q into a simple univariate modular polynomial asfollows. The one bit of information we learn from the Legendre symbol of ` mod q can be8

converted via quadratic reciprocity into an equation in q of the formq (`−1)/2 = (−1)b(mod `)

where b ∈ {0, 1} is known to us. We get one such equation for each small `i . This leads to thefollowing system of equations in q: (` −1)/2
1= (−1)b1 (mod `1 )

 q
..
.

 (`k −1)/2q= (−1)bk (mod `k )Let L be the product of all the `i ’s. Then we can apply the Chinese Remainder Theorem(CRT) to all these equations to get a polynomial f (x) ∈ ZL [x] of degree (`k − 1)/2 for which
we know that f (q) = 0 mod
L. When L is sufficiently large we know that q is a small root√3of this polynomial (q < N ). Since the polynomial√ f (x) is easy to construct the question iswhether it is possible to recover all integers |y| < 3 N such that f (y) = 0 mod L. One of theseroots of f (x) will be the desired q. Currently, the best techniques for finding small roots ofmodular equations (due to Coppersmith) do not seem capable of solving this problem.
This approach to factoring N = p2 q does not apply to standard RSA moduli N = pq. We
are clearly using the special structure of p2 q to deduce information about q. Currently we do
not know how to make use of this information. At any rate, this approach shows that factoring
N = p2 q is potentially easier than factoring N = pq. The special structure of N = p2 q opens
the door to new techniques that do not apply to N = pq.
Remark: As a final comment we note that the discussion in this section generalizes to
N = pd q for d > 2 by using the d’th power residue symbol (rather than the Legendre symbol).
This symbol can be computed using the Eisenstein reciprocity theorem [4, p. 207]. We also
note that an efficient factoring algorithm for N = p2 q using the techniques of this section would
imply that computing quadratic residousity modulo a Blum integer is as hard as factoring the
integer — a long standing open problem.

4

Conclusions: Recommended parameter sizes for N = pd q

This report studies the effectiveness of various factoring techniques for factoring integers of theform N = p2 q and more generally integers of the form N = pd q. We studied the effectivenessof three factoring techniques:
1. The Elliptic Curve Method [7] augmented by [11],2. The Lattice Factoring Method [1], and3. Factoring N = p2 q using Jacobi symbols.
Our conclusion is that the LFM method and the Jacobi symbol method cannot currently be
used to attack N = p2 q when N is 1024-bits long. On the other hand, the ECM method with
the improvements of Okamoto and Peralta poses a threat that should be addressed. Whenusing N = pd q one would like ensure that the modulus size is sufficiently large to provide thesame level of security as 1024-bit standard RSA. Our conclusions are three fold:9

1. 1024-bit integers of the form N = p2 q provide adequate security in the short term.
However, within 5 to 10 years the safety margins provided by such integers is likely to
become unacceptable.
2. To provide security comparable to standard 1024-bit RSA it is recommended to use atleast a 1280-bit N = p2 q modulus. We estimate that the running time for ECM on sucha modulus is comparable to the running time of the Number Field Sieve on 1024-bit RSA(note that we are ignoring memory-space constraints).
3. 1024-bit integers of the form N = p3 q should be considered insecure since today they
are susceptible to attack using the ECM method. The ECM can be adapted to N = p3 q
using a generalized Okamoto-Peralta improvement (generalized to make use of the cubic
symbol rather than the Legendre symbol).
We also pointed out in section 3 that integers of the form N = p2 q have more structure thanstandard RSA moduli. We showed that this may lead to new factoring algorithms specificallytargeted at N = p2 q. Hence, factoring N = p2 q might be easier than factoring N = pq ofthe same size. However, we cannot currently exploit the extra structure of N = p2 q to design
faster factoring algorithms.

References[1] D. Boneh, G. Durfee, and N. Howgrave-Graham. “Factoring N = pr q for Large r.” Proceedings of Crypto ’99, vol. 1666 of LNCS, pp. 326–337. Springer-Verlag, 1999.
[2] S. Cavalar et al. “Factorization of a 512-bit RSA Modulus”, Proc. of Eurocrypt ’2000.
[3] A. Fujioke, T. Okamoto, and S. Miyaguchi. “ESIGN: an efficient digital signature implementation for smartcards”, In. proc. Eurocrypt ’91, pp. 446–457, 1991.
[4] K. Ireland and M. Rosen “A classical introduction to modern number theory”, 2nd edition,
GTM 84, Springer, 1990.
[5] A. Lenstra and H.W. Lenstra Jr.. “Algorithms in Number Theory”, in Handbook ofTheoretical Computer Science (Volume A: Algorithms and Complexity), ch. 12, pp. 673–
715, 1990.
[6] A. Lenstra and H.W. Lenstra Jr.. “The development of the number field sieve”, Lecture
Notes in Mathematics, Vol. 1554, Springer-Verlag, 1994.
[7] H.W. Lenstra Jr.. “Factoring integers with elliptic curves”, Annuals of Mathematics,
126:649-673, 1987.
[8] P. Montgomery. “Speeding up the Pollard and Elliptic Curve methods of factorization”,
Math. Comp. Vol. 48 (1987), pp. 243–264.
[9] P. Montgomery and R. Silverman. “An FFT extension to the p − 1 factoring algorithm”,
Math. Comp. Vol. 54 (1990), pp. 839–854.
10[10] T.Okamoto. “A Fast Signature Scheme Based on Congruential Polynomial Operations”,
IEEE Trans. on Inform. Theory, IT-36,1 (1990) 47–5
[11] E.Okamoto and R.Peralta. “Faster Factoring of Integers of a Special Form”, IEICE Transactions on Fundamentals of Electronics, Communications, and Computer Sciences, E79-A,
n.4 (1996).
[12] T.Okamoto and A.Shiraishi. “A Fast Signature Scheme Based on Quadratic Inequalities”,
Proc. of the ACM Symp. Security and Privacy, ACM Press (1985)[13] T. Okamoto and S. Uchiyama. “A new public key cryptosystem as secure as factoring”,
in Proc. Eurocrypt ’98, pp. 310–318, 1998.
[14] R. Silverman and Wagstaff Jr.. “A Practical analysis of the elliptic curve factoring algorithm”, Math. Comp. Vol 61, 1993.
[15] I. Miyamoto. Report on ECM-net, Oct. 2001.
http://www.loria.fr/ zimmerma/records/ecmnet.html[16] T. Takagi. “Fast RSA-type cryptosystem modulo pk q”, in Proc. Crypto ’98, pp. 318–326,
1998.

11