Questions in number theory

learn more… | top users | synonyms (1)

0
votes
0answers
40 views

On the size of residue classes

Let $n \in \mathbb{N}$ be a odd number. Let $S \subseteq \{1,3,5,7,...,n-2,n\}$ and $|S|$ is even number. Let $R_i^k=\{a \mid a \in S \text{ } \&\text{ } a\equiv i \text{ }(mod \text{ } k)\}$ ...
1
vote
0answers
71 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
109 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 ...
13
votes
0answers
137 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
139 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$...
2
votes
0answers
88 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
115 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
216 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
364 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?
16
votes
1answer
490 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
221 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
111 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
68 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
182 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
727 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....
5
votes
1answer
188 views

Downward self-reducibility of factorization

Is integer factorization downward self-reducible? Is anything known about this?
4
votes
1answer
121 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
168 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
134 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
103 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,,\}$): ...
-3
votes
1answer
539 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
324 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\...
10
votes
2answers
463 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
61 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
157 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 ...
4
votes
1answer
121 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
566 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 ...
18
votes
4answers
603 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 ...
11
votes
2answers
678 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
553 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
780 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
120 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 ...
8
votes
1answer
240 views

Comparing co-primes

Suppose we have two numbers factorized into their primes, represented as lists of (p,d), where all p are prime, and d are the power of p. Is there a way to compare such two numbers without converting ...
4
votes
0answers
155 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 ...
21
votes
4answers
867 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
votes
0answers
375 views

Semiprime factorization, Groebner bases and a Nullstellensatz certificate

Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ \sum_{k=1}...
0
votes
0answers
119 views

count number of i such that ( (a*i+b) mod p) mod k == l

How to determine the number of $i$'s as fast as possible such that $$1\le i \le L$ and $((ai+b)\mod p) \mod k = l$$ where $p$ is a prime number, $1\lt a, b\lt p-1$, and $l \lt k \lt L \lt p$. This ...
6
votes
1answer
275 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$, ...
23
votes
2answers
2k views

Implications of proof of abc conjecture for cs theory

What implications would a proof of the abc conjecture have for tcs? http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
11
votes
0answers
172 views

generalizing Ben-Or et al's two-prover bit commitment scheme beyond bits

In "Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions" by Ben-Or, Goldwasser, Kilian, and Wigderson, the authors introduce a bit commitment protocol as a subroutine to their ...
10
votes
2answers
327 views

Subset Numbering

Fix $k\ge5$. For any big enough $n$, we would like to label all subsets of $\{1..n\}$ of size exactly $n/k$ by positive integers from $\{1...T\}$. We would like this labelling to satisfy the following ...
13
votes
2answers
2k views

What is the “nearest” problem to the Collatz conjecture that has been successfully resolved?

I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ripe for such problems"). ...
3
votes
1answer
639 views

How to find the exact period of Blum-Blum-Shub random number generator?

I've read the original paper and some related ones. But the best I can find about the period of BBS is that the period is a factor of $λ(λ(M))$, where $λ$ is Carmichael function and $M$ is the product ...
5
votes
0answers
274 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$, ...
12
votes
2answers
540 views

Complexity of Membership-Testing for finite abelian groups

Consider the following abelian-subgroup membership-testing problem. Inputs: A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-...
17
votes
1answer
663 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 ...
1
vote
1answer
214 views

Question on ascending $k$-tuples of naturals whose sum is less or equal than $S$

Let $k$ and $S$ be fixed non-negative integers. Let us regard the following set of tuples $\{ (x_1,\dots,x_k)| x_i \leq x_{i+1}, \sum_j x_j \leq S \}$ I have got some questions on this set. Is ...
7
votes
1answer
280 views

Generating a Diffie Hellman tuple without “being able to know” one of the discrete logs involved

Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ...
29
votes
2answers
884 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 ...
2
votes
1answer
283 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 ...