MHB Can we use this method to efficiently check if $N$ is composite?

[evinda]

Hello! (Wave)

According to some notes, we can check if $N$ is composite as follows.

We consider a reasonably small prime $R$.
Instead of computing $(X+A)^N$ in order to check whether $(X+A)^N \mod{N}=(X^N+A) \mod{N}$ , we compute the remainder when $(X+A)^N$ is divided by $X^R-1$. That's done using the same method we learn in algebra class for dividing one polynomial by another. What's nice about the remainder is that it has only $R+1$ terms, as opposed to $N+1$ for the expansion of $(X+A)^N$. So if $R$ is small enough , we can actually compute the remainder - using the repeated squaring trick. It is obvious that the identity

$(X+A)^N \mod{(N,X^R-1)}=(X^N+A) \mod{(N,X^R-1)}$

is always true when $N$ is a prime.

If $N$ is composite , and if we choose the right value of $R$, then we need to try only a small number of $A$'s until we find one such that

$(X+A)^N \mod{(N, X^R-1)} \neq (X^N+A) \mod{(N, X^R-1)}$.

Once we find such an $A$, we have proved that $N$ is composite. There is a deterministic way to pick the $A$'s.First of all, why does the remainder of $(X+A)^N$ divided by $X^R-1$ have $R+1$ terms and not $R$ ?Secondly, how can we compute the remainder using the repeated squaring trick and without writing the expansion of $(X+A)^N$?

 

[I like Serena]

First of all, why does the remainder of $(X+A)^N$ divided by $X^R-1$ have $R+1$ terms and not $R$ ?

Hey evinda! (Smile)

That looks like a typo.
We'd get a polynomial up to power $R-1$, so the number of terms should indeed be $R$.

Secondly, how can we compute the remainder using the repeated squaring trick and without writing the expansion of $(X+A)^N$?

If $N$ is for instance even, we can write $(X+A)^N \equiv ((X+A)^2)^{N/2} \equiv (X^2+2AX+A^2)^{N/2}$.
Now we can take the remainder of $X^2+2AX+A^2$ and repeat. (Thinking)

 

[evinda]

Hey evinda! (Smile)

That looks like a typo.
We'd get a polynomial up to power $R-1$, so the number of terms should indeed be $R$.

Do we justify it as follows?

We have that $(X+A)^N=(X^R-1)(X^{N-R}+p(X))+r(X)$ for some polynomials $p(X)$ and $r(X)$ with $\deg{r(X)} \leq R-1$.

So the remainder of the division of $(X+A)^N$ by $X^R-1$ has at most $R$ terms.

If $N$ is for instance even, we can write $(X+A)^N \equiv ((X+A)^2)^{N/2} \equiv (X^2+2AX+A^2)^{N/2}$.
Now we can take the remainder of $X^2+2AX+A^2$ and repeat. (Thinking)

Ok... But how do we find like that the remainder of $(X+A)^N$ divided by $X^R-1$ ? (Thinking)

 

[I like Serena]

Do we justify it as follows?

We have that $(X+A)^N=(X^R-1)(X^{N-R}+p(X))+r(X)$ for some polynomials $p(X)$ and $r(X)$ with $\deg{r(X)} \leq R-1$.

So the remainder of the division of $(X+A)^N$ by $X^R-1$ has at most $R$ terms.

Seems fine to me.

Ok... But how do we find like that the remainder of $(X+A)^N$ divided by $X^R-1$ ? (Thinking)

Let's pick an example. (Wait)

Suppose we pick $(X+A)^N=(x+1)^2$ and $X^R-1=x-1$.
Can we use polynomial long division to find the remainder? (Wondering)

 

[evinda]

Let's pick an example. (Wait)

Suppose we pick $(X+A)^N=(x+1)^2$ and $X^R-1=x-1$.
Can we use polynomial long division to find the remainder? (Wondering)

Using the euclidean division, we get that $x^2+2x+1=(x-1)(x+3)+4$.

But in order to apply the euclidean division, we write out the expansion of $(x+1)^2$, don't we? (Thinking)

 

[I like Serena]

Using the euclidean division, we get that $x^2+2x+1=(x-1)(x+3)+4$.

