Information Technology Reference
In-Depth Information
These numbers are admittedly big, but their size (they are twice exponential) is not
in itself an obstacle to a polynomial complexity. Nevertheless, it seems very unlikely,
or at least highly unwishable, that they be computable in a polynomial number of
steps, since this would provoke a cryptographic tsunami.
Let us first observe that, if the Pascaline has a polynomial complexity, the same
is true of the Factorial. Indeed, from the identity
2
(
2
·
U
)
!=
C
(
2
·
U
,
U
)
·
(
U
!
)
we deduce the following induction formula: Fact
n
(
u
0
,
u
1
,...,
u
n
)
=
(
1
+
u
0
(
u
1
·
2
n
2
2
.
In the other direction, it is not clear that a fast computation for the Factorial would
provide the same for the Pascaline, in the absence of division.
If the Factorial were easy to compute, then factorization would be possible using
the following well-known algorithm: consider two positive integers
U
+ ··· +
u
n
·
))
·
C
n
(
0
,
u
1
,...,
u
n
;
u
1
,...,
u
n
,
0
)
·
(
Fact
n
−
1
(
u
1
,...,
u
n
)
)
<
V
,givenin
figures; compute
U
: this decides whether or not
V
has
a factor smaller than
U
; in a small number of steps we localize the smallest factor of
V
, and finally discompose it.
We also consider two boolean functions, depending on some more boolean vari-
ables, which are the Pascaline and the Factorial in figures, defined by:
Pascfig
n
(
!
modulo
V
, and gcd
(
U
!
,
V
)
the
W
ↆ
digit of the representa-
u
0
,...,
u
n
;
v
0
,...,v
n
;
w
0
,...,w
n
)
=
tion of Pasc
n
(
u
0
,...,
u
n
;
v
0
,...,v
n
)
in base 2, where
W
=
w
0
+
2
·
w
1
+ ··· +
2
n
·
w
n
Factfig
n
(
the
W
ↆ
digit of Fact
n
(
u
n
)
These two (sequences of) functions belong to
PSPACE
. The best argument for
that is that every sequence of boolean functions appearing in an algorithmic con-
text belongs to
PSPACE
, unless it is manufactured to be a counter-example; for
something more formal, you may consult this time [
Poi08
]or[
Bür09
].
u
0
,...,
u
n
;
w
0
,...,w
n
+
log
(
n
)
)
=
u
0
,...,
8.3 Polynomials as Sums of Monomials
A Valiant summation is an expression of the form:
u
boolean
ϕ(
f
(
x
1
,...,
x
n
)
=
u
0
,...,
u
m
;
x
1
,...,
x
n
)
where
ϕ
is a polynomial in which we have separated the variables into two blocks.
This summation of exponentially many terms should have an explosive effect on the
complexity of polynomials, but this is an open question, We define the
-complexity
of
f
as the minimal complexity of
ϕ
. It seems unlikely that the Pascaline be of
polynomial
ˇ
ˇ
-complexity, but this fact, if false, should be hard to refute since it is
implied by
P
PSPACE
(the Pascaline is obtained from the Pascaline in figures by
a summation; see below the details on the exponential polynomial).
If it were true, it is not clear that it would imply a low
=
-complexity for
the Factorial, because the induction formula contains a square; the Fubini for-
ˇ
mula
u
ϕ(
v
ψ(v)
u
,v
ϕ(
u
)
·
=
u
)
·
ψ(v)
is valid only if the tuples of
