Intereting Posts

Double Integration with change of variables
Klein-bottle and Möbius-strip together with a homeomorphism
Number of positive, negative eigenvalues and the number of sign changes in the determinants of the upper left submatrices of a symmetric matrix.
The function that draws a figure eight
interesting square of log sin integral
What are the formal terms for the intersection points of the geometric representation of the extended trigonometric functions?
Summing the cubes of the insertion sequence
Distance/Similarity between two matrices
How to evaluate $\int \cos^2x \ dx$
Does there exist a function satisfying $\sup \int\vert u\vert=0$?
Limit of an integral (remainder term of a Euler-Maclaurin expansion)
Asymptotic formula for $\sum_{n \le x} \frac{\varphi(n)}{n^2}$
More unknown / underappreciated results of Euler
Computing second partial derivative with polar coordinates
Solve three equations with three unknowns

Is there a fast way to compute the order of $a \pmod n$ without computing potentially all the powers of $a$ up to $n-1$? For example, in computing the order of $87 \pmod {101}$, the naïve way could require computing up to $87^{100}$, which I want to avoid.

- Solving recurrences with boundary conditions
- $n$-Bit Strings Not Containing $010$
- Modulus calculation for big numbers
- How to approach number guessing game(with a twist) algorithm?
- $\mathbb Z_p^*$ is a group.
- Prove “casting out nines” of an integer is equivalent to that integer modulo 9
- Computational complexity of least square regression operation
- Find all solutions to $x^9 \equiv 25$(mod 29)
- Is zero odd or even?
- Modulus trick in programming

$\phi(101) = 100$, so the order of $87$ must be a factor of $100$: $2, 4, 5, 10, 20, 25, 50,$ or $100$. So you only have to compute up to $87^{50}$ to get your answer $-$ if none of these is $1$, then the order of $87$ must be $100$. But this simple method can be implemented more or less efficiently:

If you simply calculate $87^k$ for $2 \le k \le 50$, you need 49 multiplications mod $101$. But as you probably know, you can calculate powers much more efficiently by repeated squaring. If you keep track of things properly, you can calculate $87^2, 87^4, 87^5, 87^{10}, 87^{20}, 87^{25},$ and $87^{50}$ in a single repeated-squaring chain:

$x = 87$

$p_5 = p_{25} = x$

$x \leftarrow x^2 = 87^2 \mod 101$

$p_2 = p_{10} = p_{50} = x$ (now $p_2 = 87^2 \mod 101$)

$x \leftarrow x^2 = 87^4 \mod 101$

$p_5 \leftarrow p_5 \times x$ (now $p_5 = 87^5 \mod 101$)

$p_4 = p_{20} = x$ (now $p_4 = 87^4 \mod 101$)

$x \leftarrow x^2 = 87^8 \mod 101$

$p_{10} \leftarrow p_{10} \times x$ (now $p_{10} = 87^{10} \mod 101$)

$p_{25} \leftarrow p_{25} \times x$

$x \leftarrow x^2 = 87^{16} \mod 101$

$p_{20} \leftarrow p_{20} \times x$ (now $p_{20} = 87^{20} \mod 101$)

$p_{25} \leftarrow p_{25} \times x$ (now $p_{25} = 87^{25} \mod 101$)

$p_{50} \leftarrow p_{50} \times x$

$x \leftarrow x^2 = 87^{32} \mod 101$

$p_{50} \leftarrow p_{50} \times x$ (now $p_{50} = 87^{50} \mod 101$)

If I have that right, then instead of $49$ multiplications, we only need five squarings and seven multiplications. And this method generalises very well to large integers, with better and better speed-ups for larger and larger numbers.

- Distance/Similarity between two matrices
- Mean value theorem for the second derivative, when the first derivative is zero at endpoints
- $(R^{\oplus A})^{\oplus B} \approx R^{\oplus (A\times B)}$?
- Necessary and Sufficient Conditions for Random Variables
- What is the Tarski–Grothendieck set theory about?
- Meaning of correlation
- Properties of the solutions to $x'=t-x^2$
- dropping a particle into a vector field
- Are there infinitely many primes of the form $n^2 – d$, for any $d$ not a square?
- How to calculate the area of a polygon?
- How to prove or statements
- Showing that if $\lim_{x\to\infty}xf(x)=l,$ then $\lim_{x\to\infty}f(x)=0.$
- The 6 generals problem
- Number of subsets of a set $S$ of n elements , is $2^n$
- if the sum of the digits of $a+b$, $b+c$ and $a+c$ is $<5$, then is the sum of the digits of $a+b+c$ less or equal than 50?