Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
Turbo's user avatar
  • 13.9k
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 ...
Greggz's user avatar
  • 123
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 ...
Turbo's user avatar
  • 13.9k
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 ...
Turbo's user avatar
  • 13.9k
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 ...
Turbo's user avatar
  • 13.9k