Questions tagged [nt.number-theory]
Questions in number theory
110 questions
4
votes
1
answer
160
views
Logspace computation of Zeckendorf representation
By Zeckendorf's theorem any given integer can be represented as sum of Fibonacci numbers.
Given $n\in\mathbb N_{\geq 3}$ is there a logspace algorithm to represent $n$ as sum of $O(polylog(n))$ ...
- 13.3k
2
votes
0
answers
103
views
Ranges that work in the $\mathsf{NP}$ hardness variant of integer factorization
In this post on whether a variant of integer factorization
$$\mathsf{}\mbox{ }{\Pi} = \{\langle a, b, n \rangle \;|\; \exists \mbox{ } \mathsf{ an}\mbox{ }\mathsf{ integer}\mbox{ } m \in [a, b]\mbox{ ...
- 13.3k
0
votes
1
answer
137
views
Time complexity of square root floor
Given a square number in $n$ bits can we compute its square root in $O(n)$ time?
In general can we compute $\lfloor\sqrt{a}\rfloor$ in $O(\log a)$ time?
- 13.3k
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
7
votes
0
answers
82
views
Tree of addition chains
Addition chains are a well-known way of building up a number from 1 by adding two previously computed numbers. It is a long-standing open problem to determine the complexity of computing the length of ...
- 14.2k
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
10
votes
2
answers
383
views
Algorithm to check whether a given set is Sidon
We call a set of natural numbers $\mathcal S$ to be a Sidon Set if $a+b=c+d$ for $a,b,c,d\in \mathcal S$ implies $\{a,b\}=\{c,d\}$. In other words, all pairwise sums are distinct.
What algorithms do ...
- 203
-3
votes
2
answers
198
views
pq factorization
If I tried to factor a semiprime as the product of the two prime factors given below in the form pq on a home computer would I be successful?
p=(2^1024-1)+644 prime factor
q=(2^1028-1)+188 prime ...
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
0
votes
1
answer
147
views
What is a known sequence for which being constant is not provable?
My question concerns the property of being constant for computable functions ${\mathbb N}\to \{0,1\}$, within any common framework $T$ strong enough to include Heyting arithmetic (and of course not ...
- 505
21
votes
2
answers
1k
views
Decidability of diophantine equations over {=, +, gcd}
It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, ...
- 892
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
9
votes
1
answer
495
views
Formalizing the "no formula for primes" intuition
I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt:
Conjecture: There is no $O(n^2)$ expected time randomized algorithm to generate $\ge n$-...
- 3,313
0
votes
0
answers
48
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
239
views
Analytic Number theory in TCS [closed]
Are there any applications of analytic number theory in TCS?
- 31
2
votes
0
answers
83
views
is factoring harder than deciding if all prime factors lie in a particular residue class?
Let $n$ be a large positive integer. Suppose I want to know if all the prime factors of $n$ are congruent to, say, 3 mod 8. Is this any easier than just factoring $n$?
- 241
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
14
votes
4
answers
654
views
Base-k representations of the co-domain of a polynomial - is it context-free?
In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open:
Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for ...
- 411
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
0
votes
1
answer
100
views
Does this pairwise independent random process have expected max load $\sqrt{n}$?
This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ . There the following question is asked and answered in ...
- 3,912
1
vote
1
answer
350
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,071
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
10
votes
1
answer
353
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
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
3
votes
0
answers
51
views
Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?
Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ is irreducible what is the best technique to factor such ...
- 13.3k
8
votes
0
answers
321
views
Algorithms to generate consecutive primes
The prime number theorem, states that the "average length" of the gap between a prime $p$ and the next prime is ln(p). I am looking for (preferably deterministic efficient) an algorithm that generates ...
- 21.1k
6
votes
2
answers
292
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
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
10
votes
1
answer
820
views
Comparing two products of lists of integers?
Suppose I have two lists of positive integers of bounded manitude, and I take the product of all elements of each list. What's the best way to determine which product is larger?
Of course I can ...
- 233
22
votes
5
answers
854
views
Easy problems with hard counting versions
Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-...
- 13.3k
2
votes
1
answer
122
views
Factoring assuming smoothness of some numbers
I have came across a lot of factorization methods and most of them seem to assume smoothness of some numbers.
For example
When $p-1$ is smooth
When $|E(\mathbb{F}_p)|$ is smooth. (Elliptic curve ...
- 243
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
18
votes
0
answers
383
views
Does Factoring have a Statistical Zero Knowledge Proof?
The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to ...
- 3,888
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
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
-2
votes
1
answer
148
views
A curious statement in an old blog
In http://blog.computationalcomplexity.org/2009/08/finding-primes.html, a statement is added which reads "Oddly enough we would usually prefer a probabilistic over the deterministic method to find ...
- 13.3k
-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
12
votes
1
answer
425
views
Which complexity class does this number theory problem belong to?
'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete.
Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?
user34945
19
votes
1
answer
1k
views
Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$
In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his ...
3
votes
1
answer
342
views
Two rectangles whose sum of areas is given
Given is $\mathcal{P} \in \mathbb{Z}$. Are sought two rectangles which edges have integer, positive value and sum of their areas is $\mathcal{P}$. Find this two rectangles, if you know that sum of ...
- 149
4
votes
0
answers
160
views
Is there a PPAD algorithm for computing primes that sum to even numbers?
Goldbach's conjecture states that every even number greater than 2 can be expressed as the sum of 2 primes.
I'm interested in this function problem:
Given an even natural number n greater than 2, ...
user1338
0
votes
0
answers
73
views
Finding exact value with a quotients of products of random values
Sorry for the haphazard title: really not sure what this should be called
Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime).
...
- 149