# Questions tagged [nt.number-theory]

Questions in number theory

93 questions
Filter by
Sorted by
Tagged with
394 views

### Formalizing the “no formula for primes” intuition

I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt: Conjecture: There is no $O(n^2)$ expected time randomized algorithm to generate $\ge n$-...
24 views

### Is this a proof that diophantine equation solutions can't be bounded by power towers?

From this 2017 paper on upper bounds for solutions to diophantine equations: Conjecture 1. If a system of equations S ⊆ Bn has exactly one solution in positive integers x1, . . . , xn , then x1, ....
146 views

### Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?
74 views

### is factoring harder than deciding if all prime factors lie in a particular residue class?

Let $n$ be a large positive integer. Suppose I want to know if all the prime factors of $n$ are congruent to, say, 3 mod 8. Is this any easier than just factoring $n$?
453 views

### Is prime-counting function #P-complete?

Recall $\pi(n)$ the number of primes $\le n$ is the prime-counting function. By "PRIMES in P", computing $\pi(n)$ is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to ...
99 views

140 views

63 views

### Computing the class number using the prime factorization of the discriminant

i was wondering if there is a way to use the prime factorization of the discriminant $d$ when computing the class number $h(d)$. E.g., assume you have an integer $n = pq$ with $p \equiv 1\pmod{4}$ and ...
552 views

### Comparing two products of lists of integers?

Suppose I have two lists of positive integers of bounded manitude, and I take the product of all elements of each list. What's the best way to determine which product is larger? Of course I can ...
729 views

### Easy problems with hard counting versions

Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-...
102 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 ...
89 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 ...
149 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 ...
309 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 ...
162 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$...
107 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 ...
138 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 ...
336 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 ...
412 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?
899 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 ...
258 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 ...
134 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, ...
70 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). ...
248 views

2k 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 ...
107 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?
189 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 ...
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 ...