2008 | OriginalPaper | Buchkapitel
Running Time Predictions for Factoring Algorithms
verfasst von : Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali
Erschienen in: Algorithmic Number Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In 1994, Carl Pomerance proposed the following problem:
Select integers a
1
,
a
2
,...,
a
J
at random from the interval
[1,
x
]
, stopping when some (non-empty) subsequence,
{
a
i
:
i
∈
I
}
where I
⊆ { 1,2,...,
J
}
, has a square product
(that is
$\prod_{i\in I} a_i\in \mathbb Z^2$
).
What can we say about the possible stopping times, J
?
A 1985 algorithm of Schroeppel can be used to show that this process stops after selecting (1 +
ε
)
J
0
(
x
) integers
a
j
with probability 1 −
o
(1) (where the function
J
0
(
x
) is given explicitly in (1) below. Schroeppel’s algorithm actually finds the square product, and this has subsequently been adopted, with relatively minor modifications, by all factorers. In 1994 Pomerance showed that, with probability 1 −
o
(1), the process will run through at least
$J_0(x)^{1-o(1)}$
integers
a
j
, and asked for a more precise estimate of the stopping time. We conjecture that there is a “sharp threshold” for this stopping time, that is, with probability 1 −
o
(1) one will first obtain a square product when (precisely)
$\{e^{-\gamma}+o(1)\} J_0(x)$
integers have been selected. Herein we will give a heuristic to justify our belief in this sharp transition.