<p>For my question take the decision form of factorization: given <span class="math-container">$n$</span>, <span class="math-container">$k$</span> natural numbers, is there a prime factor of <span class="math-container">$n$</span> less than <span class="math-container">$k$</span> ? The family of uniform distributions <span class="math-container">$(D_n)_{n\text{ composite number}}$</span> on the sets <span class="math-container">$L_n$</span> of pairs of positive integers <span class="math-container">$(n,k)$</span> with <span class="math-container">$3&lt;k&lt;\lfloor\sqrt n\rfloor+1$</span>, encoded as the concatenation, separated by an extra symbol #, of <span class="math-container">$n$</span> and <span class="math-container">$k$</span> written in binary with a fixed number of digits <span class="math-container">$|\lfloor\sqrt n\rfloor+1|$</span> for all <span class="math-container">$k$</span>, thus with zeros on the left for <span class="math-container">$k$</span> of shorter binary expansions. Then for a composite natural number <span class="math-container">$n$</span> the length of instances in the decision problem <span class="math-container">$L_n$</span> is <span class="math-container">$|n|+|\lfloor\sqrt n\rfloor|+1$</span>, the cardinality of <span class="math-container">$L_n$</span> is <span class="math-container">$\lfloor\sqrt n\rfloor-1$</span>, and the finite distribution <span class="math-container">$D_n$</span> attributes constant weight <span class="math-container">$D_n(x)=\frac{1}{\lfloor\sqrt n\rfloor-1}$</span> to each <span class="math-container">$x\in L_n$</span>. We have <span class="math-container">$2^{|n|}-\pi(n)$</span> pairwise disjoint finite languages <span class="math-container">$L_n$</span> for a given length of instance <span class="math-container">$|n|+|\lfloor\sqrt n\rfloor|+1$</span> as we exclude primes. The language <span class="math-container">$L=\bigcup_{n\text{ composite}} L_n$</span> is the decision form of the factoring problem with the above encoding. I have lumped together all <span class="math-container">$k$</span> up to <span class="math-container">$\lfloor\sqrt n\rfloor+1$</span> and defined the distribution on all instances regardless of the actual size of <span class="math-container">$k$</span>, padding to the maximal possible size. I think that should not affect the question i am asking here, but we could refine the distribution to languages <span class="math-container">$k$</span> of fixed length; we then have to choose an enumeration of finite languages and distributions indexed by two lengths. Here i use a family of finite distributions; this can be converted into the formalisms for distributional complexity that use a single discrete distribution <span class="math-container">$\mathcal D$</span> on all strings - here ternary with the above format. The conditional probabilities of <span class="math-container">$\mathcal D$</span> on <span class="math-container">$L_n$</span> given <span class="math-container">$n$</span> as piece of string before the separator symbol # are <span class="math-container">$D_n$</span> - one can find an example of this correspondence in <a href="https://arxiv.org/pdf/cs/0606037" rel="nofollow noreferrer">this survey</a>, Section 5, though the definitions are not exactly the same as here.</p>
<p>Is it plausible that the distributional problem <span class="math-container">$\left(L,(D_n)_{n\text{ composite number}}\right)$</span> be in <span class="math-container">$\mathsf{AvgP}$</span> ?</p>
<p>Anyone is welcome to propose answers for other distributions or choices of encoding, also to the question with restrictions on pairs considered, for instance <span class="math-container">$k\in\left(n^\epsilon,n^{1/2-\epsilon}\right)$</span> for some <span class="math-container">$\epsilon\in\left(0,\frac{1}{4}\right)$</span>. I have not thought much about it, i am just trying to get a sense of the probability that we live in Impagliazzo's Cryptomania; i probably miss basic intuitions, but a short search has not yielded anything - GPT4 gives general references on factoring, nothing which treats general average-case complexity, as opposed to that of particular algorithms. It is possible that sieve methods allow one to reduce the problem on <span class="math-container">$L$</span> to subsets <span class="math-container">$L'\subset L$</span> in such a way that instances in <span class="math-container">$L\setminus L'$</span> are much easier to decide than those in <span class="math-container">$L'$</span>. I would be happy to hear additional comments on other questions about the relation between <span class="math-container">$\mathsf{AvgP}$</span> and <span class="math-container">$\mathsf{BQP}$</span>. Generalization the question above, is it plausible that <span class="math-container">$\mathsf{BQP}\subseteq\mathsf{AvgP}$</span>, for reasonable distributions like above ? I believe the reverse inclusion more likely, is anything known in this direction ? Thank you.</p>
<p>EDIT: I wrote egregious errors, confusions, in previous versions of this question, to the point that it was nonsense. Hopefully it is understandable now. I apologize, thank the moderators for their tolerance, and will welcome corrections and suggestions.</p>

