# Tagged Questions

Questions in number theory

75 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 ...
59 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)\}$ ...
72 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 ...
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 ...
180 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 ...
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$...
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 ...
116 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 ...
218 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 ...
365 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?
511 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 ...
224 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 ...
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, ...
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). ...
184 views

484 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 ...
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?
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 ...
121 views

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 ... 1answer 568 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 ... 4answers 604 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 ... 2answers 692 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 ... 1answer 554 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 ... 2answers 783 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 ... 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 ... 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 ... 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 ... 4answers 872 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 ... 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}... 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 ...
275 views

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$, ...
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/
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 ...
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 ...
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"). ...
646 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 ...
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$, ...
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-...
670 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 ...
215 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 ...
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 ...