The nt.number-theory tag has no wiki summary.
16
votes
4answers
516 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 ...
9
votes
0answers
149 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 ...
9
votes
1answer
366 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
567 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 ...
0
votes
0answers
87 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
233 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
124 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 ...
18
votes
4answers
512 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 ...
13
votes
0answers
249 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
106 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
172 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/
10
votes
0answers
144 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
282 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 ...
6
votes
1answer
508 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
0answers
235 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 ...
4
votes
0answers
164 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
391 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 ...
15
votes
1answer
522 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
134 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
202 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, ...
27
votes
2answers
676 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
241 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
161 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
242 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
191 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
148 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
229 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 ...
8
votes
4answers
552 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 ...
13
votes
2answers
430 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
700 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
216 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 ...
31
votes
0answers
751 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 ...
22
votes
2answers
736 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
229 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
200 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
390 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
330 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 ...
23
votes
1answer
960 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 ...
11
votes
2answers
316 views
Efficiently getting bits of N! ?
Given $N$ and $M$, is it possible to get the $M$'th bit (or digit of any small base) of $N!$ in time/space of $O( p( ln(N), ln(M) ) )$, where $p(x, y)$ is some polynomial function in $x$ and $y$?
...
7
votes
2answers
2k views
How to check if a number is a perfect power in polynomial time
The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in ...
4
votes
2answers
300 views
Finding divisors of an interval of integers
This numerical problem arose in one of my projects. It seems simple at first sight, but I can't seem to find a good approach. Maybe someone else has an idea:
We have two integers, $n$ and $N$. Let's ...