Yep. So $(x+1)^2 \equiv 4 \mod{(x-1)}$.

But in order to apply the euclidean division, we write out the expansion of $(x+1)^2$, don't we?

Indeed.
So let's pick $(x+1)^4$ as another example.
We have that:
$$(x+1)^4 \equiv ((x+1)^2)^2 \equiv 4^2 \mod{(x-1)}$$

 

[evinda]

Yep. So $(x+1)^2 \equiv 4 \mod{(x-1)}$.

(Nod)

Indeed.
So let's pick $(x+1)^4$ as another example.
We have that:
$$(x+1)^4 \equiv ((x+1)^2)^2 \equiv 4^2 \mod{(x-1)}$$

I see... And then we apply the euclidean division of $x^4+1$ by $x-1$ and get that the remainder is $2$ and so we deduce that $4$ is composite, right?

 

[I like Serena]

I see... And then we apply the euclidean division of $x^4+1$ by $x-1$ and get that the remainder is $2$ and so we deduce that $4$ is composite, right?

Yes, since $2\not\equiv 4 \mod 4$. (Nod)

 

[evinda]

Yes, since $2\not\equiv 4 \mod 4$. (Nod)

I see... (Nod)

We could deduce that $8$ is composite as follows, right?

We have that $(x+3)^8=((x+3)^2)^4$.

Also $(x+3)^2=x^2+6x+9=x^2-1+6x+10 \pmod{x^2-1}=6x+10 \pmod{x^2-1}$.

Therefore, $(x+3)^8=(6x+10)^4 \equiv (-2x+2)^4 \pmod{8}=(2x-2)^4 \pmod{8}$.

And then, we have that $(2x-2)^4=((2x-2)^2)^2=(4x^2-8x+4)^2 \pmod{x^2-1}$.

$4x^2-8x+4= 4x^2-4-8x+8 \equiv 4(x^2-1)-8x+8 \equiv -8x+8 \pmod{x^2-1} \equiv 0 \pmod{8}$.

And so we have that $(x+3)^8 \equiv 0 \pmod{8, x^2-1}$.

By applying the euclidean division of $x^8+3$ with $x^2-1$, we see that the remainder is 4.

Since $4 \not\equiv 0 \pmod{8} $ we deduce that $8$ is composite.

 

[evinda]

In order to show that $13$ is a prime number ,I have done the following:

$$(x+2)^{13}=(x+2)^{12} (x+2)=((x+2)^2)^6 (x+2)$$

$$(x+2)^2=x^2+4x+4=(x^2-1)+4x+5 \equiv 4x+5 \pmod{x^2-1}$$

So:

$$(x+2)^{13}=(4x+5)^6 (x+2) \pmod{x^2-1}=((4x+5)^2)^3(x+2) \pmod{x^2-1}$$$$(4x+5)^2=16x^2+40x+25=16x^2-16+40x+41 \equiv 40x+41 \pmod{x^2-1} \equiv x+2 \pmod{13}$$Then we have that: $(x+2)^{13}=(x+2)^3(x+2) \pmod{13, x^2-1}=(x+2)^2 (x+2)^2 \pmod{13, x^2-1}$.

$(x+2)^2=x^2+4x+4=(x^2-1)+ 4x+5 \equiv 4x+5 \pmod{x^2-1}$.$(4x+5)^2=16x^2+40x+25=(16x^2-16)+40x+41=x+2$.
So, $(x+2)^{13}=x+2 \pmod{13, x^2-1}$.By applying the euclidean division of $x^{13}+2$ with $x^2-1$ we get that the remainder is $x+2$.Since $(x+2)^{13} \pmod{13,x^2-1}=(x^{13}+2) \pmod{13, x^2-1}$ we deduce that $13$ is prime.

 

[I like Serena]

Yep. Nice! (Happy)

 

[evinda]

Yep. Nice! (Happy)

Great! (Smirk) What is the time complexity of the repeated squaring trick?

 

[I like Serena]

Great! (Smirk) What is the time complexity of the repeated squaring trick?

