5
$\begingroup$

My question is related to this question posted on math.SE:

Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper function $B$ which takes as its input $(N, k)$ and outputs True iff $N$ has a factor greater than or equal to $k$? Obviously, the factor cannot be itself.

My slightly altered problem statement goes like this.

Given an odd integer $n$, find its largest factor (that is not itself). You can call a function $B(m,k)$ that returns $1$ iff $m$ has a factor smaller than $k$. The function runs in constant time.

Can this be done faster than $O(\log n)$ in the average case (assuming the input is chosen uniformly at random)? Is my altered problem statement any better than the original? Specifically, I know that the probability some large number will have no factor smaller than $M$ is asymptotic to $\frac{1}{\log M}$ (see A, and B). Can you use this to your advantage?

You can also assume that division is constant time.

Edit and Attempt Solution:

$ \newcommand{\ha}[2]{\left[#1 \dots #2\right)} \newcommand{\expa}[1]{2^{#1}} \newcommand{\expb}[1]{2^{2^{#1}}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\expv}[1]{\mathrm{E}\left(#1\right)} \newcommand{\sch}{\mathbb{S}} \newcommand{\floor}[1]{\left\lfloor#1 \right\rfloor} \newcommand{\logb}[1]{\log \log #1} $ The difference between my problem statement and the original, is the definition of the function $B$. In the original, $B(N,k)$ returns $1$ if $N$ has a factor greater than or equal to $k$; in my version, this happens if $N$ has a factor less than $k$.

By making this change, I aim to capitalize on the fact that the probability of a large $N$ having no factors smaller than $M$ is asymptotic to $(\log M)^{-1}$. While this fact does not change the worst-case performance of an algorithm, it can change average-case performance. Here, by average case, I mean probabilistic analysis of the algorithm over random, uniformly distributed inputs.

(Note that my question involves only exact algorithms)

I conjectured in my comment to the related question that you can benefit from the probability by changing the way in which you partition your search space when performing a binary search (since it is much more likely for the solution to be in $\ha{1}{1000}$ instead of $\ha{1000}{N}$). I also conjectured the algorithm could run in $O(\logb N)$ average-case.

Attempted Solution

I decided to do some work on the problem myself, and I think I have a solution. I haven't really done this sort of analysis previously, so I may have some error, and there is definitely a lot missing in terms of details. I think the idea is correct, though. Note that here I find the smallest factor of $N$. We can easily find the largest factor by division (which I assume to be contstant time).

I'm posting it as part of the question because I'm not sure if it's correct, and I still want to know if there's a better way.

Let us partition the search space $\sch = \ha{1}{N}$ into disjoint integer intervals, $$ r_k = \ha{\expb k}{\expb {k+1}} \qquad 0 \leq k \leq \floor{\logb N}$$

Note that it can be that, $$ \expb{\floor{\logb N+1}} > N$$ That doesn't really matter; all we want from the partitioning $r$ is to contain the entire search space.

Now, the probability that the smallest factor of $N$, which we will call $A$, is greater than $m$ is asymptotic to $(\log m)^{-1}$. Then let, $P(A > \expb{k}) = 2^{-k}$, where $A$ is taken to be a random variable. If we let $P(r_k)$ denote the probability that $A \in r_i$, we can calculate this as: $$P(r_k) = P(a > \expb{k}) - P(a > \expb{k+1}) = 2^{-(k+1)}$$

We can identify which partition $r_k$ contains $A$ by calling the function $B(N,\expb{k})$ up to $\floor{\logb N} + 1$ times. After finding the $r_k$, we then perform a binary search for $A$ in the partition, which involves $\log \abs{r_k}$ operations. Here we note that: $$|r_k|=\expb{k+1}-\expb{k} = \expb{k}\left(\expb{k} - 1\right)\leq \expb{k+1}$$

Let $X$ be a random variable representing the number of operations taken by the binary search. The value of $X$ for the case when $A \in r_k$ is given $X_k = \log \expb{k+1} = 2^{k+1}$. The expected value of $X$ is then, $$\expv{X} = \sum_{k=0}^{\floor{\logb N} + 1} X_i P(r_i) = \sum_{k=0}^{\floor{\logb N} + 1} 2^{k+1}\cdot 2^{-(k+1)} = \floor{\logb N} +1$$

Notes

I've considered partitioning the search space using triple-exponentiation (e.g. $\expa{\expb{k}}$), but that provides no benefit. There might be a way to make the search algorithm inside the partitions faster though, but I'm not sure how.

You can also reduce the search space drastically (such as to something like $\sqrt{N}$), but I think this will have a constant speedup at most.

$\endgroup$
  • $\begingroup$ I don't see much difference, except that you got rid of "constant-time". Note that you move all complexity to the oracle $B$ (which I assume you say has constant runtime?); see also here and here. Are you interested in an exact algorithm, a randomized guarantee or a heuristic? $\endgroup$ – Raphael Aug 16 '13 at 11:32
  • $\begingroup$ I'll edit my question to make it clearer. Even though most of your comments are already answered in the body. $\endgroup$ – GregRos Aug 17 '13 at 8:26
  • $\begingroup$ @Raphael To clarify, I am aware of that I'm moving the complexity to $B$. Also, I don't understand why you provided those links. $\endgroup$ – GregRos Aug 17 '13 at 15:20
  • 2
    $\begingroup$ Traditionally, factoring algorithms have been considered in the adversarial setting (so to speak) because of cryptographic applications. In particular, it is common to analyze them in the case where $n = pq$, with $p \approx q$ being primes. You're right that there are uses of factoring outside of cryptography, and so it does make some sense to analyze factoring in the average case. $\endgroup$ – Yuval Filmus Aug 17 '13 at 15:35
  • $\begingroup$ To be honest, I hadn't thought about practical uses and that sort of thing. The problem just seemed interesting. $\endgroup$ – GregRos Aug 17 '13 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.