Questions in number theory

learn more… | top users | synonyms (1)

2
votes
0answers
98 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
0answers
41 views

Is there a complexity bound on operation $\cdot$ in a ring that is anti-commutative and commutative?

For elementary arithmetic, we know the Big O-time/complexity for $+$ (addition) and $\cdot$ (mutliplication). (So we know the big-O time for calculating $1+2$ and $1 \cdot 3$.) What if we escape ...
1
vote
1answer
104 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
95 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
273 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
304 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 ...
9
votes
2answers
239 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
54 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?
0
votes
1answer
120 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
114 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 ...
2
votes
1answer
354 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
580 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
384 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 ...
12
votes
1answer
463 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 ...
23
votes
2answers
644 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
106 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
238 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
140 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 ...
20
votes
4answers
641 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
316 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+ ...
0
votes
0answers
112 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
230 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$, ...
21
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
163 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
311 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 ...
9
votes
1answer
1k 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"). ...
2
votes
1answer
415 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
248 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
462 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 ...
17
votes
1answer
584 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
171 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 ...
6
votes
1answer
237 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, ...
28
votes
2answers
781 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 ...
2
votes
1answer
255 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 ...
3
votes
0answers
175 views

Time complexity for solving linear congruences?

what is the best known algorithm to solve linear congruences like $a x + b \equiv (n)$? And what's the time complexity of it?
10
votes
1answer
273 views

Reducing factoring prime products to factoring integer products (in average-case)

My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. Assuming the problem of FACTORING:[Given ...
7
votes
2answers
200 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)? ...
1
vote
0answers
161 views

The Number of Short Vectors in a Lattice [closed]

Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the ...
0
votes
2answers
249 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 ...
7
votes
4answers
746 views

Approaching Number Theory conjectures through Graph Theory

i try to find if there was an attempt to prove any famous Number Theory conjectures like Goldbach conjecture or Twin Prime conjectures through Graph Theory. I have in my mind something like the ...
15
votes
2answers
655 views

Collatz Conjecture & Grammars / Automata

I was wondering if there is a good bibliography of attempts to investigate the Collatz conjecture as a formal grammar? (or any other attempts in the CS community to deal with this class of generative ...
11
votes
3answers
730 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 ...
8
votes
1answer
221 views

Sum of products with bounded coefficients

The following lemma is not hard to prove. Lemma : Let $c_1 \neq c_2 \neq \dots \neq c_r \in [n]$ and $k \in [n]$. If $m_1, m_2, \dots, m_r$ are integers (some of them might be negative) such that ...
32
votes
1answer
858 views

Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

Recently Gil Kalai and Dick Lipton both wrote a nice article on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and Riemann Hypothesis. Conjecture. Let $\mu(k)$ be ...
23
votes
2answers
816 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 ...
7
votes
2answers
240 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 ...
4
votes
1answer
207 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} ...
11
votes
1answer
458 views

“Overflow” in Extended Euclidean Algorithm

Sorry if I'm mistaken with the place to ask the question (maybe I should go to stackoverflow.com/mathoverflow.net?). I wonder if there is a proof that when evaluating extended Euclidean algorithm the ...
12
votes
0answers
350 views

Reference request: a more complete “faster factorization into coprimes”

Some months ago, before the advent of "CS-Theory", I asked a question on MathOverflow about efficiently factoring an integer N into coprime factors n1 and n2, where n1 is a multiple of a given a ...
26
votes
2answers
1k 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 ...