Intereting Posts

Generalizing Ramanujan's $\pi$ formulas
Necessary/sufficient conditions for an infinite product to be exactly equal to $1$
Is there any geometric way to characterize $e$?
Metric on a Quotient of the Riemann Sphere
How to write an integral as a limit?
Why is $\sqrt{x}$ a function?
Can a function “grow too fast” to be real analytic?
Show $f$ is not $1-1$
Proof of Convergence: Babylonian Method $x_{n+1}=\frac{1}{2}(x_n + \frac{a}{x_n})$
Is this similarity to the Fourier transform of the von Mangoldt function real?
Sum of combinations of the n by consecutive k
Is there a way to write this expression differently: $\arctan 1/(1+n+n^2)$?
How is addition defined?
Show that every monotonic increasing and bounded sequence is Cauchy.
Isomorphism between tensor product and quotient module.

The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$

Normally one can use the “baby-steps giant-steps” algorithm to solve it fairly quickly. But when $\gcd(a,n) \neq 1,$ it is not possible to compute $a^{-1}\pmod{n},$ which the algorithm requires.

What algorithms are available to solve this problem in this case (apart from brute force of course)? Are there any theoretical limits on how fast such an algorithm could run?

- Solving recurrence relation: Product form
- gradient descent optimal step size
- $O(n)$ algorithm to determine a number that appears more than $n/2$ times in an array of size $n$
- how to solve the recurrence $T(n) = 2T(n/3) + n\log n$
- Subtracting two dates
- Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

- Reduction between languages in P
- Is $L_1$ context free language?
- The disease problem
- Is computer science a branch of mathematics?
- Algorithm for multiplying numbers
- Induction to prove $2n + 3 < 2^n$
- Convert Equilateral triangle to Isosceles triangle
- A natural number multiplied by some integer results in a number with only ones and zeros
- Computing the $n^{\textrm{th}}$ permutation of bits.
- How to maximize the number of operations in process

If $\gcd(a,n)=g>1$ then if $g\nmid b$ there’s clearly no solution. Otherwise write $a=g\alpha$, $b=g\beta$, $n=g\nu$, so

$$

a^x\equiv b\pmod{n} \iff g^{x-1}\alpha^x\equiv \beta \pmod{\nu}

$$

Since $\gcd(\alpha,\nu)=1$, $\alpha$ has an inverse mod $\nu$. Divide through by $\alpha$ to get

$$(g\alpha)^{x-1} = a^{x-1} \equiv \beta\alpha^{-1} \pmod{\nu}$$

If $\gcd(a,\nu)=1$ then you can use your preferred algorithm for the relatively prime case, otherwise repeat this reduction.

**Example 1**: $6^x \equiv 4 \pmod{44}$

Using $3\cdot 15 \equiv 1 \pmod{22}$ and $3\cdot 4 \equiv 1 \pmod{11}$:

$$

\begin{align}

2^{x-1}3^x & \equiv 2 \pmod{22} \\

6^{x-1} & \equiv 2\cdot 15 \equiv 8 \pmod{22} \\

2^{x-2}3^{x-1} & \equiv 4 \pmod{11} \\

6^{x-2} & \equiv 4\cdot4 \equiv 5 \pmod{11} \\

\end{align}

$$

Now $\gcd(6,11)=1$, so if you can solve this you might get $x-2=6$, $x=8$.

**Example 2**: $6^x \equiv 2 \pmod{44}$

Starting as in Example 1:

$$

\begin{align}

2^{x-1}3^x & \equiv 1 \pmod{22} \\

6^{x-1} & \equiv 2\cdot 15 \equiv 15 \pmod{22} \\

\end{align}

$$

and this has no solution since $\gcd(6,22) \nmid 15$.

This is very incomplete.

Since there are only a finite number of elements, eventually the sequence {a^{k} mod n}_{k$\ge$0} must become cyclic. So there are natural numbers $\sigma$ and $\lambda$ such that a^{$\sigma$ + v$\lambda$} = a^{$\sigma$} for all v.

So there are exactly two elements where you can’t calculate the element that came before it like you can in a cyclic group. The first is obviously 1 itself, the second is the first element of the cyclic part which is equal to both a^{$\sigma$-1}a and a^{$\sigma$+$\lambda$-1}a.

The problem is I think $\sigma$ can approach n so we’d spend all our time moving along the tail.

- Determining k: $\int_{6}^{16} \frac{dx}{\sqrt{x^3 + 7x^2 + 8x – 16}} = \frac{\pi}{k}$
- What is the meaning of normalization of varieties in complex geometry?
- Maximum number of edges in a simple graph?
- Dimension analysis of an integral
- If $G_1$ and $G_2$ are finite group and $H\leq G_1\times G_2$ then $H=P_1\times P_2$ with $P_i\leq G_i$?
- Expectation inequality for a set and its subset.
- Parallelogram law in normed vector space without an inner product.
- For a trigonometric polynomial $P$, can $\lim \limits_{n \to \infty} P(n^2) = 0$ without $P(n^2) = 0$?
- Fully independent events and their complements
- Dimension of the space of algebraic Riemann curvature tensors
- $n!$ is never a perfect square if $n\geq2$. Is there a proof of this that doesn't use Chebyshev's theorem?
- Euler characteristic of a covering space
- How to multiply and reduce ideals in quadratic number ring.
- Every prime ideal of a finitely generated $\mathbb{R}$-algebra is an intersection of maximal ideals?
- Understanding direct sum of matrices