CC BY-SA 4.0
2024-09-27T13:02:12.137Z
For the uniform distribution in the first paragraph, does the algorithm “if $k\ge\sqrt n$, answer YES iff $n$ is composite, otherwise run a $2^{|n|^{1/3+o(1)}}$-time factoring algorithm” work?
Emil Jeřábek
CC BY-SA 4.0
2024-09-27T14:38:44.097Z
@EmilJeřábek, thank you. Yes, i did not pay attention to the $\sqrt n$ threshold. One should restrict to composite $n$ and to $k<\sqrt n$. And if i have overlooked any trivial way to reduce to simpler algorithms on parts of the search space, presumably by sieve methods, please amend my question. The point is to find some simple and large enough sets of $(n,k)$ where factorization is hard - say $(n,k)$-squares-with-$n$-composite, or unions of "not too many" such squares, of cardinality $n^C$ for some $C>0$.
plm
CC BY-SA 4.0
2024-09-27T21:31:17.807Z
Please [edit] your question to state the problem accurately.  It appears that the problem statement in the question does not reflect what you actually want to ask.  We expect that the question be as accurate as you can make it -- people shouldn't have to read the comments to understand what you are asking.  What exactly is the distribution on $n$ and $p$ you are proposing?  I'm not sure what you mean by "restrict to...", as the distribution you propose does not restrict to composite $n$ and $k < \sqrt{n}$.  Did you mean some other distribution?
D.W.
CC BY-SA 4.0
2024-09-28T05:00:04.090Z
@D.W. Thank you and sorry for my vagueness, i didn't really know how best to present my question. I have amended my question. I welcome any guidance, my point is to understand a little what to expect for the average case hardness of inverting one-way functions if any exists - and here for a potential one.
plm
<quantum-computing><factoring><average-case-complexity>
Is factorization conjectured not to be in $\mathsf{AvgP}$?
plm
# Is factorization conjectured not to be in $\mathsf{AvgP}$?

(Asked by: username_0 on 2024-09-27)

For my question take the decision form of factorization: given $n$, $k$ natural numbers, is there a prime factor of $n$ less than $k$ ? The family of uniform distributions $(D\_n)\_{n\text{ composite number}}$ on the sets $L\_n$ of pairs of positive integers $(n,k)$ with $3, encoded as the concatenation, separated by an extra symbol #, of $n$ and $k$ written in binary with a fixed number of digits $|\lfloor\sqrt n\rfloor+1|$ for all $k$, thus with zeros on the left for $k$ of shorter binary expansions. Then for a composite natural number $n$ the length of instances in the decision problem $L\_n$ is $|n|+|\lfloor\sqrt n\rfloor|+1$, the cardinality of $L\_n$ is $\lfloor\sqrt n\rfloor-1$, and the finite distribution $D\_n$ attributes constant weight $D\_n(x)=\frac{1}{\lfloor\sqrt n\rfloor-1}$ to each $x\in L\_n$. We have $2^{|n|}-\pi(n)$ pairwise disjoint finite languages $L\_n$ for a given length of instance $|n|+|\lfloor\sqrt n\rfloor|+1$ as we exclude primes. The language $L=\bigcup\_{n\text{ composite}} L\_n$ is the decision form of the factoring problem with the above encoding. I have lumped together all $k$ up to $\lfloor\sqrt n\rfloor+1$ and defined the distribution on all instances regardless of the actual size of $k$, padding to the maximal possible size. I think that should not affect the question i am asking here, but we could refine the distribution to languages $k$ of fixed length; we then have to choose an enumeration of finite languages and distributions indexed by two lengths. Here i use a family of finite distributions; this can be converted into the formalisms for distributional complexity that use a single discrete distribution $\mathcal D$ on all strings - here ternary with the above format. The conditional probabilities of $\mathcal D$ on $L\_n$ given $n$ as piece of string before the separator symbol # are $D\_n$ - one can find an example of this correspondence in [this survey](https://arxiv.org/pdf/cs/0606037), Section 5, though the definitions are not exactly the same as here.

