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,

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

  • 2
    $\begingroup$ I normally read "!=" to mean not equals. Is that your intent? Also, does "% n" mean modulo $n$? Lastly, what is $r$? Do you intend somethng to be true for all values of $n$ and $r$? $\endgroup$
    – 2'5 9'2
    Commented Nov 11, 2012 at 18:32
  • $\begingroup$ @alex.jordan != is how I use it in the equation, the opposite is the same to me. % is indeed module. r is an Integer with a minimal value of 3. $\endgroup$
    – Mixxiphoid
    Commented Nov 11, 2012 at 21:51
  • 1
    $\begingroup$ It would be appreciated if you adapt your wording and your layout to the conventions of mathematics and of this forum. $\endgroup$
    – miracle173
    Commented Nov 12, 2012 at 7:52
  • $\begingroup$ @miracle173 could you please help me with that? I did my best, but as noted in the post, I have no mathematics background. Feel free to edit any thing. $\endgroup$
    – Mixxiphoid
    Commented Nov 12, 2012 at 7:56
  • 2
    $\begingroup$ I took a look at the wikipedia article. Should your relation be the if-condition in step 5 of the algorithm in the article? This would not be the case as far as I can see. The X in this algorithm is a variable and not an integer number. Did you notice that there is also a link to implementation details for the algorithm that points to article? There are probabilistic primaltity tests that are much easier to implement than the AKS algorithm like the Miller-Rabin test. $\endgroup$
    – miracle173
    Commented Nov 12, 2012 at 18:36


You must log in to answer this question.

Browse other questions tagged .