Cryptography Reference
In-Depth Information
(more specifically, b
L
), where e
i
= (log B)/(log
p
i
) , and trying to see if (b
L
- 1)
computing
and
n
have common factors.
Pollard's
p
- 1. Factors an integer,
a
, given a set of primes,
p
1
, ... ,
p
k
.
1. Set
b
= 2.
2. For each
i
in the range {1, 2, ... ,
k
} (inclusive), perform the following steps:
(a) Set
e
to be log(B)/log(p
i
) (the logarithm, base 10, of
B
divided by the logarithm of the
i
-th
prime), rounded down.
(b) Set
f
to be
p
e
i
(the
i
-th prime raised to the power of the above number).
(c) Set
b
=
b
f
mod
a.
3. Set
g
to be the GCD of
a -
1 and b.
4. If
g
is greater than 1 and less than b, then
g
is a factor of b. Otherwise, the algorithm fails.
I won't show an implementation of this algorithm, since it requires such a large list of primes.
3.3.4.1 Analysis of Pollard's p - 1
Pollard's
p
- 1 algorithm runs in time relative to the size of the upper-bound
B
. For each prime number less
than
B
≈
B
/ln
B
of them), we calculate
e
(assume this is negligible), then
f
(this takes log
2
e
operations), and
then
b
(this takes log
2
f
operations). This gives us a total of a bit more than
B
ln
B
operations to complete. This,
therefore, grows very large very fast, in terms of the largest prime number we are concerned with.
One optimization to this can be to pre-compute the values of
e
and
f
,since they will not change between runs,
saving us a little bit of time.
3.3.5 Square Forms Factorization
A method of factoring based on square forms, to be discussed in this section, was devised by Shanks in Refer-
ences [9] and [14].
Before we dive in to the Square Forms Factorization method (SQUFOF), I'll first set up a little of the math-
ematics.
Let the ordered triple of integers (a, b, c) correspond to all values of
ax
2
+ bxy + cy
2
for all integers
x
and y. We say that (a, b, c)
represents
some value
m
if, and only if, we can find two values
x
and
y
such that ax
2
+
bxy + cy
2
= m.
We say that two forms of (a, b, c) are
equivalent
if the two forms represent the same set of numbers. One
way in which this can be done is by a linear change of variables of
x
and
y
, where
x′ = Ax + By, y′ = Cx + Dy
,
and
AD - BC =
1 or -1. For example, if
A
= 1,
B
= 3,
C
= 1, and
D
= 4, then we would have
x
=
x
′ + 3
y
,
y
′ = ×
+ 4
y
, and
For example, (1, 1, 2) and (4, 26, 29) are equivalent.
Search WWH ::
Custom Search