Questions tagged [nt.number-theory]

Questions in number theory

Filter by
Sorted by
Tagged with
-3 votes
2 answers
184 views

pq factorization

If I tried to factor a semiprime as the product of the two prime factors given below in the form pq on a home computer would I be successful? p=(2^1024-1)+644 prime factor q=(2^1028-1)+188 prime ...
user68942's user avatar
3 votes
1 answer
248 views

Is modular square roots modulo primes in $NC$?

Assume modulus is prime. Is modular square roots then in $NC$? If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
Turbo's user avatar
  • 12.8k
1 vote
0 answers
103 views

On the borderline between natural and artificial problems

While there is no formal definition of what constitutes a natural algorithmic problem, in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
Andras Farago's user avatar
3 votes
0 answers
264 views

Is the following equitable factoring problem $NP$-hard or in $P$?

Consider the following factoring problem: Given an integer $r$ and another integer $N$ along with all of its $n$ number of prime factors and their corresponding multiplicities $\{p_i,e_i\}_{i=1}^n$, ...
Turbo's user avatar
  • 12.8k
0 votes
1 answer
143 views

What is a known sequence for which being constant is not provable?

My question concerns the property of being constant for computable functions ${\mathbb N}\to \{0,1\}$, within any common framework $T$ strong enough to include Heyting arithmetic (and of course not ...
Nikolaj-K's user avatar
  • 505
21 votes
2 answers
1k views

Decidability of diophantine equations over {=, +, gcd}

It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, ...
Caleb Stanford's user avatar
5 votes
2 answers
264 views

Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?

Since $e$ is transcendental, the function $f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$ is injective, $$ f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots ...
Lieuwe Vinkhuijzen's user avatar
9 votes
1 answer
489 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$-...
Geoffrey Irving's user avatar
0 votes
0 answers
45 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, ....
ghosts_in_the_code's user avatar
1 vote
1 answer
230 views

Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?
nocitome's user avatar
2 votes
0 answers
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$?
Tim kinsella's user avatar
20 votes
1 answer
509 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 ...
Igor Pak's user avatar
  • 812
1 vote
0 answers
102 views

Complexity of planted root of a system of quadratic homogeneous polynomials?

Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\dots=f_{m}=...
Turbo's user avatar
  • 12.8k
14 votes
4 answers
618 views

Base-k representations of the co-domain of a polynomial - is it context-free?

In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open: Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ for ...
DG_'s user avatar
  • 411
5 votes
1 answer
193 views

Complexity of counting integer roots of multivariate polynomials in a polyhedron?

Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total ...
Turbo's user avatar
  • 12.8k
14 votes
1 answer
1k views

Deciding whether an interval contains a prime number

What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an $\tilde O(L)$ algorithm, where $L$ is the length of the ...
Elliot Gorokhovsky's user avatar
3 votes
0 answers
265 views

Primality in $NC$ hierarchy?

AKS primality testing solves whether a given integer is prime in $P$. AKS algorithm is following: Input: integer n > 1. Check if $n$ is a perfect power: if $n = a^b$ for integers $a > 1$ and $b &...
Turbo's user avatar
  • 12.8k
5 votes
0 answers
147 views

How hard is it to generate a set of relatively prime numbers between two given bounds?

Informal Question How hard is it to generate a set of relatively prime numbers between two given bounds? Decision Problem Given $a$, $b$, and $k \in \mathbb{N}$. Does there exist a set $S \...
Michael Wehar's user avatar
2 votes
1 answer
158 views

Is there any time efficient way of achieving the result of FKS hashing lemma?

FKS hashing lemma states. Given a set of $n-$bit numbers $\{x_1,x_2,\dots,x_k\}$ there exist a prime $p$ of $O(\log n + \log k)$-bit such that $x_i$ mod $p \neq $ $x_j$ mod $p$ if $x_i \neq x_j$...
Vimal Raj Sharma's user avatar
0 votes
1 answer
91 views

Does this pairwise independent random process have expected max load $\sqrt{n}$?

This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load $\sqrt{n}$ . There the following question is asked and answered in ...
Simd's user avatar
  • 3,950
1 vote
1 answer
324 views

Relation between transcendental numbers and computational complexity?

Regarding the relation, there is the Hartmanis-Stearns conjecture, but beyond Turing Machine of the realtime output, there is no further conjecture or theorem. Obviously irrational algebraic number ...
XL _At_Here_There's user avatar
6 votes
0 answers
319 views

Is there any algorithm outputing $e$ in real time?

The Hartmanis-Stearns Conjecture says that a number computed in real time by a Turing Machine is either rational or transcendental. We know that there is some transcendental (Liouville) number that ...
XL _At_Here_There's user avatar
10 votes
1 answer
351 views

Algorithm to compute distance between powers

Given coprime $a, b$, can you quickly compute $$ \min_{x, y > 0} |a^x - b^y| $$ Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these ...
Gautam's user avatar
  • 261
4 votes
1 answer
1k views

Is Hartmanis-Stearns conjecture settled by this article?

The paper "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited" by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec https://arxiv.org/abs/1601....
XL _At_Here_There's user avatar
3 votes
0 answers
46 views

Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?

Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ is irreducible what is the best technique to factor such ...
Turbo's user avatar
  • 12.8k
8 votes
0 answers
303 views

Algorithms to generate consecutive primes

The prime number theorem, states that the "average length" of the gap between a prime $p$ and the next prime is ln(p). I am looking for (preferably deterministic efficient) an algorithm that generates ...
Mohammad Al-Turkistany's user avatar
6 votes
2 answers
288 views

Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

I need to quickly evaluate $a^{b^c} \mod n$ where $c$ is pretty big. Using the usual repeated squaring trick, this can be performed in $O(\log(b^c)) = O(c)$ time. In my problem, $c$ is huge, (say, $&...
Gautam's user avatar
  • 261
1 vote
0 answers
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 ...
Etsch's user avatar
  • 615
10 votes
1 answer
785 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 ...
user168715's user avatar
22 votes
5 answers
837 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$-...
Turbo's user avatar
  • 12.8k
2 votes
1 answer
118 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 ...
xyz's user avatar
  • 243
1 vote
0 answers
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 ...
Alexey Milovanov's user avatar
7 votes
0 answers
169 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 ...
ricardorr's user avatar
  • 541
18 votes
0 answers
369 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 ...
Henry Yuen's user avatar
  • 3,748
7 votes
0 answers
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$...
Lior Eldar's user avatar
  • 1,224
3 votes
0 answers
114 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 ...
user avatar
-2 votes
1 answer
146 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 ...
Turbo's user avatar
  • 12.8k
-3 votes
1 answer
421 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 ...
Turbo's user avatar
  • 12.8k
12 votes
1 answer
422 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?
user avatar
19 votes
1 answer
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 ...
Frédéric Grosshans's user avatar
3 votes
1 answer
303 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 ...
Tacet's user avatar
  • 149
4 votes
0 answers
150 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, ...
user avatar
0 votes
0 answers
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). ...
Dave's user avatar
  • 149
6 votes
1 answer
289 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-...
Gorav Jindal's user avatar
8 votes
2 answers
820 views

Is square removal easier than factoring?

It seems to me that the square removal task can be reduced to the factoring task, but that there is no way to reduce factoring to square removal. Is there a way to make this "feeling" more precise, i....
Thomas Klimpel's user avatar
8 votes
1 answer
823 views

Downward self-reducibility of factorization

Is integer factorization downward self-reducible? Is anything known about this?
Gorav Jindal's user avatar
4 votes
1 answer
144 views

Solving a system of sums-of-powers polynomials

What is the complexity of calculating the values of the integers $x_i$, where $0 \leq x_1 < x_2 < \dots < x_k < n$, given only the values $s_m = \sum_{i=1}^k x_i^m$? for $1 \leq m \leq k$? ...
jbapple's user avatar
  • 11.2k
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 ...
john mangual's user avatar
2 votes
1 answer
285 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 ...
mathersjj1's user avatar
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,,\}$): ...
Marzio De Biasi's user avatar