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.

  • 2
    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$?2012-11-11
  • 0
    @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.2012-11-11
  • 1
    It would be appreciated if you adapt your wording and your layout to the conventions of mathematics and of this forum.2012-11-12
  • 0
    @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.2012-11-12
  • 0
    The question appears to make two conflicting statements about your objective. At one point you say that you want to solve this equation (presumably for $X$?); then later you say that you want to prove it to be true or false (presumably for given values of all variables?) -- which one is it? Or both? Also, do you literally mean that $X$ is a random number? If so, what is its distribution, and for which of the other variables do you want to solve, given $X$?2012-11-12
  • 0
    @joriki I already know ${X}$, I want to know if this equation is true for the values I have, without calculation all the powers etc... I will change my post, in the hope to clarify the question.2012-11-12
  • 0
    How can you expect to know whether a congruence holds, without calculating the numbers in it? How would you know whether $2^{20}=1048576$ without calculating $2^{20}$? There are efficient methods for calculating $b^c\bmod d$, even when the numbers involved are very large --- is that what you are after? I'm sure that question has been discussed here, thoroughly, before.2012-11-12
  • 0
    @GerryMyerson I know how the handle mod in combination with large powers, that isn't the problem. The main problem is that the left side of the equation requires a lot of time to calculate. I would indeed like to know the answer without calculating the numbers in it. If that's possible of course.2012-11-12
  • 2
    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](http://images.apple.com/acg/pdf/aks3.pdf)? There are probabilistic primaltity tests that are much easier to implement than the AKS algorithm like the [Miller-Rabin](http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test) test.2012-11-12
  • 0
    @miracle173 It is indeed step 5 of the algorithm. I will review the use of ${X}$, thanks for pointing that out. About probabilistic primaltity tests, they aren't 100% accurate and I cannot use that. I worked with Miller-Rabin and it gave me pseudo primes. Any way, I want to implement AKS, thanks for the comment.2012-11-12
  • 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