All Questions
5 questions
4
votes
0
answers
104
views
Questions in number theory related to $NC$ and $P$-completeness
Given $a,b\in\mathbb N$ find $\operatorname{GCD}(a,b)$.
Given $a,b,c\in\mathbb N$ find $x,y\in\mathbb Z$ such that $ax+by=c$.
Euclidean algorithm solves both.
My question is if either 1 or 2 is in ...
2
votes
1
answer
913
views
Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way [closed]
I need to emulate this sequence for a program: http://oeis.org/A025302
Stuff that I've taken into account:
After finding the prime divisors of a number. I take any divisor as p and apply the ...
2
votes
0
answers
221
views
Modular inverse computation - avoiding Euclidean algorithm
Modular inverse is known to be computable by Extended Euclidean algorithm which is the reaping the rewards of computing the GCD of two numbers or proving two numbers are coprime.
If we already know ...
0
votes
1
answer
87
views
Constructing an integer with small residues for two distinct primes in polynomial time
Given two primes $p,q\in[T,2T]$, how many integers $m$ of size $O(T^{3/2+\epsilon})$ are there such that the residues $m\bmod p$ and $m\bmod q$ are both $O(polylog(T))$? Looking for an answer
Is it ...
0
votes
0
answers
122
views
Will an integer program to deterministically factor integers help derandomize $\mathbb F_q[x]$ factoring?
There are many analogies between the objects $\mathbb F_q[x]$ and $\mathbb Z$.
Supposing there is a fixed (say $10^9$) dimension linear integer program (describable without any objective function) in ...