Questions tagged [nt.number-theory]
Questions in number theory
27
questions with no upvoted or accepted answers
17
votes
0answers
320 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 ...
15
votes
0answers
438 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}...
15
votes
0answers
1k 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 ...
11
votes
0answers
183 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
1answer
334 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 ...
8
votes
0answers
262 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 ...
7
votes
0answers
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 ...
7
votes
0answers
163 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$...
7
votes
0answers
293 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$, ...
6
votes
0answers
311 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 ...
6
votes
0answers
107 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,,\}$):
...
5
votes
0answers
140 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 \...
4
votes
0answers
176 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 ...
4
votes
0answers
294 views
Time complexity for solving linear congruences?
What is the best known algorithm to solve linear congruences of the form below?
$$a x + b \equiv 0 \space (n)$$
And what is the time complexity of it?
3
votes
0answers
225 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 &...
3
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
135 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, ...
2
votes
0answers
78 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$?
2
votes
0answers
249 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 ...
1
vote
0answers
99 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}=...
1
vote
0answers
66 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 ...
1
vote
0answers
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 ...
1
vote
0answers
129 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 ...
0
votes
0answers
29 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, ....
0
votes
0answers
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).
...
0
votes
0answers
122 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 ...
