All Questions
Tagged with nt.number-theory cc.complexity-theory
45 questions
0
votes
0
answers
83
views
Evidence extended GCD is in $TC^0$
Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes ...
- 13.3k
1
vote
0
answers
119
views
What would be the cost to factor a 1024‒bits RSA modulus most economically within months today?
Of course this is a question with an answer that is due to evolve.
A 2002 paper about TWIRL stated that the cost would be around 10M$$ and an other 10M$ to manufacture the devices. A later 2007 paper ...
- 111
3
votes
1
answer
284
views
Is modular square roots modulo primes in $NC$?
Assume modulus is prime. Is modular square roots then in $NC$?
If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
- 13.3k
1
vote
0
answers
104
views
On the borderline between natural and artificial problems
While there is no formal definition of what constitutes a natural algorithmic problem,
in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
- 11.4k
3
votes
0
answers
302
views
Is the following equitable factoring problem $NP$-hard or in $P$?
Consider the following factoring problem:
Given an integer $r$ and another integer $N$ along with all of its $n$ number of prime factors and their corresponding multiplicities $\{p_i,e_i\}_{i=1}^n$, ...
- 13.3k
5
votes
2
answers
273
views
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
Since $e$ is transcendental, the function $f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$ is injective,
$$ f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots ...
- 2,204
20
votes
1
answer
526
views
Is prime-counting function #P-complete?
Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function. By "PRIMES in P", computing $\pi(n)$ is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to ...
- 812
1
vote
0
answers
106
views
Complexity of planted root of a system of quadratic homogeneous polynomials?
Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\dots=f_{m}=...
- 13.3k
5
votes
1
answer
215
views
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total ...
- 13.3k
14
votes
1
answer
1k
views
Deciding whether an interval contains a prime number
What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the ...
3
votes
0
answers
277
views
Primality in $NC$ hierarchy?
AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following:
Input: integer n > 1.
Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b &...
- 13.3k
5
votes
0
answers
148
views
How hard is it to generate a set of relatively prime numbers between two given bounds?
Informal Question
How hard is it to generate a set of relatively prime numbers between two given bounds?
Decision Problem
Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \...
- 5,167
2
votes
1
answer
166
views
Is there any time efficient way of achieving the result of FKS hashing lemma?
FKS hashing lemma states.
Given a set of $n-$bit numbers $\{x_1,x_2,\dots,x_k\}$ there exist a
prime $p$ of $O(\log n + \log k)$-bit such that $x_i$ mod $p \neq $
$x_j$ mod $p$ if $x_i \neq x_j$...
- 103
6
votes
0
answers
322
views
Is there any algorithm outputing $e$ in real time?
The Hartmanis-Stearns Conjecture says that a number computed in real time by a Turing Machine is either rational or transcendental. We know that there is some transcendental (Liouville) number that ...
- 1,071
4
votes
1
answer
1k
views
Is Hartmanis-Stearns conjecture settled by this article?
The paper
"On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited"
by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec
https://arxiv.org/abs/1601....
- 1,071
1
vote
0
answers
99
views
Computing the class number using the prime factorization of the discriminant
i was wondering if there is a way to use the prime factorization of the discriminant $d$ when computing the class number $h(d)$. E.g., assume you have an integer $n = pq$ with $p \equiv 1\pmod{4}$ and ...
- 615
1
vote
0
answers
90
views
Counting points on curves
It is known (see "Counting curves and their projections" (free version) by von zur Gathen, Karpinski, and Shparlinski) that the problem of finding the number of $\mathbb{F}_q$-rational points on a ...
- 2,023
7
votes
0
answers
176
views
Recognition of a primitive root
Adleman and McCurley published a paper in 1994 called "Open problems in number theoretic complexity, II" (http://ww.cstheory.com/papers/open.ps.gz)
Problem 18 of this list of open problems is about ...
- 560
3
votes
0
answers
118
views
Number theoretic problems complete for $\mathsf{RL}$
Are there number theoretic problems (such as those related to $\mathsf{gcd}$) that are in $\mathsf{RL}$?
Can these also be $\mathsf{RL}$-complete problems (is there any $\mathsf{RL}$-complete ...
user34945
-3
votes
1
answer
427
views
Consequences of polynomial time algorithm to variant of integer factorization
Given $N,U,V\in\Bbb N$ is there $n\in[U,V]\cap\Bbb N$ such that $n|N$ is $\mathsf{NP}$-complete modulo Cramer's conjecture on prime gaps is shown in An NP-complete variant of factoring.
So supposing ...
- 13.3k
6
votes
1
answer
306
views
Integer factorization using polynomial whose roots are prime factors
Let $n$ be a square-free positive integer, let $n=p_{1}p_{2}\ldots p_{k}$
be the prime factorization of $n$ into $k$ distinct primes $p_{i}$.
For such $n$, define $F_{n}(x)\triangleq\prod_{i=1}^{k}(x-...
- 727
8
votes
2
answers
835
views
Is square removal easier than factoring?
It seems to me that the square removal task can be reduced to the factoring task, but that there is no way to reduce factoring to square removal. Is there a way to make this "feeling" more precise, i....
- 3,103
8
votes
1
answer
883
views
Downward self-reducibility of factorization
Is integer factorization downward self-reducible? Is anything known about this?
- 727
6
votes
0
answers
108
views
Unique factorization representation and complexity
Suppose that $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$ with $p_i$ prime and $a_i \geq 1$.
Given a representation of the factorization of $N$ and an integer $m$ (using alphabet $\Sigma = \{0,1,,\}$):
...
- 23.2k
6
votes
1
answer
341
views
Complexity of factorial exponent over composite moduli
I know that computing factorial modulo a composite number has no fast algorithm and showing non-polylogarithmic lower bound in BSS model for factorial would separate P from NP in that model.
Given $a\...
- 13.3k
3
votes
1
answer
2k
views
What NP-complete problems are most similar to integer factoring?
The exact complexity of factoring integers (the decision problem) is a major open question in TCS (with important implications, especially in cryptography because of the RSA algorithm), and is widely ...
- 11.1k
15
votes
1
answer
898
views
Is there a quantum NC algorithm for computing GCD?
From the comments on one of my questions on MathOverflow
I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer ...
- 13.3k
27
votes
2
answers
1k
views
Complexity of factoring in number fields
What is known about the computational complexity of factoring integers in general number fields? More specifically:
Over the integers we represent integers via their binary expansions. What is the ...
- 5,813
1
vote
0
answers
133
views
Computational Complexity of RESTRICTED primality testing
Input: Any number $n \in \mathbb{Z}^+$ that can be represented in the form of $n = 2^a + b,\ |b|= c $.
output: YES if $n$ is prime , else NO .
Now, length of binary input is $\log(a) + O(1)$ which ...
- 1,311
4
votes
0
answers
189
views
Complexity of computing logarithm of a prime power
Suppose $n = p^k$ for some prime number $p$ and some non-negative integer $k$. What is (the best-known upper bound on) the complexity of computing $k$ on input $n$ (given in binary)? It is important ...
- 2,291
33
votes
5
answers
3k
views
Is there a natural problem on the naturals that is NP-complete?
Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
- 14.2k
6
votes
0
answers
293
views
Find the maximum set whose subset sum is unique for every of its subset
We are given a set of $n$ positive integers.
We assume all of them are bounded by a polynomial of $n$.
We would like to find a subset $S$ of these $n$ numbers such that
for any $T_1,T_2\subseteq S$, ...
- 769
19
votes
1
answer
958
views
Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?
I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically:
Problem. For a given system of $m$ linear equations ...
- 8,939
30
votes
2
answers
1k
views
How hard is it to count the number of factors of an integer?
Given an integer $N$ of length $n$ bits, how hard is it to output the number of prime factors (or alternatively number of factors) of $N$?
If we knew the prime factorization of $N$, then this would ...
- 10.3k
3
votes
1
answer
478
views
Arthur-Merlin protocol with BQP power
Context: Aaronson raised the following question:
Let f be a black-box function, which is promised either to satisfy the
Simon promise or to be one-to-one. Can a prover with the power of BQP
...
- 195
7
votes
2
answers
298
views
Complexity class of phase information in Gauss sum
Have number theoretic functions such as Gauss sums been studied from a complexity view point? Where can I get a good introduction into complexity of Gauss sum estimation (beyond the quadratic case)?
...
- 2,228
1
vote
2
answers
352
views
How to calculate the cost of factoring a large integer?
I would like to know how much it would cost to factor a large integer. The cost can be given computer operations, time to process it or even monetary value. I know there are people that factored 200 ...
- 133
11
votes
3
answers
1k
views
Can Merlin convince Arthur about a certain sum?
Merlin, who has unbounded computational resources, wants to convince Arthur that
$$m|\sum_{p\le N,\ p\text{ prime}}p^k$$
for $(N,m,k)$ with $k=O(\log N)$ and $m=O(N).$ Computing this sum in the ...
- 1,745
37
votes
1
answer
1k
views
Efficiently computable function as a counter-example to Sarnak's Mobius conjecture
Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis.
Conjecture. Let $\mu(k)$ be ...
- 7,668
28
votes
2
answers
1k
views
Finding a prime greater than a given bound
Is a deterministic polynomial-time algorithm known for the following problem:
Input: a natural number $n$ (in binary encoding)
Output: a prime number $p > n$.
(According to a list of open ...
- 751
7
votes
2
answers
367
views
Complexity of summing up integral powers
Let $x$ be a rational number, and $S_n(x)= \sum_{1\leq i\leq n} i^x$. What is the complexity of computing $S_n(x)$ correct to $d$ decimal places? Is this a Hard problem?
It is clear from Faulhaber's ...
- 521
4
votes
1
answer
229
views
Computing Size of Set with Particular Jacobi Symbol in Poly-Time
Background
Let $(\tfrac{a}{p})$ denote the Legendre symbol, defined for all integers $a$ and all odd primes $p$ by:
$(\tfrac{a}{p}) = \begin{cases}
\;\;\,0\mbox{ if } a \equiv 0 \pmod{p}
\\+1\mbox{...
- 16.6k
35
votes
3
answers
3k
views
complexity of greatest common divisor (gcd)
Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest ...
- 461
2
votes
0
answers
82
views
Algorithmic Number Theory Problem - related to Matrix Multiplication Complexity
Let $F(x) = \displaystyle\sum_{i=0}^{n-1}a_{i}x^{i}$, $G(x,y) = \displaystyle\sum_{i=0}^{n_{x}-1}\sum_{j=0}^{n_{y}-1}a_{ij}x^{i}y^{j} \in \mathbb Z[x,y]$ with $a_{i},a_{ij} \in [0,p-1]$ for some prime ...
- 13.3k
38
votes
3
answers
3k
views
Complexity of exponential function
We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs.
...
- 381