# Tag Info

Accepted

• 269k
Accepted

### Quick calculation for $(x^y) \bmod z$

Here is the quickest way I can think. Assume first that $x$ and $z$ are coprime. Factor $z = \prod_i p_i^{a_i}$ and calculate $\varphi(z) = \prod_i p_i^{a_i-1} (p_i-1)$. Compute $x' = x \pmod{z}$ and ...
• 269k
Accepted

### What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

Large numbers are factored with the General Number Field Sieve, which is, as of now, the fastest non-quantum algorithm. You can find the heuristic runtime in the linked Wikipedia-article. Also in use ...
• 1,841
Accepted

### Checking whether an integer is a square or higher power

The standard algorithm for determining whether an integer $n$ is a perfect power goes like this. We check whether it is a perfect $k$th power for $k \in \{2,\ldots,\log n\}$; as an optimization, it ...
• 269k
The average magnitude $m$ of a number of $k$ binary digits is an exponential function of $k$ (because $k= \lfloor{\log_2{m}}\rfloor + 1$, $m>0$). Using only zero, equality, and the successor ...