The number-theory tag has no wiki summary.
-3
votes
0answers
41 views
C++ Polynomial Multiplication [closed]
\begin{eqnarray} \text{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~} \end{eqnarray}\begin{eqnarray}
\text{IF YOU HAVE A QUESTION, THEN ASK AND I CAN ...
5
votes
0answers
87 views
The length of the smallest co-prime chain between any two integers
I found a variant of this problem in one of the recent algorithms competitions.
Given any two integers ($A,B, A \lt B$), find the least number, $L$, of integers between $A$ and $B$ ($N_i, 1 \lt i ...
1
vote
1answer
42 views
Faster Algorithm for Computing Norm
Can anyone suggest an algorithm faster than $\Theta(n^{2})$ for computing the following function:
$$||n||:=\frac{1}{\max\{k \in \mathbb{N}: 1|n, 2|n,\ldots,k|n\}}$$
9
votes
2answers
291 views
Finding the size of the smallest subset with GCD = 1
This is a problem from the practice session of the Polish Collegiate Programming Contest 2012. Although I could find the solutions for the main contest, I can't seem to find the solution for this ...
9
votes
0answers
170 views
Complexity of deciding whether there is a winning strategy in the following game
The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 ...
6
votes
1answer
60 views
Quadratic residue and integer factoring
I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime).
I am looking at the ...
7
votes
1answer
144 views
Algorithmic consequences of algebraic formula for partition function?
Bruinier and Ono have found an algebraic formula for the partition function, which was widely reported to be a breakthrough. I am unable to understand the paper, but does it have any algorithmic ...
5
votes
1answer
161 views
In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?
The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test:
It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for ...
2
votes
0answers
99 views
Reduction from knapsack problem to Integer relation that equals one
My question is related to the Integer Relation Detection Problem which can be formulated as:
$\qquad a_1x_1 + a_2x_2 + \cdots + a_nx_n = 0$
Where $\forall i. a_i\in\mathbb{Z} \land a_i<c \land ...
2
votes
1answer
48 views
Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits
I was solving this equation:
$$\text{key}=\left(\sum_{K=0}^n\frac{1}{a^K}\right)\bmod{m}.$$
Given
$$ 1,000,000,000 < a, n, m \; < 5,000,000,000, $$
$$ a, m \text{ are coprime}. $$
I solved it ...
6
votes
2answers
349 views
How fast can we find all Four-Square combinations that sum to N?
A question was asked at Stack Overflow (here):
Given an integer $N$, print out all possible
combinations of integer values of $A,B,C$ and $D$ which solve the equation $A^2+B^2+C^2+D^2 = N$.
...
1
vote
0answers
155 views
Finding a sequence of numbers where every product of two mod k is unique
I want to make a sequence of numbers, where I pick the numbers $a_{0}, a_{1},..,a_{n}$. The length of the sequence is $n+1$.
Now I want the product of any pair of two numbers in the sequence modulo ...
8
votes
2answers
196 views
6
votes
1answer
108 views
Prove fingerprinting
Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that
$$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c ...
