Questions in number theory
12
votes
1answer
150 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 ...
4
votes
1answer
99 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 ...
0
votes
0answers
51 views
Modular and multiplication operations
Does
modular operation reduce to integer multiplication
integer multiplication reduce to modular operation
in fully linear time and/or in logarithmic time on linear number of processors?
14
votes
1answer
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 ...
2
votes
0answers
176 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 &...
5
votes
0answers
132 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 \...
2
votes
1answer
115 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$...
0
votes
1answer
69 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 ...
1
vote
1answer
190 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 ...
6
votes
0answers
284 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 ...
9
votes
1answer
308 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 ...
5
votes
1answer
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....
3
votes
0answers
44 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 ...
8
votes
0answers
190 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 ...
2
votes
1answer
152 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, $&...
1
vote
0answers
55 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 ...
11
votes
1answer
226 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 ...
21
votes
5answers
657 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$-...
3
votes
1answer
100 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 ...
1
vote
0answers
88 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 ...
8
votes
0answers
136 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 ...
17
votes
0answers
263 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 ...
8
votes
0answers
158 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$...
3
votes
0answers
102 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 ...
-2
votes
1answer
130 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 ...
-3
votes
1answer
269 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 ...
12
votes
1answer
382 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?
18
votes
1answer
772 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
1answer
251 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 ...
3
votes
0answers
126 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, ...
0
votes
0answers
70 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).
...
6
votes
1answer
221 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-...
8
votes
2answers
762 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....
6
votes
1answer
423 views
Downward self-reducibility of factorization
Is integer factorization downward self-reducible? Is anything known about this?
4
votes
1answer
133 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$?
...
2
votes
0answers
234 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 ...
2
votes
1answer
196 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 ...
6
votes
0answers
106 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,,\}$):
...
-1
votes
1answer
753 views
What is the most efficient algorithm to generate a sequence of prime numbers?
I know about algorithms like Sieve of Eratosthenes and Sieve of Atkin for generating prime numbers.
I would like to know what is the most efficient known algorithm to generate the sequence of $k$ ...
6
votes
1answer
335 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\...
11
votes
3answers
1k 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 ...
3
votes
1answer
85 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?
1
vote
1answer
180 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 ...
6
votes
2answers
170 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 ...
3
votes
1answer
688 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 ...
19
votes
4answers
630 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 ...
12
votes
2answers
1k views
What's the most efficient algorithm for Divisibility?
What is the most efficient (in time complexity) algorithm known nowadays for the Divisibity Decision Problem: given two integers, say $a$ and $b$, does $a$ divide $b$? Let it be clear that what I ask ...
13
votes
1answer
668 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 ...
25
votes
2answers
892 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 ...
1
vote
0answers
127 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 ...
