Trying to understand code for miller Rabin test

[feral perch]

so I'm trying to understand this code for Miler Rabin test.
I saw a bunch of videos explaining the general idea mathematically,
https://www.youtube.com/watch?v=zmhUlVck3J0
(here I understood that if n divides one of the terms then it's prime, if it doesn't divide any of the terms then it's composite, but I didn't really understand why we have to get the exponent to an odd number, like I kind of get the idea but not really)
https://www.youtube.com/watch?v=qdylJqXCDGs
(I understood in this video the idea mathematically more, I also understood that the main point is
if a^exp ≡ 1 (mod n) then it's composite
if it's a^exp ≡ -1 (mod n) it's probably prime.

I also watched a videio explaining how ro implemet in python.
https://www.youtube.com/watch?v=-BWTS_1Nxao

Here is the main problem that I don't understand
in the video he talks about it from about minute 8, it's the second condition where he returns true meaning the number is composite and I don't undertand why the condition lets the number be composite espisially that he says that a^exp ≡ -1 (mod n) is eqivelant to a^exp ≡ -n-1 (mod n) how and why
and if it's equivilant why is that in other videios they say if
a^exp ≡ -1 (mod n) means that the number is prime?

so I have a similer code written in java cuz I'm used to java more:
the code is in the reply message

[frail umbra]

⌛ This post has been reserved for your question.

Hey @feral perch! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

[feral perch]

` public static boolean composite(long n, int a) {
//this test checks if n is composite and returns true
//if it's probably prime, it returns false

    // Initialize exp with n - 1.
    long exp = n - 1;

    ////assuming n is prime, so n-1 (exp) is even.
    while (exp % 2 == 0) // Make exp an odd number by dividing by 2 until it's no longer even.
    {
        exp >>= 1;// Bitwise right shift, equivalent to dividing by 2
    }

//Here is the segment of code I don't undertand
if (modularExponentiation(a, exp, n) == 1) // Check if a^exp ≡ 1 (mod n), if true, then n is composite.
{
return true;//it's composite
}

    while (exp < n - 1) {
        if (modularExponentiation(a, exp, n) == n - 1) {
            return true;
        }
        exp <<= 1;// Bitwise left shift, equivalent to multiplying by 2.
    }

    return false;
}

public static boolean millerRabinTest(long n, int k) {
    for (int i = 0; i < k; i++) {
        int a = getRandomInt(2, (int) (n - 1));
        if (!composite(n, a)) {
            return false;
        }
    }
    return true;
}`

[simple crane]

In mod n everything is divided by n.

So -1 ≡ -n-1 (mod n) and -1 ≡ n-1 (mod n)

For example -1 ≡ -21 (mod 20) and -1 ≡ 19 (mod 20)

if a^exp ≡ 1 (mod n) then it's composite
if it's a^exp ≡ -1 (mod n) it's probably prime.
That's not true.

[feral perch]

I understood this and the example you gave of how that would make his statement that -1 ≡ n-1 (mod n)

[feral perch]

I know this generly but I don't get your point of how does this info mean that if a^exp ≡n -1 (mod n) means that n is composite

[simple crane]

It's not composite, it's probably prime.

All goes from Fermat's Little Theorem.

[feral perch]

while (exp < n - 1) { if (modularExponentiation(a, exp, n) == n - 1) { return true; } exp <<= 1;// Bitwise left shift, equivalent to multiplying by 2. }

but this part of the code states that if a^exp ≡n -1 (mod n) it returns true which means that it's composite

[simple crane]

Are you sure that the code is right?

Here's some pseudo-code from Wikipedia:

        if y = 1 and x ≠ 1 and x ≠ n − 1 then # nontrivial square root of 1 modulo n
            return “composite”

Note ≠

[feral perch]

I took it from the video and I ran it and it worked

[simple crane]

            if (!composite(n, a)) {
                return false;
            }

Ouch, it seems that the function's name is at least wrong?

[feral perch]

The video put singleTest but I felt composite works better

in readibility

[simple crane]

Well, it doesn't describe what that function does, lol.

[feral perch]

What I understoo from the video that it returns true if the number is composite false if it's prime

[simple crane]

It's opposite.

And it's not prime, but strong prime, it could be composite.

[feral perch]

so the code works but the namings are wrong?

for composite method

[simple crane]

Yes

[feral perch]

so it returns true if it's prime false if it's composite?

anfd it returns true beacuse for a number to be probably prime
i a^exp ≡ 1 (mod n)
or
a^exp ≡ -1 (mod n)
?

[simple crane]

Yes, by definition the number is probably prime if one of this condition is true.

Wait, no.

The second one has 2^r in exponent.

[feral perch]

it has 2^r because each time we are multiplying by 2 right?

so just for it to become clear in my head we first make the exp odd to check if a^exp ≡ 1 (mod n)
if its not congruent to 1
then wetest if th other terms are congruent to -1 by multiplying each time by 2

[simple crane]

Yes

[feral perch]

mmm now why is it if we have the exponent odd and
a^exp ≡ 1 (mod n)
then it's prime

[simple crane]

That's Fermat's Little Theorem, but modified.

Because if a^2b ≡ 1 (mod n) then a^b ≡ 1 (mod n)

[feral perch]

What I know is that fermat's little theorem is:
a^(n-1) ≡ 1 (mod n)

so how do we go from that to
a^exp ≡ 1 (mod n)

or wait we just mean that exp=n-1 right?

[simple crane]

At the beginning

And then you divide it by 2 multiple times because 1^2 = 1 (AFAIR n has to be prime for that to be true in a modulo group)

[feral perch]

could you give me an example to actually see it cuz chatGPT doesn't understand me well to give me examples

like I want to try dividing by 2 and getting to an odd number to test if a^exp ≡ 1 (mod n)