Intereting Posts

Locus using Euclidean geometry
Constructing two tangents to the given circle from the point A not on it
problems with singularity $0$ of $\int_{W} \frac{e^{\frac{1}{z}}}{(z-3)^3} dz$.
In how many possible ways can we write $3240$ as a product of $3$ positive integers $a$, $b$ and $c$?
How to solve for a variable that is only in exponents?
How to integrate $\int \frac{e^x dx}{1\,+\,e^{2x}}$
Polynomial Interpolation and Security
Why do we say “almost surely” in Probability Theory?
Does this inequality involving differences between powers hold on a particular range?
Permutations of a string with duplicate characters
How to maximize profit in this equation?
Suppose $|G| = 105$. Show that it is abelian if it has a normal $3$-Sylow subgroup.
Combinatorial proof of binomial coefficient summation
Cross product: matrix transformation identity
Sums of Consecutive Cubes (Trouble Interpreting Question)

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?

- Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$
- What better way to check if a number is a perfect power?
- Finding Required Permutation
- Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days
- Continued fraction expansion related to exponential generating function
- Prime number generator, how to make

- Fastest way to calculate $e^x$ up to arbitrary number of decimals?
- Counting permutations, with additional restrictions
- Development of a specific hardware architecture for a particular algorithm
- Is $L_1$ context free language?
- Efficiently testing if sigma(n) = m
- Is Dijkstra's algorithm optimal for unweighted graphs?
- How to prove that this function is primitive recursive?
- Are points on the complex plane sufficient to solve every solvable equation composed of the hyperoperators, their inverses, and complex numbers?
- Solving recurrences with boundary conditions
- Formal proof for detection of intersections for constrained segments

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.

- Complex exponent with real part = 1/2 should convert x into -x
- How do I extend RS-integral to bounded variation parameters?
- Probability of waiting for an interview
- How to prove $\int^{\pi/2}_0 \log{\cos{x}} \, \mathrm{d}x = \pi/2 \log{1/2}$
- Basis for the intersection of two integer lattices
- Sum of multiplication of all combination of m element from an array of n elements
- How to prove that this set of elements are linearly independent?
- Primitive characters mod k
- What is the color number of the 3D space, if we allow only convex regions?
- Proving there is no natural number which is both even and odd
- Odds of winning at minesweeper with perfect play
- If two real matrices are conjugated over $\mathbb{C}$, are they then also conjugated over $\mathbb{R}$?
- Question about Quaternion group $Q_8$ and Dihedral group $D_8$
- Show $a_{n+1}=\sqrt{2+a_n},a_1=\sqrt2$ is monotone increasing and bounded by $2$; what is the limit?
- How to find a basis of an image of a linear transformation?