# Time complexity of finding the largest factor of a number (using a specific oracle)

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}{\left[#1 \dots #2\right)} \newcommand{\expa}{2^{#1}} \newcommand{\expb}{2^{2^{#1}}} \newcommand{\abs}{\left|#1\right|} \newcommand{\expv}{\mathrm{E}\left(#1\right)} \newcommand{\sch}{\mathbb{S}} \newcommand{\floor}{\left\lfloor#1 \right\rfloor} \newcommand{\logb}{\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.

• 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?
– Raphael
Aug 16, 2013 at 11:32
• I'll edit my question to make it clearer. Even though most of your comments are already answered in the body. Aug 17, 2013 at 8:26
• @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. Aug 17, 2013 at 15:20
• 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. Aug 17, 2013 at 15:35
• To be honest, I hadn't thought about practical uses and that sort of thing. The problem just seemed interesting. Aug 17, 2013 at 15:49