1
$\begingroup$

I have the following equation.

$(X + a)^n\equiv(X^n + a)(X^r - 1)\bmod n.$

This is part of the AKS algorithm.

The problem is, that I'll have to solve this equation for every $1\leq a<10$ and $n$ can become quite big. With big I mean at least 100.000.000. So are dealing here with big powers. All numbers are positive Integers and $X$ is a random prime number and $3\leq X\leq 2000$ and is different for every $a$. $r$ is at least $3$ and can become as high as a million.

The question:
I want to know if it is possible to proof this equation without calculating the actual values. (The powers etc...) I don't want the proof just for this equation but for all equations in general, where it would take too long to calculate both parts of the equation and compare the results.

I have no mathematics background or what so ever, so be easy with the terms please :).

What I tried:
Not much, since I have no idea where to start. I have tried to simplify the equation with Wolfram Mathematica, but it gave me the same equation.

If you need more information, please leave a comment.

Thanks in advance,
Mixxiphoid

EDIT:
${X}$ is always a prime.
I edited the first paragraph concerning the meaning of the variables.

  • 0
    I think the world would be interested to know of examples where Miller-Rabin gave pseudoprimes that turned out not to be primes.2012-11-13

0 Answers 0