Is it plausible that the distributional problem $\left(L,(D\_n)\_{n\text{ composite number}}\right)$ be in $\mathsf{AvgP}$ ?

Anyone is welcome to propose answers for other distributions or choices of encoding, also to the question with restrictions on pairs considered, for instance $k\in\left(n^\epsilon,n^{1/2-\epsilon}\right)$ for some $\epsilon\in\left(0,\frac{1}{4}\right)$. I have not thought much about it, i am just trying to get a sense of the probability that we live in Impagliazzo's Cryptomania; i probably miss basic intuitions, but a short search has not yielded anything - GPT4 gives general references on factoring, nothing which treats general average-case complexity, as opposed to that of particular algorithms. It is possible that sieve methods allow one to reduce the problem on $L$ to subsets $L'\subset L$ in such a way that instances in $L\setminus L'$ are much easier to decide than those in $L'$. I would be happy to hear additional comments on other questions about the relation between $\mathsf{AvgP}$ and $\mathsf{BQP}$. Generalization the question above, is it plausible that $\mathsf{BQP}\subseteq\mathsf{AvgP}$, for reasonable distributions like above ? I believe the reverse inclusion more likely, is anything known in this direction ? Thank you.

EDIT: I wrote egregious errors, confusions, in previous versions of this question, to the point that it was nonsense. Hopefully it is understandable now. I apologize, thank the moderators for their tolerance, and will welcome corrections and suggestions.

**Tags:** quantum-computing, factoring, average-case-complexity

> **Comments:**
> **username_1**: For the uniform distribution in the first paragraph, does the algorithm “if $k\ge\sqrt n$, answer YES iff $n$ is composite, otherwise run a $2^{|n|^{1/3+o(1)}}$-time factoring algorithm” work?  
> **username_0**: @EmilJeřábek, thank you. Yes, i did not pay attention to the $\sqrt n$ threshold. One should restrict to composite $n$ and to $k<\sqrt n$. And if i have overlooked any trivial way to reduce to simpler algorithms on parts of the search space, presumably by sieve methods, please amend my question. The point is to find some simple and large enough sets of $(n,k)$ where factorization is hard - say $(n,k)$-squares-with-$n$-composite, or unions of "not too many" such squares, of cardinality $n^C$ for some $C>0$.  
> **username_2**: Please [edit] your question to state the problem accurately.  It appears that the problem statement in the question does not reflect what you actually want to ask.  We expect that the question be as accurate as you can make it -- people shouldn't have to read the comments to understand what you are asking.  What exactly is the distribution on $n$ and $p$ you are proposing?  I'm not sure what you mean by "restrict to...", as the distribution you propose does not restrict to composite $n$ and $k < \sqrt{n}$.  Did you mean some other distribution?  
> **username_0**: @username_2 Thank you and sorry for my vagueness, i didn't really know how best to present my question. I have amended my question. I welcome any guidance, my point is to understand a little what to expect for the average case hardness of inverting one-way functions if any exists - and here for a potential one.  

---

## 0 answers