Hmm... we just did 2 and 4 with R=1 (actually not a prime but we'll overlook that), and 8 and 13 with R=2.
How many squarings did we need? (Wondering)

Since $(x+2)^{13} \pmod{13,x^2-1}=(x^{13}+2) \pmod{13, x^2-1}$ we deduce that $13$ is prime.

Btw, this is not sufficient to prove that $13$ is prime.
According to the theorem we have to verify the same thing for a number of different values of $A$. (Nerd)

 

[evinda]

Hmm... we just did 2 and 4 with R=1 (actually not a prime but we'll overlook that), and 8 and 13 with R=2.
How many squarings did we need? (Wondering)

In order to show that 4 is composite we needed 1 squaring, to show that 8 is composite we needed 2 squarings and for the number 13, we needed 4 squarings. So for the last 2 numbers, we needed $\lfloor{\log_2{n} \rfloor}$ squarings, right? (Thinking)

Btw, this is not sufficient to prove that $13$ is prime.
According to the theorem we have to verify the same thing for a number of different values of $A$. (Nerd)

Is this sure? Because according to my notes:

If $N$ is composite , and if we choose the right value of $R$, then we need to try only a small number of $A$'s until we find one such that

$(X+A)^N \mod{(N, X^R-1)} \neq (X^N+A) \mod{(N, X^R-1)}$.

Once we find such an $A$, we have proved that $N$ is composite.

(Thinking)

 

[I like Serena]

In order to show that 4 is composite we needed 1 squaring, to show that 8 is composite we needed 2 squarings and for the number 13, we needed 4 squarings. So for the last 2 numbers, we needed $\lfloor{\log_2{n} \rfloor}$ squarings, right? (Thinking)

There you go. We have the time complexity for the case we only have to try one value of A, and for a value of R that is sufficiently low with respect to N.
Note that the 'normal' way to check if N is prime, is to check divisibility of all numbers up to $\sqrt N$.

Is this sure? Because according to my notes:

Yes. It's what it says there.
We need to try a number of A's until we find the inequality.
And we have tried A=1, and found it gave an equality.
So we would need to try again. (Thinking)

 

[evinda]

In order to show that 4 is composite we needed 1 squaring, to show that 8 is composite we needed 2 squarings and for the number 13, we needed 4 squarings. So for the last 2 numbers, we needed $\lfloor{\log_2{n} \rfloor}$ squarings, right? (Thinking)

Since $\lceil{\log_2{13} }\rceil=4$, we need $\lceil{\log_2{n} \rceil}$ squarings, thinking about it again... Don't we? (Thinking)

There you go. We have the time complexity for the case we only have to try one value of A, and for a value of R that is sufficiently low with respect to N.
Note that the 'normal' way to check if N is prime, is to check divisibility of all numbers up to $\sqrt N$.

So at the 'normal' way, the time complexity is $O(c \lceil{\log_2{n} \rceil})=O(\log n)$, right?

Yes. It's what it says there.
We need to try a number of A's until we find the inequality.
And we have tried A=1, and found it gave an equality.
So we would need to try again. (Thinking)

Yes, because we may find that $(X+A)^N=(X^N+A) \pmod{N, X^R-1}$ for some $A,N,R$ but for some others $A,N,R$ it could hold that $(X+A)^N \neq (X^N+A) \pmod{N, X^R-1}$.

So we have to check the equality/ inequality for sufficient different values of $A,N,R$, right?

 

[I like Serena]

Since $\lceil{\log_2{13} }\rceil=4$, we need $\lceil{\log_2{n} \rceil}$ squarings, thinking about it again... Don't we? (Thinking)

Erm... whatever... I'll stick to $O(\log_2 n)$. (Whew)

So at the 'normal' way, the time complexity is $O(c \lceil{\log_2{n} \rceil})=O(\log n)$, right?

That should be $O(\sqrt N)$. (Worried)

Yes, because we may find that $(X+A)^N=(X^N+A) \pmod{N, X^R-1}$ for some $A,N,R$ but for some others $A,N,R$ it could hold that $(X+A)^N \neq (X^N+A) \pmod{N, X^R-1}$.

So we have to check the equality/ inequality for sufficient different values of $A,N,R$, right?

We want to find whether a specific $N$ is prime or composite.
And I believe we select one specific $R$.
So we would need to check for sufficient different values of $A$ until we find an inequality (or not).
It does say that there's a "deterministic way to pick the $A$'s", so whatever that is, we need to check all of those.
Suppose there are $k$ values of $A$ that we have to check, then the time complexity becomes $O(k\log_2 N)$. (Thinking)

 

[evinda]

Erm... whatever... I'll stick to $O(\log_2 n)$. (Whew)

(Nod)

That should be $O(\sqrt N)$. (Worried)

Oh yes, that's what I meant. I wrote the time complexity when using the repeated squaring trick.

We want to find whether a specific $N$ is prime or composite.
And I believe we select one specific $R$.
So we would need to check for sufficient different values of $A$ until we find an inequality (or not).
It does say that there's a "deterministic way to pick the $A$'s", so whatever that is, we need to check all of those.
Suppose there are $k$ values of $A$ that we have to check, then the time complexity becomes $O(k\log_2 N)$. (Thinking)

I understand... (Smile)

It says at my first post that $R$ should be small enough. How small should it be? Is there a relation in respect to $N$ that it should satisfy ? (Thinking)

 

[I like Serena]

It says at my first post that $R$ should be small enough. How small should it be? Is there a relation in respect to $N$ that it should satisfy ? (Thinking)

We would need to investigate. In practice it may be a matter of trial and error.
If we pick $R=N+1$ we won't do any squaring tricks, but we will immediate be done, only to repeat for different values of $A$.
Presumably we would need $O(\sqrt N)$ different values for $A$, meaning it would be just as fast as the 'normal' method.

More generally the complexity is $O(k(1 + \lceil\log_2\frac N {R-1}\rceil) = O(k\log_2 \frac N R)$.
Basically it all depends on how many values for $A$ we will need to try.
Do you have any information on this "deterministic way to pick the $A$'s"? (Wondering)

 

[evinda]

If we pick $R=N+1$ we won't do any squaring tricks, but we will immediate be done, only to repeat for different values of $A$.
Presumably we would need $O(\sqrt N)$ different values for $A$, meaning it would be just as fast as the 'normal' method.

We would need to check all the values of $A$, such that $(A,N)=1$, i.e. $\phi(N)$ values. So the time complexity would be $O(\phi(N))$, right?

More generally the complexity is $O(k(1 + \lceil\log_2\frac N {R-1}\rceil) = O(k\log_2 \frac N R)$.

How do we get this time complexity? (Thinking)

Basically it all depends on how many values for $A$ we will need to try.
Do you have any information on this "deterministic way to pick the $A$'s"? (Wondering)

No, it isn't given any further information. (Shake)

 

[I like Serena]

We would need to check all the values of $A$, such that $(A,N)=1$, i.e. $\phi(N)$ values. So the time complexity would be $O(\phi(N))$, right?

Erm... that is a lot of values to check... and I'm not aware of a straight forward method to find those. (Sweating)
If we find an $A$ such that $(A,N)\ne 1$, we already know that $N$ is composite!
And if we find that all possible values of $A$ are co prime, we already know that $N$ is prime.

How do we get this time complexity?

If $N \le R-1$, there is nothing to reduce, meaning we have $k$ checks - one for every $A$.
If $N \le 2(R-1)$, we need to use one iteration of the squaring trick for every value of $A$.
If $2^{m-1}(R-1) < N \le 2^m(R-1)$, we need to reduce $m$ times for every value of $A$.
So in general we need $mk$ reductions, where $m = \lceil\log_2\frac{N}{R-1}\rceil$. (Thinking)

 

[evinda]

If we find an $A$ such that $(A,N)\ne 1$, we already know that $N$ is composite!
And if we find that all possible values of $A$ are co prime, we already know that $N$ is prime.

Yes, I understand. (Nod)

If $N \le 2(R-1)$, we need to use one iteration of the squaring trick for every value of $A$.
If $2^{m-1}(R-1) < N \le 2^m(R-1)$, we need to reduce $m$ times for every value of $A$.
So in general we need $mk$ reductions, where $m = \lceil\log_2\frac{N}{R-1}\rceil$. (Thinking)

Could you explain to me how we deduce this? I haven't understood it... (Sweating)

 

[I like Serena]

Could you explain to me how we deduce this? I haven't understood it... (Sweating)

Suppose $N<R$, how many squaring reductions do we need? None yes?
And for $N=R$ we need 1 squaring reduction.

Now how big must $N$ be in relation to $R$ before we need 2 squaring reductions (that reduce the polynomial to one of degree $R-1$)? (Wondering)
And for which $N$ do we need 3 squaring reductions for the first time?

 

[evinda]

Suppose $N<R$, how many squaring reductions do we need? None yes?

Yes.

And for $N=R$ we need 1 squaring reduction.

Yes, for $N=R$ we will compute $(X+A)^R=((X+A)^2)^{\frac{R}{2}} \pmod{N, X^R-1}$ and since $\frac{R}{2}<R$ we won't do any further squaring reductions. Right?

Now how big must $N$ be in relation to $R$ before we need 2 squaring reductions (that reduce the polynomial to one of degree $R-1$)? (Wondering)

That's what we get when making 2 squaring reductions:

$$(X+A)^N=((X+A)^2)^{\frac{N}{2}}=(X^2+2AX+A^2)^{\frac{N}{2}}= ((X^2+2AX+A^2)^2)^{\frac{N}{4}} \pmod{N, X^R-1}$$

So in this case it has to hold that $\frac{N}{4}<R$.

And for which $N$ do we need 3 squaring reductions for the first time?

When we make 3 squaring reductions:

$$(X+A)^N=((X+A)^2)^{\frac{N}{2}}=(X^2+2AX+A^2)^{\frac{N}{2}}=((X^2+2AX+A^2)^2)^{\frac{N}{4}}\pmod{N, X^R-1}= \\(((X^2+2AX+A^2)^2)^2)^{\frac{N}{8}} \pmod{N,X^R-1}$$

So in this case it has to hold that $\frac{N}{8}<R$.

So in general, making $i$ squaring reductions, it has to hold that $\frac{N}{2^i}<R$, right?
If so, how do we use this to find the time complexity? (Thinking)

 

[I like Serena]

Yes, for $N=R$ we will compute $(X+A)^R=((X+A)^2)^{\frac{R}{2}} \pmod{N, X^R-1}$ and since $\frac{R}{2}<R$ we won't do any further squaring reductions. Right?

To be exact, it depends on whether $N=R$ is even or odd.
For even $N$ we would compute $(X+A)^N=((X+A)^2)^{\frac{N}{2}} \pmod{N, X^R-1}$.
And for odd $N$ we woud compute $(X+A)^N=((X+A)^2)^{\frac{N-1}{2}}(X+A) \pmod{N, X^R-1}$.
Still, let's count this as 1 'squaring reduction'.

That's what we get when making 2 squaring reductions:

$$(X+A)^N=((X+A)^2)^{\frac{N}{2}}=(X^2+2AX+A^2)^{\frac{N}{2}}= ((X^2+2AX+A^2)^2)^{\frac{N}{4}} \pmod{N, X^R-1}$$

So in this case it has to hold that $\frac{N}{4}<R$.

Yes, so for $N < 4R$ we need at most 2 squaring reductions.
What is the highest value of $N$ that 1 squaring reduction suffices?

When we make 3 squaring reductions:

$$(X+A)^N=((X+A)^2)^{\frac{N}{2}}=(X^2+2AX+A^2)^{\frac{N}{2}}=((X^2+2AX+A^2)^2)^{\frac{N}{4}}\pmod{N, X^R-1}= \\(((X^2+2AX+A^2)^2)^2)^{\frac{N}{8}} \pmod{N,X^R-1}$$

So in this case it has to hold that $\frac{N}{8}<R$.

So in general, making $i$ squaring reductions, it has to hold that $\frac{N}{2^i}<R$, right?
If so, how do we use this to find the time complexity? (Thinking)

The time complexity is given by the number of squaring reductions ($i$) that we have to do.
Can we solve the inequality for $i$? (Wondering)

 

[evinda]

To be exact, it depends on whether $N=R$ is even or odd.
For even $N$ we would compute $(X+A)^N=((X+A)^2)^{\frac{N}{2}} \pmod{N, X^R-1}$.
And for odd $N$ we woud compute $(X+A)^R=((X+A)^2)^{\frac{N-1}{2}}(X+A) \pmod{N, X^R-1}$.
Still, let's count this as 1 'squaring reduction'.

(Nod)

Yes, so for $N < 4R$ we need at most 2 squaring reductions.
What is the highest value of $N$ that 1 squaring reduction suffices?

For $N=3R$ we need at least 2 squarings, and for $N=2R$ we need 2 squarings. So the highest value of $N$ that $1$ squaring reduction suffices is $N=R$, right? (Thinking)

The time complexity is given by the number of squaring reductions ($i$) that we have to do.
Can we solve the inequality for $i$? (Wondering)

$\frac{N}{2^i}<R \Rightarrow \frac{N}{R}<2^i \Rightarrow i>\log_2{\frac{N}{R}}$.

But.. don't we need to find an upper bound of the number of squaring reductions?

 

[I like Serena]

For $N=3R$ we need at least 2 squarings, and for $N=2R$ we need 2 squarings. So the highest value of $N$ that $1$ squaring reduction suffices is $N=R$, right?

How about $N=R+1$?

$\frac{N}{2^i}<R \Rightarrow \frac{N}{R}<2^i \Rightarrow i>\log_2{\frac{N}{R}}$.

But.. don't we need to find an upper bound of the number of squaring reductions?

Then let's try to find that upper bound, or rather, the lower bound for $\frac N{2^i}$. (Thinking)

 

[evinda]

How about $N=R+1$?

When $R$ is even, we have that $(X+A)^{R+1}=(X+A)^R(X+A)=((X+A)^2)^{\frac{R}{2}} (X+A) \pmod{N, X^R-1}$.

So considering that $R<2N$, we will need one squaring.

When $R$ is odd, then $(X+A)^{R+1}=((X+A)^2)^{\frac{R+1}{2}} \pmod{N, X^R-1}$.

So when $R<2N-1$ we will need one squaring.

Then let's try to find that upper bound, or rather, the lower bound for $\frac N{2^i}$. (Thinking)

To have one squaring, the lowest possible value of $R$ is $1$, to have 2 squarings this value becomes $2N+1$, right?

 

[I like Serena]

When $R$ is even, we have that $(X+A)^{R+1}=(X+A)^R(X+A)=((X+A)^2)^{\frac{R}{2}} (X+A) \pmod{N, X^R-1}$.

So considering that $R<2N$, we will need one squaring.

When $R$ is odd, then $(X+A)^{R+1}=((X+A)^2)^{\frac{R+1}{2}} \pmod{N, X^R-1}$.

So when $R<2N-1$ we will need one squaring.

Then how about $N=R+2, ..., N=2R-1, N=2R$? (Wondering)

To have one squaring, the lowest possible value of $R$ is $1$, to have 2 squarings this value becomes $2N+1$, right?

Let's assume $R$ to be a fixed unknown value.
We want to know for which $N(R)$ we need at least 2 squaring reductions and at most 2 squaring reductions. (Thinking)

 

[evinda]

Then how about $N=R+2, ..., N=2R-1, N=2R$? (Wondering)

When $N=R+1$ and $R$ is even , we need one squaring reduction when $R>2$.
When $R$ is odd, we need one squaring reduction when $R>1$.

When $N=2R-1$, we have that $(X+A)^{2R-1}=(X+A)^{2R-2}(X+A) \pmod{N, X^R-1}=((X+A)^2)^{R-1}(X+A) \pmod{N,X^R-1}$.

Since $R-1<R$, we need exactly one squaring reduction.

For $N=2R$, we have:

$(X+A)^{2R}=((X+A)^2)^{R} \pmod{N, X^R-1}=(((X+A)^2)^2)^{\frac{R}{2}} \pmod{N, X^R-1}$

So in this case we need two squaring reductions, right?

Let's assume $R$ to be a fixed unknown value.
We want to know for which $N(R)$ we need at least 2 squaring reductions and at most 2 squaring reductions. (Thinking)

The smallest value of $N(R)$ for which we need 2 squaring reductions is $N(R)=2R$, right?For $N(R)=3R$ we need three squaring reductions, don't we? (Thinking)