Questions tagged [comp-number-theory]
The comp-number-theory tag has no usage guidance.
43
questions
1
vote
0
answers
56
views
Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them
In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
3
votes
1
answer
248
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 ...
- 12.8k
0
votes
0
answers
45
views
Is this a proof that diophantine equation solutions can't be bounded by power towers?
From this 2017 paper on upper bounds for solutions to diophantine equations:
Conjecture 1. If a system of equations S ⊆ Bn has exactly one solution
in positive integers x1, . . . , xn , then x1, ....
1
vote
1
answer
230
views
Analytic Number theory in TCS [closed]
Are there any applications of analytic number theory in TCS?
- 31
7
votes
0
answers
122
views
Is finding square roots as hard as factoring, when coins are *public* and the square root oracle is adversarial?
Background: There is a well known argument (due to Rabin) that demonstrates that if one has access to an machine that computes square roots of elements in $\mathbb{Z}_n$, with $n = pq$, then $n$ can ...
- 1,439
20
votes
1
answer
509
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
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 ...
1
vote
0
answers
146
views
Fixed dimension Integer programming minus LLL in fixed parameter $NC$?
If you remove LLL part then is remaining part of
a. Lenstra algorithm
b. Barvinok algorithm
in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$ dimension, $m$ ...
- 12.8k
3
votes
0
answers
78
views
How to charactorize computational complexity based on finding solution to algebraic equations? [closed]
The Matiyasevich/MRDP Theorem relates two notions:one from computability theory, the other from number theory, thus Turing Machine and algorithms finding integral solution to algebraic equations can ...
- 1,058
1
vote
1
answer
324
views
Relation between transcendental numbers and computational complexity?
Regarding the relation, there is the Hartmanis-Stearns conjecture, but beyond Turing Machine of the realtime output, there is no further conjecture or theorem. Obviously irrational algebraic number ...
- 1,058
6
votes
0
answers
319
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,058
4
votes
0
answers
195
views
What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$
We know that Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable,so what is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$?
Is it equivalent to Tarski elimination ...
- 1,058
10
votes
1
answer
351
views
Algorithm to compute distance between powers
Given coprime $a, b$, can you quickly compute $$ \min_{x, y > 0} |a^x - b^y| $$
Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these ...
- 261
6
votes
2
answers
288
views
Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?
I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $&...
- 261
9
votes
2
answers
381
views
Any computable transcendental number that is computable in P time but not $O(n)$
Is there any known computable transcendental number such that its $n$th digit is computable in polynomial time, but not in $O(n)$?
- 1,058
2
votes
0
answers
119
views
What is the complexity of computation of zero point by Rieman zeta function?
What is the complexity of computation of zero point by Rieman zeta function?
That is, given s, whether ζ(s)=0? Is it in P? Any reference is appreciated.
- 1,058
-2
votes
1
answer
627
views
The factoring problem reduces to order finding or is it the other way around? [closed]
initially i was not at all equipped in theoretical computer science and knew only basics of number of theory.
I started working from scratch on the age old problem of primality testing which led me to ...
3
votes
0
answers
82
views
Finding degree two subfield
Let $K=\frac{\mathbb{Q}[x]}{<f(x)>}$ where $f(x)$ is irreducible over $\mathbb{Q}$ and has even degree. I want to find $K_2$ such that $ \mathbb{Q} \subseteq K_2\subseteq K$ and $[K_2:\mathbb{Q}]...
- 243
10
votes
0
answers
230
views
Does a polynomial-time algorithm for factoring product of two primes imply a polynomial-time algorithm for factoring in general?
Is it known if the existence of a polynomial-time algorithm for the promise problem of factoring of numbers with two prime factors implies that factoring in general has a polynomial-time algorithm?
- 101
7
votes
0
answers
173
views
Simplified lattices
Consider the following question:
Let $N$ be some large prime number, and suppose we are given $n$
uniformly independent samples $g_i$ from $0...,N-1$.
Think of $N$ as being exponentially large in $n$...
- 1,224
5
votes
1
answer
995
views
Computational complexity of modular power towers (tetration)
The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$.
The complexity of modular multiplication is open though some results ...
- 2,035
6
votes
1
answer
289
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
1
answer
823
views
Downward self-reducibility of factorization
Is integer factorization downward self-reducible? Is anything known about this?
- 727
4
votes
1
answer
144
views
Solving a system of sums-of-powers polynomials
What is the complexity of calculating the values of the integers $x_i$, where $0 \leq x_1 < x_2 < \dots < x_k < n$, given only the values $s_m = \sum_{i=1}^k x_i^m$? for $1 \leq m \leq k$?
...
- 11.2k
1
vote
1
answer
117
views
What is necessary and/or sufficient requirement for a subring of a field to be computable? [closed]
As title asks, what is necessary and/or sufficient requirement for a subring of a field to be a computable ring?
Conditions on either field or subring are fine.
- 11
2
votes
0
answers
269
views
Sieve Methods for Twin Primes - How to extract algorithm from formula
I am reading Cojocaru and Murty's Introduction to Sieve Methods and their Applications. They wait until Chapter 5 to discuss the Sieve of Eratosthenes for finding primes - and their version of it is ...
- 568
2
votes
1
answer
285
views
n irrational number whose digits are pseudo-random: conceptual mismatch?
Are there irrational numbers whose digits are considered pseudo-random?
Both concepts seem to be mismatched as a pseudo-random number generator typically is periodic and therefore generates a ...
- 29
13
votes
1
answer
878
views
Complexity class of this problem?
I am trying to understand to which complexity class the following problem belongs:
Exponentiating Polynomial Root Problem (EPRP)
Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients ...
- 2,216
12
votes
3
answers
3k
views
Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$
Sean Anderson published bit twiddling hacks containing the Eric Cole's algorithm to find the $\lceil\log_2 v \rceil$ of an $N$-bit integer $v$ in $O(\lg(N))$ operations with multiply and lookup.
The ...
- 223
5
votes
1
answer
275
views
Is the primality problem with unary input NLOGSPACE-Hard?
Consider the language $L=\{1^n : n \text{ is prime}\}$. Is this language NLOGSPACE-Hard?
The motivation for this question is that $L$ is a good candidate for reducing to other languages related to my ...
3
votes
1
answer
114
views
Complexity of higher order residues
Let $P$ be a prime. Given a number $a$, what is the computational complexity in establishing if $a$ is a cubic or higher order residue modulo $P$? Are there any good algorithms?
- 12.8k
1
vote
1
answer
221
views
What algorithms do you know for beltway reconstruction? [closed]
I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem?
Beltway Reconstruction Problem:
Assume there is a set of ...
- 179
6
votes
2
answers
193
views
Difference Sets
Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$
where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N} $$ and $p_k$'s are distinct.
We calculate the differences as: $$d=p_i-p_j\mod ...
- 179
19
votes
4
answers
706
views
How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?
Can anyone help me with the following problem?
I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K $ (for example $K=6$), given a list of $K^2$ values that correspond to the ...
- 193
5
votes
0
answers
93
views
How short can reversible representations of the n-bit primes be?
For $\: 1 < n \:$ and $\: n^{o(1)} < \sigma \leq n \:$, $\:$ how small can $L$ be for there to be for there to be an
efficiently computable (deterministic) function $\;\; f \: : \: \{0\hspace{....
user6973
15
votes
1
answer
857
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 ...
- 12.8k
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 ...
- 6,013
7
votes
1
answer
1k
views
Discrete log in GL(2,p)
Let $p$ be a large prime. Let $A$ be a $2\times 2$ matrix with coefficients in $GF(p)$ (i.e., coefficients taken modulo $p$). Let $B=A^k$, where $k$ is an integer not given to us. Given $p$, $A$, ...
- 11.7k
16
votes
1
answer
697
views
$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $?
While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post:
If, for every $n$, there exists a relation of the form
$$ (2^n)! = \sum_{k=0}^{m-1} ...
- 2,786
18
votes
3
answers
2k
views
Determinant modulo m
What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but ...
- 343
13
votes
4
answers
3k
views
Computing the Mobius function
The Mobius function $\mu(n)$ is defined as $\mu(1)=1$, $\mu(n)=0$ if $n$ has a squared prime factor, and $\mu(p_1 \dots p_k)= (-1)^k$ if all the primes $p_1,\dots,p_k$ are different. Is it possible to ...
- 515
7
votes
2
answers
287
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,208
12
votes
0
answers
277
views
Conditional density of primes
We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem.
My question is
about the density of primes when we choose random numbers from a ...
- 21.5k