The 2024 Developer Survey results are live! See the results

# Questions tagged [nt.number-theory]

Questions in number theory

108 questions
Filter by
Sorted by
Tagged with
109 views

### Time complexity of square root floor

Given a square number in $n$ bits can we compute its square root in $O(n)$ time? In general can we compute $\lfloor\sqrt{a}\rfloor$ in $O(\log a)$ time?
• 13.1k
79 views

### Evidence extended GCD is in $TC^0$

Despite centuries of search extended $GCD$ is known to accommodate one algorithm which is the Euclidean algorithm (the solution through Integer Linear Programming which needs basis reduction goes ...
• 13.1k
77 views

Addition chains are a well-known way of building up a number from 1 by adding two previously computed numbers. It is a long-standing open problem to determine the complexity of computing the length of ...
• 14.1k
1 vote
91 views

• 2,099
495 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$-...
• 3,263
46 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, ....
1 vote
236 views

### Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?
• 31
83 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$?
• 241
516 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 ...
• 812
1 vote
103 views

• 13.1k
147 views

• 261
1 vote
94 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 ...
• 615
807 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 ...
• 233
848 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$-...
• 13.1k
119 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 ...
• 243
1 vote
90 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 ...
• 2,013
172 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 ...
• 561
377 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 ...
• 3,798
173 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$...
• 1,224
116 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 ...
147 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 ...
• 13.1k
425 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 ...
• 13.1k
423 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?
1k 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 ...
330 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 ...
• 149
156 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, ...
73 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). ...
• 149
297 views

### Integer factorization using polynomial whose roots are prime factors

Let $n$ be a square-free positive integer, let $n=p_{1}p_{2}\ldots p_{k}$ be the prime factorization of $n$ into $k$ distinct primes $p_{i}$. For such $n$, define \$F_{n}(x)\triangleq\prod_{i=1}^{k}(x-...
• 727