Questions tagged [nt.number-theory]
Questions in number theory
106
questions
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
290
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
6
votes
0
answers
108
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,,\}$):
...
- 23k
-1
votes
1
answer
1k
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$ ...
- 89
6
votes
1
answer
341
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\...
- 12.9k
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
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.9k
1
vote
1
answer
222
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
3
votes
1
answer
2k
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 ...
- 11k
19
votes
4
answers
711
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
13
votes
2
answers
2k
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 ...
- 341
15
votes
1
answer
869
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.9k
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,033
1
vote
0
answers
132
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 ...
- 1,281
8
votes
1
answer
253
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 ...
- 83
4
votes
0
answers
187
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 ...
- 2,281
31
votes
5
answers
3k
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 ...
- 14k
15
votes
0
answers
458
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}...
- 537
0
votes
0
answers
124
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 ...
- 121
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$, ...
- 12.1k
24
votes
2
answers
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/
- 357
11
votes
0
answers
190
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 ...
- 4,531
10
votes
2
answers
378
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 ...
- 2,247
19
votes
2
answers
6k
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 ...
- 11k
3
votes
1
answer
2k
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 ...
Lacek
6
votes
0
answers
293
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$, ...
- 769
13
votes
2
answers
902
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-...
19
votes
1
answer
939
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 equations ...
- 8,821
1
vote
1
answer
314
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 ...
- 1,165
7
votes
1
answer
588
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, ...
- 178
30
votes
2
answers
1k
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 ...
- 10.3k
2
votes
1
answer
468
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
...
- 185
4
votes
0
answers
328
views
Time complexity for solving linear congruences?
What is the best known algorithm to solve linear congruences of the form below?
$$a x + b \equiv 0 \space (n)$$
And what is the time complexity of it?
- 41
10
votes
1
answer
378
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 $N ...
- 101
7
votes
2
answers
293
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
1
vote
0
answers
268
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 ...
- 11
1
vote
2
answers
339
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 ...
- 133
7
votes
4
answers
1k
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 ...
16
votes
2
answers
1k
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 ...
- 263
11
votes
3
answers
1k
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 ...
- 1,735
8
votes
1
answer
245
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 $...
- 10.6k
37
votes
1
answer
1k
views
Efficiently computable function as a counter-example to Sarnak's Mobius conjecture
Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis.
Conjecture. Let $\mu(k)$ ...
- 7,648
28
votes
2
answers
1k
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 ...
- 751
7
votes
2
answers
361
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 ...
- 521
4
votes
1
answer
229
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}
\\+1\mbox{...
- 16.5k
11
votes
1
answer
898
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 ...
- 1,103
15
votes
0
answers
1k
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 ...
- 8,821
5
votes
0
answers
210
views
Possible connection between complexity of Factorials and the density of solution of a set of Diophantine equations
Let $P(x) \in \mathbb Z[x]$ of degree $\ge 2$ and $S = \{(x,n) \in \mathbb Z^{2}:P(x)=n!\}$. It is known:
$(a)$ $|S| < \infty$ under the $abc$ conjecture.
$(b)$ Density of $S$ in $\mathbb Z$ is $...
- 12.9k
3
votes
0
answers
103
views
A question on factorials
$P(x) = n!$ where $P(x) \in \mathbb Z[x]$ has finitely many $(x,n) \in \mathbb Z^{2}$ assuming $abc$ conjecture.
Consider the following variant: Given $c,d,r,s,k \in \mathbb Z$ and $P(x) = n!$ where ...
- 12.9k