Intereting Posts

How many geometrical interpretations does matrix multiplication have?
Does orthogonality of vectors depend on the chosen basis?
If $(X,d)$ is a metric space then I want to show that limit point compactness and sequential compactness are equivalent.
Why does $ \frac{2x}{2+x}$ provide a particularly tight lower bound for $\ln(1+x)$ for small positive values of $x$?
Burgers equation with initial data $u(x,0) = x^2$
About $\lim \left(1+\frac {x}{n}\right)^n$
An easy way to remember PEMDAS
Chain rule for multivariable functions confusion
How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
Show $\frac{1}{4}\leq \mu(A\cap B \cap C)$
Definition of Submanifold of Topological Manifold
Gamma function of negative argument
Prove that square root of 2 is irrational using the principle of Mathematical Induction
Find points along a Bézier curve that are equal distance from one another
question involving Markov chain

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.

- Factoring large integers without a cluster
- Prove Euler's Theorem when the integers are not relatively prime
- Algorithm for constructing primes
- Chaitin's constant and coding undecidable propositions in a number
- How to find inverse of 2 modulo 7 by inspection?
- Generating a Eulerian circuit of a complete graph with constant memory
- Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version
- How to test if a graph is fully connected and finding isolated graphs from an adjacency matrix
- Fractals using just modulo operation
- All pairs shortest path in undirected and unweighted graphs

$\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.

- An incorrect method to sum the first $n$ squares which nevertheless works
- Proving $\lim \limits_{n\to +\infty } \left(1+\frac{x}{n}\right)^n=\text{e}^x$.
- Why isn't $\mathbb{R}^2$ a countable union of ranges of curves?
- What is the math notation for this type of function?
- Probability measure on $\mathcal{P}(\mathbb{R})$
- What is the difference between square of sum and sum of square?
- Why is there a $p\in \mathbb{N}$ such that $mr – p < \frac{1}{10}$?
- Types of polynomial functions. Quadratic, cubic, quartic, quintic, …,?
- graph vertex chromatic number in a union of 2 sub-graphs
- Proving Functions are Surjective
- The center of a non-Abelian group of order 8
- $\{x^nf(x)\}_{n\in\mathbb{N}}\subset L_2(a,b)$ as a complete system
- Group theory proof of existence of a solution to $x^2\equiv -1\pmod p$ iff $p\equiv 1 \pmod 4$
- Is irrational times rational always irrational?
- Let $f,g$ be two distinct functions from $$ to $(0, +\infty)$ such that $\int_{0}^{1} g = \int_{0}^{1} f $.