Questions tagged [nt.number-theory]

Questions in number theory

32 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
348 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,698
447 views

• 4,900
210 views

• 12.5k
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 ...
• 12.5k
109 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 ...
136 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, ...
• 5,070
102 views

A question on factorials

$P(x) = n!$ where $P(x) \in \mathbb Z[x]$ has finitely many $(x,n) \in \mathbb Z^{2}$ assuming $abc$ conjecture. Consider the following variant: Given $c,d,r,s,k \in \mathbb Z$ and $P(x) = n!$ where ...
• 12.5k
81 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
262 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 ...
• 578
81 views

Algorithmic Number Theory Problem - related to Matrix Multiplication Complexity

Let $F(x) = \displaystyle\sum_{i=0}^{n-1}a_{i}x^{i}$, $G(x,y) = \displaystyle\sum_{i=0}^{n_{x}-1}\sum_{j=0}^{n_{y}-1}a_{ij}x^{i}y^{j} \in \mathbb Z[x,y]$ with $a_{i},a_{ij} \in [0,p-1]$ for some prime ...
• 12.5k
1 vote